记录编号	371392	评测结果	AAAAAAAAAAT
题目名称	[USACO Dec10]恐吓信	最终得分	90
用户昵称	_Itachi	是否通过	未通过
代码语言	C++	运行时间	1.135 s
提交时间	2017-02-16 07:53:43	内存使用	1.94 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50005<<1,INF=0x3f3f3f3f;
int N,N1,r[maxn];char s[maxn];
int wa[maxn],wb[maxn],height[maxn],Rank[maxn],sa[maxn],cnt[maxn];
inline bool R_cmp(int *y,int a,int b,int len){
	return y[a]==y[b]&&y[a+len]==y[b+len];
}
void Rabit_sa(int n,int m){
	int *t,*x=wa,*y=wb,i,j,p;
	for(i=0;i<m;i++)cnt[i]=0;
	for(i=0;i<n;i++)cnt[x[i]=r[i]]++;
	for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
	for(i=n-1;~i;i--)sa[--cnt[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p){
		for(i=n-j,p=0;i<n;i++)y[p++]=i;
		for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<m;i++)cnt[i]=0;
		for(i=0;i<n;i++)cnt[x[y[i]]]++;
		for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
		for(i=n-1;~i;i--)sa[--cnt[x[y[i]]]]=y[i];
		for(t=x,x=y,y=t,i=1,x[sa[0]]=0,p=1;i<n;i++)
			x[sa[i]]=R_cmp(y,sa[i],sa[i-1],j)?p-1:p++;
	}
}
void Rabit_H(int n){
	int i,j,k=0;
	for(i=0;i<=n;i++)Rank[sa[i]]=i;
	for(i=0;i<=n;height[Rank[i++]]=k)
	for(k?k--:k,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
inline int Rabit_find(int pos){
	int i,k=INF,res=-INF;
	for(i=pos;i;i--){
		k=min(k,height[i]);
		if(sa[i-1]<N1){res=k;break;}
	}
	for(k=INF,i=pos+1;i<=N;i++){
		k=min(k,height[i]);
		if(sa[i]<N1){res=max(res,k);break;}
	}
	return res;
}
int main(){
	freopen("thre_letter.in","r",stdin);freopen("thre_letter.out","w",stdout);
	int n,m,i=0,k,ans=0;scanf("%d%d",&n,&m);N1=n;
	for(i=0;i<n;i++)do s[i]=getchar();while((s[i]<'a'||s[i]>'z')&&(s[i]<'A'||s[i]>'Z'));
	for(i=0;i<n;i++)r[i]=s[i];r[n]=1;
	for(i=0;i<m;i++)do s[i]=getchar();while((s[i]<'a'||s[i]>'z')&&(s[i]<'A'||s[i]>'Z'));
	for(i=0;i<m;i++)r[i+n+1]=s[i];r[N=n+m+1]=0;
	Rabit_sa(N+1,200),Rabit_H(N);
	for(i=n+1;i<N;)k=Rabit_find(Rank[i]),i+=k,ans++;
	printf("%d\n",ans);
}