月度归档： 2012年4月

问题概述：

输入一个字符串，如何求最长重复出现（至少出现2次）的子字符串呢？比如输入ttabcftrgabcd，输出结果为abc，canffcancd，输出结果为can？

http://hi.baidu.com/zhang_daxia/blog/item/c9ea38f24e3bf39eb801a040.html中间给了一个后缀树的方法，但是其算法复杂度是O(n^2*log(n))（因为中间的qsort中间的strcmp的复杂度也是O(n)），实际上这样的题目最多O(n^2)就可以了，如果借鉴KMP的方法则可以达到O(mn)，其中m是最长重复的子字符串。下面是我的算法，其实很简单，类似拉链那样逐位比较就行了，注意字符串不能重叠（比如ababa，则最大重复则为ab而不是aba）。因为对KMP不熟悉，所以就没有放上O(mn)的算法。。

C++语言: 高亮代码由发芽网提供

#include <iostream>

#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define LEN 1000
void work(char *s)
{
    int i,j;
    int len=strlen(s);
    int al,ar,bl,br;//left right of the simistring
    int maxlen = 0;
    char maxstr[LEN];
    for(i=0;i<len;i++)
    {
        al = 0; ar = 0; bl = i; br = i;
        for(j=i;j<=len;j++)
        {
            if(ar-al>maxlen)
            {
                maxlen = ar-al;
                memset(maxstr,0,LEN);
                strncpy(maxstr,&s[al],ar-al);
            }
            if(j==len) break;
            if(s[j-i]==s[j])
            {
                ar++;
                br++;
                if(bl>=ar)    continue;
            }
            bl=br=j+1;
            al=ar=j+1-i;            
        }
    }
    cout << maxlen << " " <<  maxstr << endl;
}
int main()
{
    char s[LEN];
    while(cin>>s)
    {
        work(s);
    }
    return 0;
}