Ananimous(3) 求m个字符串中重复n次字符串的最长的那个

一直听说过后缀树和后缀数组，但没机会用，你这个方法想法上确实巧，非常值得借鉴。不过对于这道题我有点 ...
darksteel 发表于 2011-4-21 02:41

   恩，是我没说清楚，对于拼接可以这样解决，每个字符串后面加入结束符号，就是输入字串中不可能出现的，例如
输入是S1,S2,S3,
你可以用S1#1S2#2S3#3来连起来，这样基本上就能解决问题了。 如果要求刚好n次的话可以对每个i多做1次判断满足(i, i+n-1)最大，并且不等于(i, i+n)的就可以了

回复 11# danielgao
这样应该就没问题了。以前从未对后缀树组的强大有感性认识，原来可以这么用，确实收获不少。
如果非得说还有什么concern的话，那就是拼接起来之后再建后缀数组，感觉上会有一些操作不是有效的，不知这样说对不对，就是会有因为拼接而多加出来的操作。不过由于数据结构本身的强大，应该能做到和trie的方法等同或更好。如果这题要求的是一个长串中出现n次的最长的子串，这个方法就再合适不过了。
   

想了半天，居然忘记有后缀数组这个神器了。。

后缀数组 + LCP ， 如果LCP用线段树, 一遍扫过去求所有的LCP[l,l+m)   O(nlg(N))