Tag-AC自动机

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-10-04 22:22:06 |  0 Comments  |  AC自动机 字符串

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'
Title - Artist
0:00