作者DJWS (...)
看板Prob_Solve
标题Re: [问题] Longest Concatenate String
时间Tue Apr 3 14:30:29 2012
我的想法：
一、穷举每一个字串作为母字串，看看哪个是对的。
二、针对一个母字串，建立 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)
1F：推 seedman:aspera面试问题 我回答的就是我第一篇po的 04/03 14:44
2F：推 seedman:子字串可以重复用多次 这样好像和2冲突？ 04/03 14:53
3F：推 suhorng:2也可以做成对每个可能的[a,b]都标 比如写KMP一样可以在线 04/03 15:10
4F：→ suhorng:性时间内完成 04/03 15:10
5F：→ DJWS:刚刚想到 改用Aho-Corasick的话就可以线性时间做完了 04/03 16:31
6F：→ DJWS:另外 细想了之後 我不知道怎麽用suffix tree找到匹配位置XD 04/03 16:33
7F：推 AstralBrain:关於步骤二, 如果一个子字串找到很多组[a,b] 04/03 20:03
8F：→ AstralBrain:这个图的大小会不会变成O(S^2) ? 04/03 20:04
9F：→ DJWS:楼上你说的对! 我没有想到... 04/03 21:35
10F：推 seedman:用Aho-Corasick的话要怎麽避开该字串本身呢？ 04/04 04:34
11F：→ DJWS:不用避开呀~ 当匹配到原本字串的时候 忽略他就行了 04/04 08:58
12F：→ DJWS:另外Aho-Corasick可以避免掉AstralBrain版友说的O(S^2)情况 04/04 08:59
13F：→ DJWS:开一条母字串一样长的bool阵列 母字串比对过程中 随时标记 04/04 09:02
14F：→ DJWS:从第一个字元可以走到哪些字元 走访suffix link计算[a,b]的 04/04 09:03
15F：→ DJWS:过程中 一旦发现a是走得到的节点 就可以立即中止计算[a,b] 04/04 09:04
16F：推 seedman:咦？这个演算法不是树建完後 每次就直接拿字串去查 04/04 16:01
17F：→ seedman:然後看字串拜访的顺序得知是由哪些子字串组成的吗？ 04/04 16:02
18F：→ seedman:然後他是可以往下走就往下走 不然就走failure link? 04/04 16:02
19F：→ seedman:所以有字典中有包含要查询的字串会变成输出自己？ 04/04 16:03
20F：→ DJWS:如果一次中很多个pattern 就得走suffix link找到所有pattern 04/04 17:49
21F：→ DJWS:如果树上已经有原本字串 当然就会中原本字串 此时忽略即可 04/04 17:50
22F：推 seedman:感觉我好像运作方式没搞懂@@ 大概要实作才会了解 谢谢回应 04/05 11:11
23F：→ DJWS:事实上我也没有懂得很透彻... 如果造成困扰 很不好意思~ 04/05 16:17