科林明伦杯

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;
}

发表评论