[問題] Longest Concatenate String
問題是這樣的
給一堆字串
找出最常的可以用其他字串組合出來的字串
像是下面這組input
cat
cats
dog
hippopotamuses
rat
ratcatdogcat
ratcatdogcat可以由rat cat dog cat組成
他就是最長的可以由其他字串組合出來的字串
我現在的作法是很基本的
從最長的字串開始試
每次切一段子字串 長度從1慢慢開始往上加
用Binary search在另外一堆排好的字串裡面找看有沒有出現過
有的話就切下一段子字串去比對
沒有的話就增加長度
但是這樣很慢
字串相關的我想到的只有suffix tree
可是看不太出來和這題的關係 （每個字串都建一個？）
或是這題根本不是這樣解呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 98.208.56.49
→
04/03 13:45, , 1F
04/03 13:45, 1F
→
04/03 14:01, , 2F
04/03 14:01, 2F
※ 編輯: seedman 來自: 98.208.56.49 (04/03 14:02)
→
04/03 22:00, , 3F
04/03 22:00, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：