J 最大值
链接:https://ac.nowcoder.com/acm/contest/5758/J
来源:牛客网
题目描述
有一个字符串s,对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。
请问给出一个字符串他的ac串最大长度为多少
输入描述:
输入数据第一行是t,表示数据的组数,接下来每组数据输入一个字符串s
(t<=10,s<=1e5)
输出描述:
输出最大长度
输入
2 aaaaa abacc
输出
4 1
说明
aaaab的ac串是aaa(2:4)
acac的ac串是ac(3:4)
#include <iostream>
#include <string>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string s,sub;
cin>>s;
int len=s.length(),l=0,r=len-1,mid;
while(l<=r)
{
mid=(l+r)/2;
sub=s.substr(0,mid);
if (s.find(sub,1)!=-1)
{
l=mid+1;
mid=(l+r)/2;
}
else
{
r=mid-1;
mid=(l+r)/2;
}
}
sub=s.substr(0,mid);
printf("%d\n",sub.length());
}
return 0;
}