作者seedman (cc)
站内Prob_Solve
标题[问题] Longest Concatenate String
时间Tue Apr 3 13:29:06 2012
问题是这样的
给一堆字串
找出最常的可以用其他字串组合出来的字串
像是下面这组input
cat
cats
dog
hippopotamuses
rat
ratcatdogcat
ratcatdogcat可以由rat cat dog cat组成
他就是最长的可以由其他字串组合出来的字串
我现在的作法是很基本的
从最长的字串开始试
每次切一段子字串 长度从1慢慢开始往上加
用Binary search在另外一堆排好的字串里面找看有没有出现过
有的话就切下一段子字串去比对
没有的话就增加长度
但是这样很慢
字串相关的我想到的只有suffix tree
可是看不太出来和这题的关系 （每个字串都建一个？）
或是这题根本不是这样解呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 98.208.56.49
1F：→ suhorng:范例的意思是可以重复用吗? 04/03 13:45
2F：→ seedman:是的 子字串可以重复用 04/03 14:01
※ 编辑: seedman 来自: 98.208.56.49 (04/03 14:02)
3F：→ shemale:suffix tree是不错的解法，做得好的话，好像可以O(n) 04/03 22:00