D : DS串应用—最长重复子串

D : DS串应用—最长重复子串

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 38     Solved: 16

Description

求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。

Input

测试次数t

t个测试串

Output

对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.

Sample Input

3
abcaefabcabc
szu0123szu
szuabcefg

Sample Output

4
3
-1

注：这里有个地方得注意，就是他最大重复子串是不重叠的。方法利用就是KMP中的一个计算next[]数组的函数的计算前后缀重复度的特性。
分两种情况判定：不重叠：k*2<=i和重叠：i/(i-k)>=2，第一个很容易理解，第二个，i/(i-k)可以求重复次数是多少
如果超过2，比如是5那么就取两个重复串，所以就有了这个式子：（i-k）单串长度 乘重复次数/2这样取的子串长度就肯定不重叠
ac代码如下：

#include<iostream>
using namespace std;
int Get_next(string a)
{
    int i=0,k=-1;
    int len=a.length(),maxn=0;
    int *nextt=new int[a.length()+1];
    nextt[0]=-1;
    while(i<len)
    {
        if(k==-1||a[i]==a[k])
        {
            i++,k++;
            nextt[i]=k;
            if(k*2<=i)maxn=max(maxn,k);
            if(i/(i-k)>=2)maxn=max(maxn,(i-k)*(i/(i-k)/2));
        }
        else k=nextt[k];
    }
    return maxn;
}
int get_maxnum(string a)
{
    int len=a.length(),maxn=0;
    for(int i=0;i<len;i++)
    {
        maxn=max(maxn,Get_next(a.substr(i,len)));
    }
    return maxn;
}
int main()
{
    string a;
    int n;
    cin>>n;
    while(n--)
    {
    cin>>a;
    int num=get_maxnum(a);
    if(!num)cout<<-1<<endl;
    else cout<<num<<endl;
    }
    return 0;
}