作者tkcn (小安)
站內Prob_Solve
標題Re: [問題] 一個演算法相關的問題
時間Wed Jun 8 13:28:23 2011
※ 引述《walker2009 (不害怕。不後悔)》之銘言：
: 想請問一個演算法相關的問題
: 假設我有一段 text, 長度是 n
: 另外還有一段 pattern, 長度是 m
: 其中 n > m
: 我知道說, 在 text 的哪些位置是 character 'X', 共 A 個
: 我也知道, 在 pattern 的哪些位置是 character 'X', 共 B 個
: 我想求, pattern 從 text 的第一個位置滑到最後一個位置時
: 其中哪些位置是 pattern 中的 'X' 有對到 text 中的 'X' 的
: 只要任意一個 X 對到就可以了, 不用全部對到
: 當然最暴力的做法的時間複雜度會是 O(A*B)
: 可是因為我們知道, 這些位置最多就是 n 個
: A*B 的作法會重複算到一些位置
: 請問這個問題有辦法在 O(n + m) 裡面解出來嗎??
: 或是拜託有經驗的大大可以提供相關的關鍵字讓我去搜尋~
: 想 google 或爬文都不知道該如何下手 Orz
: 謝謝^^
註： 以下是看錯題目時寫的解法，
適用在找出 T 中有多少個 X 能夠被 P 中的 X cover。
T: [....X......X......XXX.....X]
P: [.X...X..] (P 放最左邊的情況)
[.X...X..] (P 放最右邊的情況)
|------------------| (第一個 X 所能 cover 的位置)
|------------------| (第二個 X 所能 cover 的位置)
注意到一個特性，每一個 X 所能 cover 的長度都是一樣的，
所以越晚出現的 X 也會結束的較晚，不會有晚出現先結束的狀況。
按照先後順序處理 P 中的 X，
每次都從上次能 cover 到的結尾開始就好。
複雜度是 |P| + |T|。
沒說的很細，不過我想這樣夠了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
1F：推 walker2009:感謝 t大~ 參悟中! 06/08 13:29
2F：推 walker2009:這樣省到的只有尾巴的長度為 m 的那一小段 06/08 13:32
3F：→ tkcn:突然發現 IP 好近呀... 06/08 13:33
4F：→ walker2009:痾...不對...我想說的是...這個做法好像不太對@@ 06/08 13:33
5F：→ walker2009:XD 06/08 13:33
6F：→ walker2009:真的耶... 06/08 13:33
7F：→ tkcn:難道我又誤會題目了嗎...Orz 06/08 13:35
8F：→ walker2009:第一個 X 可以 cover 到的範圍之內, 也是需要考慮 06/08 13:35
9F：→ walker2009:pattern 其他 X 的位置, 因為他們的 shift 會導致 06/08 13:35
你是要 T 中的 X 能被 cover 的數量?
還是 P 中的 X 能對應到 T 中的 X 的數量?
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 13:36)
10F：→ walker2009: pattern 的起始點不一樣 06/08 13:36
11F：→ walker2009:oh... 我大概知道我語病在哪了... 可能又要改題目了QQ 06/08 13:36
12F：推 walker2009:我要的是...pattern在 shift 到哪一個位置時, 會有XX對 06/08 13:43
13F：→ walker2009:也就是所有 shift 的值 06/08 13:43
14F：→ walker2009:我稍微改一下題目了...Q_Q 這樣還有語病嗎 06/08 13:43
重新確認一下 :)
如果 T 和 shift 過的 P 在相同位置都是 X，稱為配對成功。
你要求的是所有能夠配對成功的 shift，是這樣嗎?
另一個問題:
: 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)
所以 P 的尾端超出 T 是允許的囉?
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 14:00)
15F：→ walker2009:嗯嗯 所有配對成功的 shift~ 06/08 14:09
16F：→ walker2009:一般而言是不能超過,但是允許超過也無所謂~不影響big O 06/08 14:09
我是覺得能不能超過得先講清楚，
因為也許會有個演算法只能算出允許超過的。
所以如果你真正要的是不允許超過的，還是直接定義清楚比較好。
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 17:13)
17F：→ walker2009:嗯~ 我要的是不允許超過的~ 06/08 17:17
18F：→ walker2009:就是要 pattern 可以每個位置都對到 text 的~ 不能凸出 06/08 17:18
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 18:36)