Re: [問題] Longest Concatenate String

[DJWS (...)]

我的想法：

一、窮舉每一個字串作為母字串，看看哪個是對的。

二、針對一個母字串，建立 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)
推 seedman:aspera面試問題 我回答的就是我第一篇po的
推 seedman:子字串可以重複用多次 這樣好像和2衝突？
推 suhorng:2也可以做成對每個可能的[a,b]都標 比如寫KMP一樣可以在線
→ suhorng:性時間內完成
→ DJWS:剛剛想到  改用Aho-Corasick的話就可以線性時間做完了
→ DJWS:另外  細想了之後  我不知道怎麼用suffix tree找到匹配位置XD
推 AstralBrain:關於步驟二, 如果一個子字串找到很多組[a,b]
→ AstralBrain:這個圖的大小會不會變成O(S^2) ?
→ DJWS:樓上你說的對! 我沒有想到...
推 seedman:用Aho-Corasick的話要怎麼避開該字串本身呢？
→ DJWS:不用避開呀~ 當匹配到原本字串的時候  忽略他就行了
→ DJWS:另外Aho-Corasick可以避免掉AstralBrain版友說的O(S^2)情況
→ DJWS:開一條母字串一樣長的bool陣列  母字串比對過程中  隨時標記
→ DJWS:從第一個字元可以走到哪些字元  走訪suffix link計算[a,b]的
→ DJWS:過程中  一旦發現a是走得到的節點  就可以立即中止計算[a,b]
推 seedman:咦？這個演算法不是樹建完後 每次就直接拿字串去查
→ seedman:然後看字串拜訪的順序得知是由哪些子字串組成的嗎？
→ seedman:然後他是可以往下走就往下走 不然就走failure link?
→ seedman:所以有字典中有包含要查詢的字串會變成輸出自己？
→ DJWS:如果一次中很多個pattern  就得走suffix link找到所有pattern
→ DJWS:如果樹上已經有原本字串  當然就會中原本字串  此時忽略即可
推 seedman:感覺我好像運作方式沒搞懂@@ 大概要實作才會了解 謝謝回應
→ DJWS:事實上我也沒有懂得很透徹...  如果造成困擾  很不好意思~