[問題] Longest Concatenate String
看板Prob_Solve (計算數學 Problem Solving)作者seedman (cc)時間12年前 (2012/04/03 13:29)推噓0(0推 0噓 3→)留言3則, 3人參與討論串1/2 (看更多)
問題是這樣的
給一堆字串
找出最常的可以用其他字串組合出來的字串
像是下面這組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 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
