记录编号	286068	评测结果	AAAAAAAAAA
题目名称	[USACO Dec10]恐吓信	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2016-07-26 13:37:08	内存使用	11.00 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=100010;
int read(){
	char c=getchar();
	while(c<'A'||c>'Z')
		c=getchar();
	return c-'A';	
}
int fa[maxn],len[maxn];
int lst,cnt,ch[maxn][26];
struct SAM{
	SAM(){cnt=lst=1;}
	void Insert(int c){
		int p=lst,np=lst=++cnt;len[np]=len[p]+1;
		while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
		if(!p)fa[np]=1;
		else{
			int q=ch[p][c],nq;
			if(len[q]==len[p]+1)
				fa[np]=q;
			else{
				nq=++cnt;len[nq]=len[p]+1;
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];
			}	
		}
	}
}sam;
int n,m;
int main(){
	freopen("thre_letter.in","r",stdin);
	freopen("thre_letter.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		sam.Insert(read());
	int p=1,ans=0;
	for(int i=1;i<=m;i++){
		int c=read();
		if(!ch[p][c])
			{ans+=1;p=1;}
		p=ch[p][c];
	}	
	printf("%d\n",ans+1);
	return 0;
}