ZOJ 3228 Searching the String

AC自动机吼题

虽然是很常规的模式串与匹配串的匹配计数问题，但它稍微给了一个新花样和一些坑。
写完这题，我当时就很感慨，如果我能在多校之前写过这题就好了……

题意：
先给你一个匹配串，再给你很多模式串，模式串前都有标号。标号为 0 表示计数可重叠，标号为 1 表示计数不可重叠。

思路：
写不来呀…………
看了题解，kuangbin只说了一句，加一个数组维护一下就好了…………这特么怎么维护…………

看了代码大致能理解，开了一个 last 数组记录每个位置上一次被匹配时的位置。
如果匹配串的位置与AC自动机上的相应位置的上一匹配位置差距为这个模式串的长度以上，说明可以匹配。
特别想要详细说，但又觉得没有什么好说的，所谓大道至简，原理真的很简单。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int max_n = 6e5 + 10;
const int max_c = 26;
int mp[max_n / 6], sel[max_n / 6];

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int dep[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
        dep[root] = 0;
    }

    int insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = str[i] - 'a';
            if (!next[now][c]) {
                next[now][c] = newNode();
                dep[next[now][c]] = dep[now] + 1;
            }
            now = next[now][c];
        }
        end[now] = true;
        return now;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int ans[max_n][2];
    int last[max_n];
    void query(char str[], int n)
    {
        memset(ans, 0, sizeof ans);
        memset(last, -1, sizeof last);
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            now = next[now][str[i] - 'a'];
            int cur = now;
            while (cur != root) {
                if (end[cur]) {
                    ans[cur][0]++;
                    if (i - last[cur] >= dep[cur]) {
                        last[cur] = i;
                        ans[cur][1]++;
                    }
                }
                cur = fail[cur];
            }
        }
        for (int i = 0; i < n; i++)
            printf("%d\n", ans[mp[i]][sel[i]]);
        puts("");
    }
} aho;

char str[max_n], buf[10];

int main()
{
    int n, cas = 0;
    while (scanf("%s", str) != EOF) {
        scanf("%d", &n);
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%d %s", sel + i, buf);
            mp[i] = aho.insert(buf);
        }
        aho.build();
        printf("Case %d\n", ++cas);
        aho.query(str, n);
    }
    return 0;
}