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

[walker2009 (不害怕。不後悔)]

抱歉 @@ 因為沒有演算法的專版,

之前在此版常受到大家幫忙

所以還是來最常逛的 C/C++ 版來發問了

===================================

想請問一個演算法相關的問題


假設我有一段 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)


給個例子

         1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
如果 T = X  -  -  -  X  -  X  X  -  -  X  X  -  -  -

     P = X  -  -  X

 ( - 表示任意非 X 字元)

我們求出來的解是 1, 2, 4, 5, 7, 8, 9, 11, 12 這幾個位置

因為當 P shift 到這幾個位置時, 都會有 X 對上 X 的情況


      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  T = X  -  -  -  X  -  X  X  -  -  X  X  -  -  -

1 P = X  -  -  X
2        X  -  -  X
4              X  -  -  X
5                 X  -  -  X
7                       X  -  -  X
8                          X  -  -  X
9                             X  -  -  X
11                                  X  -  -  X
12                                     X  -  -  X



當然最暴力的做法的時間複雜度會是 O(A*B)

可是因為我們知道, 這些位置最多就是 n 個

A*B 的作法會重複算到一些位置



請問這個問題有辦法在 O(n + m) 裡面解出來嗎??

或是拜託有經驗的大大可以提供相關的關鍵字讓我去搜尋~

想 google 或爬文都不知道該如何下手 Orz


