作者DJWS (...)
看板Prob_Solve
標題Re: [問題] Longest Concatenate String
時間Tue Apr 3 14:30:29 2012
我的想法：
一、窮舉每一個字串作為母字串，看看哪個是對的。
二、針對一個母字串，建立 suffix tree。
其餘字串拿來做字串匹配，找到在母字串的匹配位置[a,b]，
三、引入圖論。母字串的每一個字元都是一個節點，
步驟二每一個匹配位置[a,b]，都是一條邊 a -> b+1。
問題變成：第一個字元是否有路通往最後一個字元'\0'。
這個用DFS BFS找一下就有答案。
時間複雜度 O(NS)
步驟二與三都是線性時間 O(S) S是總字元數
步驟一執行N次 N是總字串數
不知道能不能更快...
另外想請教此題的來源～
※ 引述《seedman (cc)》之銘言：
: 問題是這樣的
: 給一堆字串
: 找出最常的可以用其他字串組合出來的字串
: 像是下面這組input
: cat
: cats
: dog
: hippopotamuses
: rat
: ratcatdogcat
: ratcatdogcat可以由rat cat dog cat組成
: 他就是最長的可以由其他字串組合出來的字串
: 我現在的作法是很基本的
: 從最長的字串開始試
: 每次切一段子字串 長度從1慢慢開始往上加
: 用Binary search在另外一堆排好的字串裡面找看有沒有出現過
: 有的話就切下一段子字串去比對
: 沒有的話就增加長度
: 但是這樣很慢
: 字串相關的我想到的只有suffix tree
: 可是看不太出來和這題的關係 （每個字串都建一個？）
: 或是這題根本不是這樣解呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.126.94
※ 編輯: DJWS 來自: 61.230.126.94 (04/03 14:42)
1F：推 seedman:aspera面試問題 我回答的就是我第一篇po的 04/03 14:44
2F：推 seedman:子字串可以重複用多次 這樣好像和2衝突？ 04/03 14:53
3F：推 suhorng:2也可以做成對每個可能的[a,b]都標 比如寫KMP一樣可以在線 04/03 15:10
4F：→ suhorng:性時間內完成 04/03 15:10
5F：→ DJWS:剛剛想到 改用Aho-Corasick的話就可以線性時間做完了 04/03 16:31
6F：→ DJWS:另外 細想了之後 我不知道怎麼用suffix tree找到匹配位置XD 04/03 16:33
7F：推 AstralBrain:關於步驟二, 如果一個子字串找到很多組[a,b] 04/03 20:03
8F：→ AstralBrain:這個圖的大小會不會變成O(S^2) ? 04/03 20:04
9F：→ DJWS:樓上你說的對! 我沒有想到... 04/03 21:35
10F：推 seedman:用Aho-Corasick的話要怎麼避開該字串本身呢？ 04/04 04:34
11F：→ DJWS:不用避開呀~ 當匹配到原本字串的時候 忽略他就行了 04/04 08:58
12F：→ DJWS:另外Aho-Corasick可以避免掉AstralBrain版友說的O(S^2)情況 04/04 08:59
13F：→ DJWS:開一條母字串一樣長的bool陣列 母字串比對過程中 隨時標記 04/04 09:02
14F：→ DJWS:從第一個字元可以走到哪些字元 走訪suffix link計算[a,b]的 04/04 09:03
15F：→ DJWS:過程中 一旦發現a是走得到的節點 就可以立即中止計算[a,b] 04/04 09:04
16F：推 seedman:咦？這個演算法不是樹建完後 每次就直接拿字串去查 04/04 16:01
17F：→ seedman:然後看字串拜訪的順序得知是由哪些子字串組成的嗎？ 04/04 16:02
18F：→ seedman:然後他是可以往下走就往下走 不然就走failure link? 04/04 16:02
19F：→ seedman:所以有字典中有包含要查詢的字串會變成輸出自己？ 04/04 16:03
20F：→ DJWS:如果一次中很多個pattern 就得走suffix link找到所有pattern 04/04 17:49
21F：→ DJWS:如果樹上已經有原本字串 當然就會中原本字串 此時忽略即可 04/04 17:50
22F：推 seedman:感覺我好像運作方式沒搞懂@@ 大概要實作才會了解 謝謝回應 04/05 11:11
23F：→ DJWS:事實上我也沒有懂得很透徹... 如果造成困擾 很不好意思~ 04/05 16:17