→ suhorng:範例的意思是可以重複用嗎? 04/03 13:45
→ seedman:是的 子字串可以重複用 04/03 14:01
※ 編輯: seedman 來自: 98.208.56.49 (04/03 14:02)
→ shemale:suffix tree是不錯的解法，做得好的話，好像可以O(n) 04/03 22:00
問題是這樣的
給一堆字串
找出最常的可以用其他字串組合出來的字串
像是下面這組input
cat
cats
dog
hippopotamuses
rat
ratcatdogcat
ratcatdogcat可以由rat cat dog cat組成
他就是最長的可以由其他字串組合出來的字串
我現在的作法是很基本的
從最長的字串開始試
每次切一段子字串 長度從1慢慢開始往上加
用Binary search在另外一堆排好的字串裡面找看有沒有出現過
有的話就切下一段子字串去比對
沒有的話就增加長度
但是這樣很慢
字串相關的我想到的只有suffix tree
可是看不太出來和這題的關係 （每個字串都建一個？）
或是這題根本不是這樣解呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 98.208.56.49