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

[yauhh (喲)]

※ 引述《walker2009 (不害怕。不後悔)》之銘言：
: 想請問一個演算法相關的問題
: 假設我有一段 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)

最後這個敘述看不懂,好像所指的pattern可以任意伸縮長度一樣. 不過,不管這個
敘述,看你問題描述,似乎可以反向解:

因為當你講 X--X 這個pattern時,意思其實是 X--- 或 ---X,那就簡單了.

接下來只要從text線性走過,找到每個 X 並把前後四位之內都標出來就是答案.

例如
      1 2 3 4 5 6 7 8 9
        X   X X       X

找到 2 標出 2; 找到 4 標出 1,2,4; 找到 5 標出 2,4,5; 找到 9 標出 6.

之後再將重複結果統一即可.


--
/yau

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.231.66.68
→ yauhh:另一個問題是,你怎麼肯定想要找O(n+m)的解?
→ suhorng:原PO的意思應該是指 text跟pattern的任一個M有對應到
→ suhorng:那段意思是說, text長度是n, pattern長度是m
→ suhorng:而對於位置i, 若 (p[1],t[i]) (p[2],t[i+1]) ...
→ suhorng:(p[m], t[i+m-1]) 中有任一個pair是 (M,M), 就說pattern
→ suhorng:在text+i這個位置match  這樣? 然後要找出所有match的i
→ angleevil:其實tag固定在頭尾的話,也是可以做出這效果
推 walker2009:嗯嗯@@ 是要找 suhorng大說的那個
→ walker2009:yau大的作法看起來是 O(nm)~
→ walker2009:我不確定有 linear time 的解啦XD 只是一開始看到
→ walker2009:這問題, 看起來很簡單, 我跟幾個朋友都覺得應該可以
→ walker2009:但後來卻都想不出 linear time 的解, 因此想說問看看
→ walker2009:有沒有人處理過類似問題, 或是有關鍵字可以提供查詢@@
→ yauhh:我看你要先把一個問題定清楚：
→ yauhh:怎
→ yauhh:麼說pattern case可以拉到討論O(m)的程度。
→ yauhh:以本例來看，只明確看到你要找二個offsets：0，3
→ yauhh:二個Offsets相關字元都是X。另外，別的位子是否not X也可以
→ yauhh:現在具體的pattern很小，整個其實化約成O(n)了。
推 AstralBrain:你是來回答問題還是來否定整個問題的...
推 ledia:推樓上... 別擔心, 反正大家都有看懂就好了 XD
→ angleevil:~"~這問題,我至少誤解三次以上.演算法真是新人勿碰阿
→ yauhh:你認為我否定問題？我認為我是幫他補強問題
→ yauhh:如果你不認同我的看法，可以發表你自己的解。不必無謂相爭
→ yauhh:原po應該可以參考這篇:
→ yauhh:http://en.wikipedia.org/wiki/Suffix_tree
→ yauhh:所討論的不是相同的問題,但有很接近目標的感覺.
推 walker2009:嗯@@ 我有想過 suffix tree, 但最後還是會轉回
→ walker2009:don't care matching, 掉到 O(n log m)
→ angleevil:其實看到原po給的連結,和其他給的連結
→ angleevil:就算用到boolean convolution,應該也是要對text的index
→ angleevil:和pattern index.到最後更加無法理解logm的由來.
→ yauhh:log的出現通常跟tree有關係
推 LPH66:既然能看成 index 那可以更進一步這樣看:
→ LPH66:原問題等同於求 {p-q | p \in P, q \in Q}
→ LPH66:其中 P \subseteq {1,2,3,...,n} Q \subseteq {1,2,3,...,m}
→ LPH66:這和多項式乘法有點類似  自然就能有類似 FFT 的做法
→ LPH66:(其實就是 boolean convolution 在做的事了}
→ LPH66:這裡 log 的出現就和 FFT 的 divide & conquer 做法有關
→ LPH66:而比較沒有明顯的樹存在
推 DJWS:如果字元數不多的話　是不是可以用hash table？
→ DJWS:      種類
推 walker2009:可以這麼想, 因為我只 care X 這個 character
→ walker2009:所以我把其他 character 都換成 O 也沒關係,不影響答案
→ walker2009:因此這個問題可以想成只有 2 種 character
推 ledia:hash table worst case 也會是 O(nm)
→ firejox:二進位碼？
→ angleevil:~"~所以這題有實作出來嗎? 如果有的話,不知道可以po上來
→ angleevil:嗎? 讓小弟知道怎麼做