2018北京区域赛 Approximate Matching （AC自动机+dp）

这道题我们首先发现因为最多就一个地方不一样，因此其实最终的答案就是n+1个字符串所产生的，也就是对于给定串，只改一位以及原串加入字典树

之后的做法和一道经典例题（文本打印机）一毛一样，就是枚举在哪个节点跑ac自动机+dp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int mod=1e9+7;
string s;
struct node{
    int cnt;
    node *nxt[2];
    node *fail;
}*rt;
int num,idx;
node pool[666][6100];
int val[N];
ll f[105][6100][2];
int n,m;
int sum;
void insert(string s,int x){
    node *p=rt;
    int i;
    for(i=0;i<s.size();i++){
        int sign=s[i]-'0';
        if(p->nxt[sign]==NULL){
            p->nxt[sign]=pool[sum]+(++idx);
            p->nxt[sign]->cnt=++num;
        }
        p=p->nxt[sign];
        if(i==(int)s.size()-1){
            val[p->cnt]=x;
        }
    }
}
void build(){
    int i;
    queue<node *> q;
    rt->fail=rt;
    for(i=0;i<2;i++){
        if(rt->nxt[i]){
            rt->nxt[i]->fail=rt;
            q.push(rt->nxt[i]);
        }
        else{
            rt->nxt[i]=rt;
            rt->nxt[i]->fail=rt;
        }
    }
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(i=0;i<2;i++){
            if(t->nxt[i]){
                t->nxt[i]->fail=t->fail->nxt[i];
                q.push(t->nxt[i]);
            }
            else{
                t->nxt[i]=t->fail->nxt[i];
            }
        }
        val[t->cnt]|=val[t->fail->cnt];
    }
}
void init(){
    memset(f,0,sizeof f);
    int i;
    for(i=0;i<=num;i++)
        val[i]=0;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int i,j,k;
    while(t--){
        init();
        rt=pool[sum];
        rt->cnt=0;
        idx=0,num=0;
        cin>>n>>m;
        cin>>s;
        insert(s,1);
        for(i=0;i<(int)s.size();i++){
            if(s[i]=='1')
                s[i]='0';
            else
                s[i]='1';
            insert(s,1);
            if(s[i]=='1')
                s[i]='0';
            else
                s[i]='1';
        }

        build();
        f[0][0][0]=1;
        for(i=1;i<=m;i++){
            for(j=0;j<=num;j++){
                for(k=0;k<=1;k++){
                    int id=(pool[sum]+j)->nxt[k]->cnt;
                    if(val[id]){
                        f[i][id][1]+=f[i-1][j][1]+f[i-1][j][0];
                    }
                    else{
                        f[i][id][1]+=f[i-1][j][1];
                        f[i][id][0]+=f[i-1][j][0];
                    }
                }
            }
        }
        ll ans=0;
        for(i=0;i<=num;i++)
            ans+=f[m][i][1];
        cout<<ans<<endl;
        sum++;
    }
    return 0;
}