TJOI2018碱基序列

思考PAM上暴力DP

确实也可以，但是复杂了许多，不要想多了！

kmp匹配一遍每个串之后直接DP（这样还保险些，毕竟不知道序列总长度）

时间复杂度\(O(|S|ka)\)

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=1e4+4,mod=1e9+7;
int k,kk,n,m,f[2][N],fail[N];
char s[N],c[N];
int main(){
	k=read();
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=0;i<=n;i++)f[0][i]=1;
	int cur=1,pre=0;
	while(k--){
		memset(f[cur],0,sizeof(f[cur]));
		kk=read();
		while(kk--){
			scanf("%s",c+1);
			m=strlen(c+1);
			for(int i=2,j=0;i<=m;i++){
				while(j&&c[j+1]!=c[i])j=fail[j];
				if(c[j+1]==c[i])j++;
				fail[i]=j;
			}
			for(int i=1,j=0;i<=n;i++){
				while(j&&c[j+1]!=s[i])j=fail[j];
				if(c[j+1]==s[i])j++;
				if(j==m)f[cur][i]=(f[cur][i]+f[pre][i-m])%mod;
			}
		}
		cur^=1;pre^=1;
	}
	int ans=0;
	for(int i=0;i<=n;i++)ans=(ans+f[pre][i])%mod;
	cout<<ans;
	return (0-0);
}

TJOI2018碱基序列

原文：https://www.cnblogs.com/aurora2004/p/12622810.html