J-最大值“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)
最大值
https://ac.nowcoder.com/acm/contest/5758/J
题意：
有一个字符串s，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。
请问给出一个字符串他的ac串最大长度为多少？
题解：
他这个ac串是非前缀子串与前缀相同，就像abab 他是最长ac串是ab，非前缀子串是第一个起点不是原字符串的起点，就是如果表上号的话就是
abab 1234
ac串开始点不能是1，且ac串与原串从1开始对应相等。就从3开始走到4就是ab然后最长就是2。
知道这个我们可以知道他就是KMP，可惜我不会。哈哈~
官方题解正好就KMP
看就自取吧（嘻嘻嘻）。
另一种；
直接二分找也可以，因为长度是单调的，他可以是n就肯定可以是n-1之后.....
所以我们就可以利用ac串的长度来写的二分的算法，二分少不了判断，判断条件是，先截取原字符串0-len的字符串，再用非前缀长度为len的字符串与它比较，相等就是len这个长度可以做到，不相等判断下一个，如果到最后还没有相等的，就是len不行。
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
bool check(ll len){
string temp=str.substr(0,len);
for(int i=1;i+len<=n;i++)
{
string h=str.substr(i,len);
if(h==temp) return 1;
}return 0;
}
#define read read()
int main(){
t=read;
while(t--){
cin>>str;
n=str.size();
l=0;
r=n;
sum=0;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid)){
sum=mid;
l=mid+1;
}else {
r=mid-1;
}
}
cout<<sum<<endl;
}
return 0;
}
