HDOJ 5763 Another Meaning

很少做这种带有综合性质的题啊，kmp+基本线性dp都写不了

先说说这个题的基本思路：首先是个字符串匹配的题，最经典的kmp算法可以在O（N）内时间解决

然后就是，如何根据kmp的匹配值进行计算，答案是dp

如果当前位置未匹配，dp【i】=dp【i-1】

如果当前位置匹配，那么dp【i】=dp【i-1】+dp【i-m】，其中m是子串的串长

套上两个模板就能AC的一个简单题

void kmp_pre(char x[],int m,int Next[]){
	int i,j,k;
	j=Next[0]=-1;
	i=0;
	while(i<m){
		while(j!=-1&&x[i]!=x[j]) j=Next[j];
		Next[++i]=++j;
	}
}

int Next[1001000];
void KMP_Count(char x[],int m,char y[],int n){
	int i,j,k;
	int ans=0;
	kmp_pre(x,m,Next);
	i=j=k=0;
	while(i<n){
		while(j!=-1&&x[j]!=y[i]) j=Next[j];
		i++;j++;k++;
		if (j>=m){
			ok[k]=true;
			//printf("%d ",k);
			j=Next[j];
		}
	}
}

int main(){
	//input;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%s%s",y,x);
		memset(ok,false,sizeof(ok));
		memset(dp,0,sizeof(dp));
		printf("Case #%d: ",Case);
		int leny=strlen(y);
		int lenx=strlen(x);
		KMP_Count(x,lenx,y,leny);
		//for(int i=0;i<=leny;i++)
		//	if (ok[i]) printf("%d ",i);
		dp[0]=1;
		for(int i=1;i<=leny;i++)
			if (ok[i]) dp[i]=(dp[i-1]+dp[i-lenx])%mod;
			else dp[i]=dp[i-1];
		printf("%I64d\n",dp[leny]);
	}
	return 0;
}