103北市賽 5.加密金鑰 (Key)

想法：

觀察發現，若存在長度=m的解，那麼對於x<=m均有解。
由這項單調性，可以二分搜長度，
再枚舉這個長度的子字串是否相同即可。

實作上要使用string hash的技巧，
請諸位自己多背一些質數吧^^。

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxn 100005
#define ll long long
using namespace std;
const int p=0x7abcdef7;
const int q=0x7deface1;
char ar[maxn];
int _s[maxn];
int _p[maxn];
int pow(int a,int b)
{
	if(_p[b])
		return _p[b];
	if(b==0)
		return _p[0]=1;
	ll tmp=pow(a,b/2);
	tmp*=tmp;
	tmp%=q;
	if(b&1)
		return _p[b]=(tmp*a)%q;
	return _p[b]=tmp;
}
void build()
{
	ll tmp=_s[0]=ar[0];
	for(int i=1;ar[i];i++)
	{
		tmp*=p;
		tmp+=ar[i];
		tmp%=q;
		_s[i]=tmp;
	}
}
int get(int l,int r)
{
	ll ret=_s[r];
	if(!l)
		return ret;
	ll tmp=pow(p,r-l+1);
	tmp*=_s[l-1];
	tmp%=q;
	ret-=tmp;
	return ((ret%q)+q)%q;
}
vector<bool> fnd(q,false);
vector<int> pos;
bool chk(int len)
{
	while(pos.size())
	{
		fnd[*pos.rbegin()]=false;
		pos.pop_back();
	}
	for(int i=0;ar[i+len-1];i++)
	{
		int val=get(i,i+len-1);
		if(fnd[val])
			return true;
		else
		{
			pos.push_back(val);
			fnd[val]=true;
		}
	}
}
void print(int len)
{
	while(pos.size())
	{
		fnd[*pos.rbegin()]=false;
		pos.pop_back();
	}
	for(int i=0;ar[i+len-1];i++)
	{
		int val=get(i,i+len-1);
		if(fnd[val])
		{
			for(int j=0;j<len;j++)
				printf("%c",ar[i+j]);
			puts("");
			return;
		}
		else
		{
			pos.push_back(val);
			fnd[val]=true;
		}
	}
}
int main()
{
	scanf("%s",ar);
	build();
	int low=1,high=strlen(ar)-1,mid;
	while(high>low)//ans=low-1
	{
		mid=(low+high)/2;
		if(chk(mid))
			low=mid+1;
		else
			high=mid;
	}
	print(low-1);
	return 0;
}