题目传送门

-------------------------------------- 过年在家无聊补一下这周做的几道AC自动机的模板题

sol:AC自动机,在fail边的基础上再加一个last边,指向真正有效的节点,跳fail边改成跳last边来跳过无效点。

  • AC自动机

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef pair<int, int> PII;
    const int MAXN = ;
    struct Trie {
    int son[MAXN][], fail[MAXN], last[MAXN];
    int cnt[MAXN], inde[MAXN]; int tot, root, _max;
    vector<int> vec; string str[];
    int add_node() {
    memset(son[tot], -, sizeof(son[tot]));
    cnt[tot] = ; inde[tot] = -;
    return tot ++;
    }
    void init() {
    tot = _max = ;
    root = add_node();
    }
    void insert(char* s, int id) {
    int p = root;
    for (int i = ; s[i]; i++) {
    int index = s[i] - 'a';
    if (son[p][index] == -)
    son[p][index] = add_node();
    p = son[p][index];
    }
    inde[p] = id;
    str[id] = s;
    }
    void build() {
    queue<int> que;
    fail[root] = last[root] = root;
    for (int i = ; i < ; i++) {
    if (son[root][i] == -) son[root][i] = root;
    else {
    fail[son[root][i]] = root;
    last[son[root][i]] = root;
    que.push(son[root][i]);
    }
    }
    while (!que.empty()) {
    int p = que.front(); que.pop();
    for (int i = ; i < ; i++) {
    if (son[p][i] == -) son[p][i] = son[fail[p]][i];
    else {
    fail[son[p][i]] = son[fail[p]][i];
    if (inde[son[fail[p]][i]] != -)
    last[son[p][i]] = son[fail[p]][i];
    else
    last[son[p][i]] = son[last[p]][i];
    que.push(son[p][i]);
    }
    }
    }
    }
    void slove(char* s) {
    int p = root;
    for (int i = ; s[i]; i++) {
    int index = s[i] - 'a';
    p = son[p][index];
    for (int tmp = p; tmp != root; tmp = last[tmp]) {
    if (inde[tmp] == -) continue;
    cnt[tmp] ++;
    if (cnt[tmp] > _max) {
    _max = cnt[tmp];
    vec.clear();
    vec.push_back(inde[tmp]);
    } else if (cnt[tmp] == _max) {
    vec.push_back(inde[tmp]);
    }
    }
    }
    }
    void output() {
    printf("%d\n", _max);
    sort(vec.begin(), vec.end());
    for (int i = ; i < vec.size(); i++)
    cout << str[vec[i]] << endl;
    }
    } ac;
    char s[];
    int main() {
    int n;
    while (scanf("%d", &n) && n) {
    ac.init();
    for (int i = ; i <= n; i++) {
    scanf("%s", s);
    ac.insert(s, i);
    }
    ac.build(); scanf("%s", s);
    ac.slove(s); ac.output();
    }
    return ;
    }
05-11 21:57
查看更多