HDU 6138 Fleet of the Eternal Throne

昨天多校的AC自动机入门题……

为什么我还要写AC自动机入门题呢，因为我太不甘心了……

题意：
给你很多个字符串，很多个询问。
每个询问两个数( a , b) ，表示询问第 ( a)个字符串和第( b)个字符串的最长的子串同时必须是某一个给定字符串的前缀。

思路：
这个真的是很简单的，建议AC自动机初学者写完 HDU 2222 后马上来写这题……
仔细思考，AC自动机建立在Tire图上，Trie图上的一个结点就代表了一个前缀。
所以我将所有字符串建立一个AC自动机，对于一个询问的两个字符串，我用一个set去记录第一个字符串所能到达的结点。第二个字符串去查询是否有相同结点。如果有，就说明有一个子串同时是某一个字符串的前缀。将当前答案与这个结点的深度进行比较就好了……

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int max_n = 1e5 + 10;
const int max_c = 26;

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

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

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

    void insert(const string& str)
    {
        int len = str.length(), 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];
        }
    }

    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(const string& str, bool is_first)
    {
        if (is_first)
            key.clear();
        int now = root, len = str.length(), ans = 0;
        for (int i = 0; i < len; i++) {
            now = next[now][str[i] - 'a'];
            int cur = now;
            while (cur != root) {
                if (is_first)
                    key.insert(cur);
                else if (key.find(cur) != key.end()) 
                    ans = max(ans, dep[cur]);
                cur = fail[cur];
            }
        }
        if (!is_first)
            printf("%d\n", ans);
    }
} aho;

string str[max_n];

int main()
{
    ios_base::sync_with_stdio(false);

    int T, n, q, a, b;
    cin >> T;
    while (T--) {
        cin >> n;
        aho.init();
        for (int i = 0; i < n; i++) {
            cin >> str[i];
            aho.insert(str[i]);
        }
        aho.build();
        cin >> q;
        while (q--) {
            cin >> a >> b;
            if (a == b)
                printf("%d\n", (int)str[a - 1].length());
            else {
                aho.query(str[a - 1], true);
                aho.query(str[b - 1], false);
            }
        }
    }
    return 0;
}