作者yauhh (喲)
看板Prob_Solve
標題Re: [問題] 一個演算法相關的問題
時間Thu Jun 9 09:34:56 2011
※ 引述《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
1F：→ yauhh:另一個問題是,你怎麼肯定想要找O(n+m)的解? 06/09 09:41
2F：→ suhorng:原PO的意思應該是指 text跟pattern的任一個M有對應到 06/09 11:05
3F：→ suhorng:那段意思是說, text長度是n, pattern長度是m 06/09 11:05
4F：→ suhorng:而對於位置i, 若 (p[1],t[i]) (p[2],t[i+1]) ... 06/09 11:06
5F：→ suhorng:(p[m], t[i+m-1]) 中有任一個pair是 (M,M), 就說pattern 06/09 11:06
6F：→ suhorng:在text+i這個位置match 這樣? 然後要找出所有match的i 06/09 11:06
7F：→ angleevil:其實tag固定在頭尾的話,也是可以做出這效果 06/09 11:43
8F：推 walker2009:嗯嗯@@ 是要找 suhorng大說的那個 06/09 13:04
9F：→ walker2009:yau大的作法看起來是 O(nm)~ 06/09 13:18
10F：→ walker2009:我不確定有 linear time 的解啦XD 只是一開始看到 06/09 13:19
11F：→ walker2009:這問題, 看起來很簡單, 我跟幾個朋友都覺得應該可以 06/09 13:19
12F：→ walker2009:但後來卻都想不出 linear time 的解, 因此想說問看看 06/09 13:19
13F：→ walker2009:有沒有人處理過類似問題, 或是有關鍵字可以提供查詢@@ 06/09 13:19
14F：→ yauhh:我看你要先把一個問題定清楚： 06/09 13:28
15F：→ yauhh:怎 06/09 13:29
16F：→ yauhh:麼說pattern case可以拉到討論O(m)的程度。 06/09 13:30
17F：→ yauhh:以本例來看，只明確看到你要找二個offsets：0，3 06/09 13:32
18F：→ yauhh:二個Offsets相關字元都是X。另外，別的位子是否not X也可以 06/09 13:35
19F：→ yauhh:現在具體的pattern很小，整個其實化約成O(n)了。 06/09 13:38
20F：推 AstralBrain:你是來回答問題還是來否定整個問題的... 06/09 15:58
21F：推 ledia:推樓上... 別擔心, 反正大家都有看懂就好了 XD 06/09 16:38
22F：→ angleevil:~"~這問題,我至少誤解三次以上.演算法真是新人勿碰阿 06/09 17:19
23F：→ yauhh:你認為我否定問題？我認為我是幫他補強問題 06/09 18:15
24F：→ yauhh:如果你不認同我的看法，可以發表你自己的解。不必無謂相爭 06/09 18:17
25F：→ yauhh:原po應該可以參考這篇: 06/09 22:55
27F：→ yauhh:所討論的不是相同的問題,但有很接近目標的感覺. 06/09 22:58
28F：推 walker2009:嗯@@ 我有想過 suffix tree, 但最後還是會轉回 06/09 23:33
29F：→ walker2009:don't care matching, 掉到 O(n log m) 06/09 23:33
30F：→ angleevil:其實看到原po給的連結,和其他給的連結 06/10 09:35
31F：→ angleevil:就算用到boolean convolution,應該也是要對text的index 06/10 09:36
32F：→ angleevil:和pattern index.到最後更加無法理解logm的由來. 06/10 09:37
33F：→ yauhh:log的出現通常跟tree有關係 06/10 21:17
34F：推 LPH66:既然能看成 index 那可以更進一步這樣看: 06/11 03:19
35F：→ LPH66:原問題等同於求 {p-q | p \in P, q \in Q} 06/11 03:19
36F：→ LPH66:其中 P \subseteq {1,2,3,...,n} Q \subseteq {1,2,3,...,m} 06/11 03:20
37F：→ LPH66:這和多項式乘法有點類似 自然就能有類似 FFT 的做法 06/11 03:20
38F：→ LPH66:(其實就是 boolean convolution 在做的事了} 06/11 03:21
39F：→ LPH66:這裡 log 的出現就和 FFT 的 divide & conquer 做法有關 06/11 03:21
40F：→ LPH66:而比較沒有明顯的樹存在 06/11 03:21
41F：推 DJWS:如果字元數不多的話 是不是可以用hash table？ 06/11 07:14
42F：→ DJWS: 種類 06/11 07:15
43F：推 walker2009:可以這麼想, 因為我只 care X 這個 character 06/12 00:44
44F：→ walker2009:所以我把其他 character 都換成 O 也沒關係,不影響答案 06/12 00:45
45F：→ walker2009:因此這個問題可以想成只有 2 種 character 06/12 00:45
46F：推 ledia:hash table worst case 也會是 O(nm) 06/14 09:08
47F：→ firejox:二進位碼？ 06/14 19:54
48F：→ angleevil:~"~所以這題有實作出來嗎? 如果有的話,不知道可以po上來 06/15 21:45
49F：→ angleevil:嗎? 讓小弟知道怎麼做 06/15 21:46