[問題] 一個演算法相關的問題

看板Prob_Solve作者walker2009 (不害怕。不後悔)時間13年前 (2011/06/08 12:53)推噓0(0推 0噓 6→)

留言6則, 2人參與討論串1/3 (看更多)

※ [本文轉錄自 C_and_CPP 看板 #1DxlxA8d ] 作者: walker2009 (不害怕。不後悔) 看板: C_and_CPP 標題: [問題] 一個演算法相關的問題時間: Wed Jun 8 12:47:04 2011 抱歉 @@ 因為沒有演算法的專版, 之前在此版常受到大家幫忙所以還是來最常逛的 C/C++ 版來發問了 =================================== 想請問一個演算法相關的問題假設我有一段 text, 長度是 n 另外還有一段 pattern, 長度是 m 其中 n > m 我知道說, 在 text 的哪些位置是 character 'X', 共 A 個我也知道, 在 pattern 的哪些位置是 character 'X', 共 B 個我想求, pattern 從 text 的第一個位置滑到最後一個位置時其中哪些位置是 pattern 中的 'X' 有對到 text 中的 'X' 的只要任意一個 X 對到就可以了, 不用全部對到也就是 find all 1<= i <= n, such that for pairs (p[1],t[i]) , (p[2],t[i+1]) , ... , (p[m],t[i+m-1]) 至少有一個 pair 是 (X,X) 給個例子 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 如果 T = X O O O X O X X O O X X O O O P = X O O X 我們求出來的解是 1, 2, 4, 5, 7, 8, 9, 11, 12 這幾個位置因為當 P shift 到這幾個位置時, 都會有 X 對上 X 的情況 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T = X O O O X O X X O O X X O O O 1 P = X O O X 2 X O O X 4 X O O X 5 X O O X 7 X O O X 8 X O O X 9 X O O X 11 X O O X 12 X O O X 當然最暴力的做法的時間複雜度會是 O(A*B) 可是因為我們知道, 這些位置最多就是 n 個 A*B 的作法會重複算到一些位置請問這個問題有辦法在 O(n + m) 裡面解出來嗎?? 或是拜託有經驗的大大可以提供相關的關鍵字讓我去搜尋~ 想 google 或爬文都不知道該如何下手 Orz 謝謝^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.217

→

walker2009

06/08 12:47,

06/08 12:47

→

james732

06/08 12:51,

06/08 12:51

→

walker2009

06/08 12:52,

06/08 12:52