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

[tkcn (小安)]

※ 引述《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
推 walker2009:感謝 t大~ 參悟中!
推 walker2009:這樣省到的只有尾巴的長度為 m 的那一小段
→ tkcn:突然發現 IP 好近呀...
→ walker2009:痾...不對...我想說的是...這個做法好像不太對@@
→ walker2009:XD
→ walker2009:真的耶...
→ tkcn:難道我又誤會題目了嗎...Orz
→ walker2009:第一個 X 可以 cover 到的範圍之內, 也是需要考慮
→ walker2009:pattern 其他 X 的位置, 因為他們的 shift 會導致
你是要 T 中的 X 能被 cover 的數量?
還是 P 中的 X 能對應到 T 中的 X 的數量?
※ 編輯: tkcn            來自: 140.114.78.231       (06/08 13:36)
→ walker2009: pattern 的起始點不一樣
→ walker2009:oh... 我大概知道我語病在哪了... 可能又要改題目了QQ
推 walker2009:我要的是...pattern在 shift 到哪一個位置時, 會有XX對
→ walker2009:也就是所有 shift 的值
→ walker2009:我稍微改一下題目了...Q_Q 這樣還有語病嗎
重新確認一下　:)

如果 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)
→ walker2009:嗯嗯  所有配對成功的 shift~
→ walker2009:一般而言是不能超過,但是允許超過也無所謂~不影響big O
我是覺得能不能超過得先講清楚，
因為也許會有個演算法只能算出允許超過的。
所以如果你真正要的是不允許超過的，還是直接定義清楚比較好。
※ 編輯: tkcn            來自: 140.114.78.231       (06/08 17:13)
→ walker2009:嗯~ 我要的是不允許超過的~
→ walker2009:就是要 pattern 可以每個位置都對到 text 的~ 不能凸出
※ 編輯: tkcn            來自: 140.114.78.231       (06/08 18:36)