謝謝^^

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.217
→ walker2009:題外話~ 覺得如果 ptt 多個'演算法'版還不錯耶 ~_~
→ james732:Prob_Solve這個板應該可以說是演算法板  雖然有點冷清 XD
→ walker2009:XD 我轉過去試試看~ 謝謝
推 xatier:請左轉Prob_Solve囉~
※ walker2009:轉錄至看板 Prob_Solve                                06/08 12:53
→ walker2009:囧~ 那邊人氣是 0 ...Q_Q
→ tkcn:樓上快回那板回我推文呀~~XD
→ walker2009:我回了XD~ 題目有點不清~ 我修改一下~
※ 編輯: walker2009      來自: 140.114.78.217       (06/08 13:01)
推 singlovesong:KMP?
→ tkcn:KMP 不行，題目不是那意思
→ angleevil:根據你後來的意思,我用了一個還是暴力法.但是不會到A*B
→ angleevil:http://pastie.org/2036041
→ walker2009:那會是多少呢@@? 能稍微解釋一下嗎~
→ walker2009:我瞧瞧~ 3q :D
→ walker2009:唔...是我看錯嗎, angle大的解法好像跟要求不一樣(遮臉
※ 編輯: walker2009      來自: 140.114.78.217       (06/08 13:42)
→ walker2009:題意不清 ~_~ 我又修改了一次
→ walker2009:看來定義題目也是門功夫 囧
推 chubiei:感覺不太可能 因為worst case就是A*B
→ angleevil:1.size_t strcspn(const char*, const char*)
→ angleevil:2.string::find_first_of
→ angleevil:http://0rz.tw/RR6cu 第一個方法的參考網址
→ angleevil:雖然都是暴力法,但是strcspn是組語寫出來的.會快點
→ walker2009:給chu大~ 的確最壞情況是 A*B 都完全沒有重複到的位置
→ walker2009:可是 text 長度就是 n, 所以最多也只有 n 個這種位置~
→ walker2009:因此無論如何位置總數都會被 O(n) bound 住
→ angleevil:~"~這次應該沒給錯了吧,再錯,我退出Orz
→ walker2009:嗯嗯, 都知道了
→ walker2009:XD
→ walker2009:angle大英文不好(筆記)
→ angleevil:Orz有沒有幫到才是重點
→ walker2009:angle大弄錯題意了啦XD
→ angleevil:Orz看來這篇非我能力所及,交給其他人吧
→ walker2009:我加個例子@@
※ 編輯: walker2009      來自: 140.114.78.217       (06/08 14:46)
推 michael0728n:如果算出每兩個X對到時 字串的head會在哪裡
→ michael0728n:不   還是A*B  不要理我XD
→ walker2009:XD 先算出來再移除重複的就 O(A*B) 了
※ 編輯: walker2009      來自: 140.114.78.217       (06/08 14:59)
推 Ebergies:基本上雖然答案只有 n 個但是你要確定每個答案是對的要 m
→ walker2009:我只有 O(nlogm) 的解法 Q_Q~ 想知道這問題有沒有人做
→ angleevil:walker2009可以給我那解法讓我參考一下
→ walker2009:把不是'X'的 characters coding 成 0, 'X' coding 成 1
→ walker2009:將 text 和 pattern 都轉成 binary sequence 後
→ walker2009:我們要求的就變成在每個長度為 m 的 substring 中
→ walker2009:有哪一段是有 1 對到 1 的
→ walker2009:總共有 n 段 substring, 我們對這 n 段做
→ walker2009:boolean convolution, 時間為 O(nlogm)
→ walker2009:boolean convolution出來的結果>0 表示這位置有1對到1
推 Ebergies:logm?
→ walker2009:嗯嗯~ 目前 boolean convolution 最快就做到 nlogm
→ Ebergies:是使用 randomized algorithm 嗎? 對這東西不熟
→ Ebergies:有沒有相關的資訊呢, 蠻有興趣的
→ walker2009:噗~ 其實我也沒有很熟, google convolution 的話應該會
→ walker2009:有蠻多結果~ nlogm 的
→ angleevil:因為覺得轉化成bool也是要時間,所以我用位元運算去檢查
→ walker2009:我只有把它當工具用 ~_~ 要 implement 還得再看熟點
→ angleevil:http://pastie.org/2036580,我也很好奇你用哪種tool
推 Ebergies:樓上那個用 == 比不就好了, 比較快吧...
→ Ebergies:我查 boolean convolution 第一篇是跟演算法無關的
→ Ebergies:之後有一個 PPT 只有講結果 = ="
→ angleevil:我是根據-->有哪一段是有 1 對到 1,然後覺得用^就可以
→ walker2009:人家玩演算法只會紙上談兵咩~ 幹麻這樣~ (扭
→ angleevil:~"~walker2009 可以把你找到文章po出來嘛? 我也想研究
→ walker2009:http://tinyurl.com/3g7tjhj 這篇看完大概就差不多了吧
→ walker2009:詳情請 google 'fast convolution' 搭配 FFT 服用
→ walker2009:我剛不知道按到什麼鍵文章前有個大 D 符號 @@
→ walker2009:請問要怎麼刪除 @@?
→ walker2009:刪除了o.o
推 Ebergies:原來重點是用 FFT 做 convolution, 都忘了有這東西了
→ angleevil:QQ
推 tropical72:好奇一問, 所以,walker2009 已於 O(n+m) 完成 ?
→ Ebergies:我個人認為頂多 O(nlogm) 吧, 另外網路上有另一篇類似的
→ angleevil:看完walker2009找到資料,其實也不一定用0 or 1表示
→ angleevil:只是目前我還困在overlap matching algorithm那章
→ angleevil:有些例子的表示還有點想不透,也可以用Suffix Array +
→ angleevil:不好意思上面那個當沒講,~"~看演算法看到頭昏
→ walker2009:Ebergies大~ 可以告訴我那篇類似的篇文或關鍵字嗎@@?
推 LPH66:如果是 FFT 的話應該是 O(nlogm) 沒錯了
→ LPH66:話說回來這問題等同於求 {p-q|p \in P,q \in Q}
→ LPH66:其中 P \subseteq {1,2,3,...n}  Q \subseteq {1,2,3,...,m}
→ LPH66:感覺沒有比 FFT 更好的做法的樣子...
→ angleevil:後來想想,除了只比對頭尾的字元,大概就只有nlogm
推 LPH66:只比頭尾就是 m=2 啊  把它當常數吃掉當然用什麼都是 O(n)..
→ angleevil:QQ
推 Ebergies:http://www.iis.sinica.edu.tw/~hil/random/team3.ppt
推 angleevil:Ebergies good!研究中