[JSOI2007]文本生成器

Link

问题描述

对于一个长度为 \(n\) 的串 \(S\) ，有多少可能情况的串 \(S\) 使得 \(S\) 的子串中至少包含一个给定的串，给定的串有 \(m\) 个

解法

由多模式串匹配想到AC自动机，由计数想到dp

首先建好Trie图，更新所有end标记。记 \(dp[now][st][flag]\) 表示当前正在匹配第 \(st\) 位，已确定的串匹配到了Trie图上的 \(now\) 号节点，\(flag\) 表示是否已经出现过给定的模式串。总共有 \((\sum_{i=1}^{m} |s_i|)\times n \times 2\) 种状态，显然要记忆化搜索。对于每个状态枚举下一位所有可能的 \(26\) 位字符，并在Trie图上进行节点转移，flag或上end标记，最后累加答案。当 \(st=n+1\) 即已经匹配完成时，返回值为flag的状态（显然若有给定字符串则贡献 \(1\) 的答案）。最终的结果为初始状态 \(dp[0][1][false]\)

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define Mod 10007
#define N 107

template<class T>
inline void read(T &x){
    x=0;char c=getchar();T flag=1;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    x*=flag;
}

struct Trie{
    int vis[26],fail,end;
}go[N*100];

int cnt=0,n,m,f[N*100][N][2];
char s[N];
queue<int> Q;

inline void insert(){
    int now=0,len=strlen(s);
    for(int i=0;i<len;i++){
        int to=s[i]-'A';
        if(!go[now].vis[to])
            go[now].vis[to]=++cnt;
        now=go[now].vis[to];
    }
    go[now].end=1;
}
inline void Get_fail(){
    for(int i=0;i<26;i++)
        if(go[0].vis[i]) Q.push(go[0].vis[i]);
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        for(int i=0;i<26;i++)
            if(go[u].vis[i]){
                go[go[u].vis[i]].fail=go[go[u].fail].vis[i];
                go[go[u].vis[i]].end|=go[go[go[u].fail].vis[i]].end;
                Q.push(go[u].vis[i]);
            }else go[u].vis[i]=go[go[u].fail].vis[i];
    }
}
int dfs(int now,int st,bool flag){
    if(st==m+1) return flag;
    if(f[now][st][flag]!=-1) return f[now][st][flag];
    f[now][st][flag]=0;int ret=0;
    for(int i=0;i<26;i++){
        int to=go[now].vis[i];
        ret=(ret+dfs(to,st+1,flag|go[to].end))%Mod;
    }
    return f[now][st][flag]=ret;
}
int main(){
//    freopen("dict.in","r",stdin);
//    freopen("dict.out","w",stdout);
    memset(f,-1,sizeof(f));
    read(n);read(m);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        insert();
    }
    Get_fail();
    printf("%d",dfs(0,1,false));
}
/*
2 2
AB
BA
*/