HDU 6096 String

AC自动机好题，恐怕出题人都完全没有想到是AC自动机。
队友在写这题的时候突然发现了AC自动机的题解。
我看了一下发现还真是板子题。

正文：

WTM！！！！想打人！！！！！！！！！

Shit！！！

淦，再也不为了缩行偷懒了

这题我真的写了好久，今天刚刚发现错误，真的真的真的就是一个板子题，不过要转换一下并且check一下长度就可以了。
但是！！我为了偷懒，在输出的时候，就把答案清零了，这就导致了相同前后缀的答案错误！！！

题意：
给你很多字符串。再给你多组前后缀，问这几组前后缀在以上字符串的出现次数。

思路：
将前缀prefix 与 后缀 suffix 通过一个非字母字符连接，插入到trie中。
再将模式串通过相同的非字母字符连接，对其跑一边AC 自动机记录一下答案就可以了。

需要注意的地方就是模式串的长度不能小于后缀+前缀。

AC Code

#include <bits/stdc++.h>

using namespace std;

const int max_n = 5e5 + 10;
const int max_c = 27;

int ans[max_n], mp[max_n];

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

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

    void init()
    {
        size = 1;
        root = newNode();
    }

    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();
            now = next[now][c];
        }
        limit[now] = len - 1;
        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]);
                }
        }
    }

    void query(char str[], int len)
    {
        int now = root;
        for (int i = 0; str[i]; i++) {
            now = next[now][str[i] - 'a'];
            int cur = now;
            while (cur != root) {
                if (limit[cur] && len >= limit[cur])
                    ans[cur]++;
                cur = fail[cur];
            }
        }
    }
} aho;

char str[max_n], prefix[max_n], suffix[max_n];
pair<int, int> key[max_n];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        memset(ans, 0, sizeof ans);
        scanf("%d %d", &n, &m);
        int cur = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%s", str + cur);
            key[i] = make_pair(cur, strlen(str + cur));
            cur += key[i].second;
        }
        aho.init();
        for (int i = 1; i <= m; i++) {
            scanf("%s %s", prefix + 1, suffix);
            prefix[0] = '{';
            strcat(suffix, prefix);
            mp[i] = aho.insert(suffix);
        }
        aho.build();
        for (int i = 1; i <= n; i++) {
            int st = key[i].first, en = st + key[i].second;
            for (int j = st; j <= en; j++)
                prefix[j - st] = suffix[j - st] = str[j];
            prefix[key[i].second] = suffix[key[i].second] = 0;
            strcat(prefix, "{");
            strcat(prefix, suffix);
            aho.query(prefix, key[i].second);
        }
        for (int i = 1; i <= m; i++)
            printf("%d\n", ans[mp[i]]); //我在这里给ans清零了……
    }
    return 0;
}