PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

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