10.15 晚上考试总结

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=1e6+5;
const int p=13331;
int pw[N],hs[N];
int lens;
int get_hash(int l,int r)
{
	return hs[r]-hs[l-1]*pw[r-l+1];
}
map<int,int> v;
bool check(int x)
{
	v.clear();
	for(int i=1;i<=lens-x+1;i++)v[get_hash(i,i+x-1)]++;
	for(int i=1;i<=lens-x+1;i++)
	{
		if(v[get_hash(i,i+x-1)]==1)return 1;//就是这里
	}
	return 0;
}
signed main()
{
	string s;
	cin>>s;
	lens=s.size();
	s='#'+s;
	pw[0]=1;
	for(int i=1;i<=lens;i++)
	{
		hs[i]=hs[i-1]*p+(s[i]-'0');
		pw[i]=pw[i-1]*p;
	}
	int l=1,r=lens;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	v.clear();
	for(int i=1;i<=lens-l+1;i++)v[get_hash(i,i+l-1)]++;
	for(int i=1;i<=lens-l+1;i++)
	{
		if(v[get_hash(i,i+l-1)]==1)
		{
			cout<<s.substr(i,l);
			return 0;
		}
	}
	return 0;
}