记录编号	213743	评测结果	AAAAAAAAAA
题目名称	[USACO Dec10]恐吓信	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2015-12-13 12:18:26	内存使用	11.74 MiB

#define MAXN 100010UL
#define MAXC 26UL
 
#include <cstdio>
#include <cstring>
 
int n,m,s[MAXN],t[MAXN];
 
struct SuffixAutomaton{
	int son[MAXN][MAXC],pre[MAXN],step[MAXN],last,cnt;
	inline void Push(int p){step[++cnt]=p;return;}
/*	inline void Print(){
		printf("cnt:%d\n",cnt);
		for(int i=0;i<=cnt;i++){
			printf("node  : %d \n",i);
			printf("	pre = > %d\n",pre[i]);
			for(int j=0;j<26;j++){
				if(!son[i][j]) continue;
				printf("	==> %c %d\n",j+'A',son[i][j]);
			}
			puts("");
		}
		return;
	}*/
	inline void Extend(int ch){
		Push(step[last]+1);
		int p=last,np=cnt,q,nq;
		for(;!son[p][ch];p=pre[p]) son[p][ch]=np;
		if(!p&&son[0][ch]==np) pre[np]=0;
		else{
			q=son[p][ch];
			if(step[q]==step[p]+1) pre[np]=q;
			else{
				Push(step[p]+1);
				nq=cnt;
				memcpy(son[nq],son[q],sizeof(son[q]));
				pre[nq]=pre[q];
				pre[q]=pre[np]=nq;
				for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq;
			}
		}
		last=np;
		return;
	}
	inline void Build(){
		for(int i=0;i<n;i++)
			Extend(s[i]);
		return;
	}
	inline int SP(int node,int ch,int &matched){
		while(node&&!son[node][ch]) node=pre[node],matched=step[node];
		if(son[node][ch]) matched++;
		return son[node][ch];
	}
	inline int Solve(){
		int Ans=1,len=0,matched=0,node=0;
		for(int i=0;i<m;i++){
			len++,node=SP(node,t[i],matched);
			if(matched<len) Ans++,i--,node=0,matched=0,len=0;
		}
		return Ans;
	}
}SAM;
 
inline void Read(int p[],int len){
	for(int i=0,c;i<len;){
		c=getchar();
		while(c<'A'||c>'Z') c=getchar();
		p[i++]=c-'A';
	}
	return;
}

int main(){
	freopen("thre_letter.in","r",stdin);
	freopen("thre_letter.out","w",stdout);
	scanf("%d%d",&n,&m);
	Read(s,n);Read(t,m);
	SAM.Build();
	//SAM.Print();
	printf("%d",SAM.Solve());
	return 0;
}