本文共 1677 字，大约阅读时间需要 5 分钟。
好像是入门题的说 跑生成的串中不带给定字符串的个数ans 26^m-ans就是答案 dp[i][j]表示字符第i位在ac自动机上第j的节点的合法情况数 如果转移到的下一个节点是字符的结尾，就是非法的 转移dp[i][j]+=dp[i-1][j]; ps 节点编号从1开始
好像是入门题的说
跑生成的串中不带给定字符串的个数ans 26^m-ans就是答案
dp[i][j]表示字符第i位在ac自动机上第j的节点的合法情况数
如果转移到的下一个节点是字符的结尾，就是非法的
转移dp[i][j]+=dp[i-1][j];
ps 节点编号从1开始
#include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define sd(x) scanf("%d",&(x))#define sl(x) scanf("%lld",&(x))#define scs(s) scanf("%s",s)#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)#define lowbit(x) x&(-x)using namespace std;const int maxn=1e5+10;const int mod=10007;int dp[105][6005];int mub=1;int tree[maxn][26],cnt[maxn];int fail[maxn],End[maxn][26];char s[maxn];void Insert(){ int root=1; int l=strlen(s); rep(i,0,l-1) { int now=s[i]-'A'; if(!tree[root][now]) tree[root][now]=++mub; root=tree[root][now]; } cnt[root]++;}void getfail(){ for(int i=1;i<=mub;i++) fail[i]=1; queue q;fail[1]=0; q.push(1); while(!q.empty()) { int now=q.front(); q.pop(); rep(i,0,25) { int k=fail[now]; if(tree[now][i]) { q.push(tree[now][i]); fail[tree[now][i]]=k?tree[fail[now]][i]:1; cnt[tree[now][i]]|=cnt[fail[tree[now][i]]]; } else tree[now][i]=k?tree[fail[now]][i]:1; } }}void DP(int x){ rep(i,1,mub) { rep(j,0,25) { if(cnt[tree[i][j]]) continue; dp[x][tree[i][j]]+=dp[x-1][i]; dp[x][tree[i][j]]%=mod; } }}int main(){ int n,m,ans=1,tot=0; sd(n),sd(m); rep(i,1,n) scs(s),Insert(); getfail();dp[0][1]=1; rep(i,1,m) DP(i),ans=(ans*26)%mod; rep(i,1,mub) tot=(tot+dp[m][i])%mod; printf("%d\n",((ans-tot)%mod+mod)%mod); return 0;}
转载于:https://www.cnblogs.com/minun/p/11293960.html