链接:

https://www.luogu.org/problem/P3796

题意:

有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。

思路:

字典树的每个结束节点记录对应的模板串标号, 匹配时记录次数.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#include <iomanip>

#include <iostream>

#include <sstream>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int MAXN = 2e6+10;

struct Trie

{

    int Next[26];

    int End;

    int Fail;

    void Init()

    {

        memset(Next, 0, sizeof(Next));

        End = Fail = 0;

    }

}trie[MAXN];

int cnt, n, pos, maxt;

int Ans[MAXN];

char s[MAXN], Pt[200][100];

void Insert(char *t, int id)

{

    int len = strlen(t);

    int p = 0;

    for (int i = 0;i < len;i++)

    {

        if (trie[p].Next[t[i]-'a'] == 0)

        {

            trie[p].Next[t[i]-'a'] = ++cnt;

            trie[cnt].Init();

        }

        p = trie[p].Next[t[i]-'a'];

    }

    trie[p].End = id;

}

void BuildAC()

{

    queue<int> que;

    for (int i = 0;i < 26;i++)

    {

        if (trie[0].Next[i] != 0)

            que.push(trie[0].Next[i]);

    }

    while (!que.empty())

    {

        int u = que.front();

        que.pop();

        for (int i = 0;i < 26;i++)

        {

            if (trie[u].Next[i])

            {

                trie[trie[u].Next[i]].Fail = trie[trie[u].Fail].Next[i];

                que.push(trie[u].Next[i]);

            }

            else

                trie[u].Next[i] = trie[trie[u].Fail].Next[i];

                //压缩路径, 没有的点直接指向别的节点, 减少向上找的时间

        }

    }

}

void Query(char *qs)

{

    int len = strlen(qs);

    int p = 0;

    for (int i = 0;i < len;i++)

    {

        p = trie[p].Next[qs[i]-'a'];

        for (int j = p;j != 0 && trie[j].End != -1;j = trie[j].Fail)

        {

            //将所有能出现的匹配都跑一遍, 同时处理防止多跑.

            if (trie[j].End != 0)

            {

                Ans[trie[j].End]++;

                maxt = max(maxt, Ans[trie[j].End]);

            }

        }

    }

}

int main()

{

    while (~scanf("%d", &n) && n)

    {

        memset(Ans, 0, sizeof(Ans));

        cnt = pos = maxt = 0;

        trie[0].Init();

        for (int i = 1;i <= n;i++)

        {

            scanf("%s", Pt[i]);

            Insert(Pt[i], i);

        }

        scanf("%s", s);

        BuildAC();

        Query(s);

        if (maxt <= 0)

            puts("0");

        else

        {

            printf("%d\n", maxt);

            for (int i = 1;i <= n;i++)

            {

                if (Ans[i] == maxt)

                    puts(Pt[i]);

            }

        }

    }

    return 0;

}

巴特西

洛谷-P3796-AC自动机加强版

链接:

题意:

思路:

代码:

最新文章

热门文章