Hihocoder 1887 2018-2019ICPC北京H Approximate Matching AC自动机+DP

题目大意

给出一个模式串n为01串，求问长度为m的所有文本串中有多少长度为n的子串能做到与模式串近似匹配。

近似匹配的意思为：最多只有一个字符与模式串不同。

题解

我们是无法在短时间内强行进行近似匹配的，所以只能转化成完全匹配来做。

最多只有一个字符与模式串不同，这样我们就可以把模式串写成n+1个不同的模式串，即原模式串每个字符都变换一次，作为一个新的模式串。

多模式串匹配问题，一定是AC自动机。

我们把所有的模式串合起来建立一个AC自动机，在上面跑DP就可以了。

我们设dp[i][j]表示当前遍历文本串的第i位，到达AC自动机状态j的方案数。

当然这样空间是不够用的，所以需要用滚动数组优化掉第一维的空间。

对于上一位的状态j，假设当前位到达状态为next[j][k]，k为枚举的第i位的字符；

若当前状态为终结状态，则总方案数ans += dp[i-1&1][j] * (1ll << (m-i))

若当前状态非终结状态，则有转移dp[i&1][next[j][k]] += dp[i-1&1][j];

直接DP即可。

代码

#include <bits/stdc++.h>
const int maxn = 2e3 + 5;
using namespace std;
typedef long long ll;
int nex[maxn][2], fail[maxn], ed[maxn], flag[maxn];
int root, p;
inline int newnode() {
    for (int i = 0; i < 2; ++i) {
        nex[p][i] = -1;
    }
    ed[p++] = 0;
    return p - 1;
}
inline void init() {
    p = 0;
    root = newnode();
}
inline void insert(char *buf) {
    int now = root;
    for (int i = 0; buf[i]; ++i) {
        if (nex[now][buf[i]-'0'] == -1) 
            nex[now][buf[i]-'0'] = newnode();
        now = nex[now][buf[i]-'0'];
    }
    ed[now] = 1;
    flag[now] = 1;
} 
void build() {
    queue<int> que;
    fail[root] = root;
    for (int i = 0; i < 2; ++i) {
        if (nex[root][i] == -1)
            nex[root][i] = root;
        else {
            fail[nex[root][i]] = root;
            que.push(nex[root][i]);
        }
    }
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        for (int i = 0; i < 2; ++i) {
            if (nex[now][i] == -1) 
                nex[now][i] = nex[fail[now]][i];
            else {
                fail[nex[now][i]] = nex[fail[now]][i];
                if(ed[nex[fail[now]][i]])
                    ed[nex[now][i]] = 1;
                que.push(nex[now][i]);
            }
        }
    }
}
int T;
ll n,m;
char s[maxn];
ll dp[2][maxn];
int main(){
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%lld%lld",&n,&m);
        scanf("%s",s);
        insert(s);
        for(int i = 0;i < n;++i){
            if(s[i] == '1') s[i] = '0';
            else s[i] = '1';
            insert(s);
            if(s[i] == '1') s[i] = '0';
            else s[i] = '1';
        }
        build();
        ll ans = 0;
        dp[0][0] = 1;
        for(int i = 1;i <= m;++i){
            for(int j = 0;j < p;++j)dp[i & 1][j] = 0;
            for(int j = 0;j < p;++j){
                if(ed[j])continue;
                for(int k = 0;k < 2;++k){
                    if(ed[nex[j][k]]){
                        ans += dp[i + 1 & 1][j] * (1ll << (m - i));
                    }
                    else{
                        dp[i&1][nex[j][k]] += dp[i+1&1][j];
                    }
                }
            }
        }
        for(int i = 0;i < p;++i){
            dp[0][i] = dp[1][i] = 0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}