andyli

题解 UVA1449 【Dominating Patterns】
本题模板多但长度短,而文本串又很长,正适合用$AC$自动机。一个容易忽略的地方是重复吹安的模板。如果模板有重复,后...
扫描右侧二维码阅读全文
26
2019/06

题解 UVA1449 【Dominating Patterns】

本题模板多但长度短,而文本串又很长,正适合用$AC$自动机。一个容易忽略的地方是重复吹安的模板。如果模板有重复,后一个子串会覆盖前一个,因此需要用其他方法判重,其中一个简单的方法是建一个字符串到编号的索引$map<string,int> mp$,每次在初始化的时候清空,在插入的时候更新,最后在输出的时候使用。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 11000, maxm = 151;

map<string, int> mp;
struct AhoCorasickAutomata
{
    int ch[maxn][26];
    int f[maxn];     // fail函数
    int val[maxn];   // 每个字符串的结尾结点都有一个非0的val
    int last[maxn];  // 输出链表的下一个结点
    int cnt[maxm];
    int sz;

    void init()
    {
        sz = 1;
        memset(ch[0], 0, sizeof(ch[0]));
        memset(cnt, 0, sizeof(cnt));
        mp.clear();
    }
    // 字符c的编号
    int idx(char c) { return c - 'a'; }
    // 插入字符串。v必须非0
    void insert(char* s, int v)
    {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; i++)
        {
            int c = idx(s[i]);
            if (!ch[u][c])
            {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = v;
        mp[string(s)] = v;
    }
    // 递归打印以结点j结尾的所有字符串
    void print(int j)
    {
        if (j)
        {
            cnt[val[j]]++;
            print(last[j]);
        }
    }
    // 在T中找模板
    void find(char* T)
    {
        int n = strlen(T);
        int j = 0;  // 当前结点编号,初始为根结点
        for (int i = 0; i < n; i++)
        {  // 文本串当前指针
            int c = idx(T[i]);
            while (j && !ch[j][c])
                j = f[j];  // 顺着细边走,直到可以匹配
            j = ch[j][c];
            if (val[j])
                print(j);
            else if (last[j])
                print(last[j]);  // 找到了
        }
    }
    // 计算fail函数
    void getFail()
    {
        queue<int> q;
        f[0] = 0;
        // 初始化队列
        for (int c = 0; c < 26; c++)
        {
            int u = ch[0][c];
            if (u)
            {
                f[u] = 0;
                q.push(u);
                last[u] = 0;
            }
        }
        // 按BFS顺序计算fail
        while (!q.empty())
        {
            int r = q.front();
            q.pop();
            for (int c = 0; c < 26; c++)
            {
                int u = ch[r][c];
                if (!u)
                    continue;
                q.push(u);
                int v = f[r];
                while (v && !ch[v][c])
                    v = f[v];
                f[u] = ch[v][c];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }
} ac;

char str[1000005], P[maxm][80];
int main()
{
    int n;
    while (~scanf("%d", &n) && n)
    {
        ac.init();
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", P[i]);
            ac.insert(P[i], i);  // 注意要更新mp映射
        }
        ac.getFail();
        scanf("%s", str);
        ac.find(str);  // 计算每个模板的cnt值
        int ans = *max_element(ac.cnt + 1, ac.cnt + 1 + n);  // 最大值
        printf("%d\n", ans);
        for (int i = 1; i <= n; i++)
            if (ac.cnt[mp[string(P[i])]] == ans)  // 用到了mp映射
                printf("%s\n", P[i]);
    }
    return 0;
}
Last modification:June 26th, 2019 at 03:44 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment