Re: [問題] Longest Concatenate String
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間12年前 (2012/04/03 14:30)推噓7(7推 0噓 16→)留言23則, 4人參與討論串2/2 (看更多)
我的想法：
一、窮舉每一個字串作為母字串，看看哪個是對的。
二、針對一個母字串，建立 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)
推
04/03 14:44, , 1F
04/03 14:44, 1F
推
04/03 14:53, , 2F
04/03 14:53, 2F
推
04/03 15:10, , 3F
04/03 15:10, 3F
→
04/03 15:10, , 4F
04/03 15:10, 4F
→
04/03 16:31, , 5F
04/03 16:31, 5F
→
04/03 16:33, , 6F
04/03 16:33, 6F
推
04/03 20:03, , 7F
04/03 20:03, 7F
→
04/03 20:04, , 8F
04/03 20:04, 8F
→
04/03 21:35, , 9F
04/03 21:35, 9F
推
04/04 04:34, , 10F
04/04 04:34, 10F
→
04/04 08:58, , 11F
04/04 08:58, 11F
→
04/04 08:59, , 12F
04/04 08:59, 12F
→
04/04 09:02, , 13F
04/04 09:02, 13F
→
04/04 09:03, , 14F
04/04 09:03, 14F
→
04/04 09:04, , 15F
04/04 09:04, 15F
推
04/04 16:01, , 16F
04/04 16:01, 16F
→
04/04 16:02, , 17F
04/04 16:02, 17F
→
04/04 16:02, , 18F
04/04 16:02, 18F
→
04/04 16:03, , 19F
04/04 16:03, 19F
→
04/04 17:49, , 20F
04/04 17:49, 20F
→
04/04 17:50, , 21F
04/04 17:50, 21F
推
04/05 11:11, , 22F
04/05 11:11, 22F
→
04/05 16:17, , 23F
04/05 16:17, 23F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
