
2731: 最长重复子串
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 6 Solved: 4
[Submit][Status][Web Board]
Description
如果一个串x在S中出现,并且xx也在S中出现,那么x就叫做S的重复子串。
输入长度为n的串S,求它的最长重复子串。
输入长度为n的串S,求它的最长重复子串。
Input
首先给出字符串长度,其小于等于30000,接下来一个字符串
Output
如题
Sample Input
12
ABBABBCBCCCC
Sample Output
3
HINT
Source
题解:就是最长连续重复子串XX,先假设有两个点相距k(k为题目答案)分别为i,j且i,j分别为第一个X和第二个X中的一个点,
那么就会有一个R和L,R+L=k-1 && for z=1 to r do s[i+z]==s[j+z] && for z=1 to l do s[i-z]==s[j-z](这个自己画画图就可以知道了);
所以枚举k就可以了 详细分析可以看:http://wenku.baidu.com/link?url=RNgJuj25v47IZ37Nc6iqEsqwhARFmXEe2gKRQuOys574byP2ozEJaKq-qMvYlo482P1CoKnLlxz0lLHetYnent78SXzWEGYbF5uNZ14A2pW
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 31000
char s[maxn];
int net[maxn];
int fix,ans,n,l,r,j;
using namespace std;
int main()
{
scanf("%d",&n);
scanf("%s",s+);
for (int k=n/; k>=; k--)
{
int i=,j;
while (i+k<=n)
{
j=i+k;
l=;r=;
while (j+r<=n && s[i+r]==s[j+r]) r++;
while (i-l>= && s[i-l]==s[j-l]) l++;
if (r+l->=k)
{
printf("%d\n",k);
return ;
}
i=j;
}
} }