hdu 3065 AC自动机 匹配串编号以及出现次数

本文主要是介绍hdu 3065 AC自动机 匹配串编号以及出现次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

仍旧是天朝语题。

第一行，一个整数N（1<=N<=1000），表示病毒特征码的个数。
接下来N行，每行表示一个病毒特征码，特征码字符串长度在1—50之间，并且只包含“英文大写字符”。任意两个病毒特征码，不会完全相同。
在这之后一行，表示“万恶之源”网站源码，源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符（不包括回车）。

解析：

加两个数组来维护 id 和 出现次数就行了 (￣▽￣)" 。

代码：

#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define LL long long
#define lson lo,mi,rt<<1
#define rson mi+1,hi,rt<<1|1
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)using namespace std;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double ee = exp(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
const double pi = acos(-1.0);
const LL iinf = 0x3f3f3f3f3f3f3f3f;const int dictSize = 128;int cnt[maxn];
char name[maxn][55];struct Trie
{int next[maxn * dictSize][dictSize];   //next[i][j]保存节点i的那个编号为j的节点(小写字母按字典序编号为0-(a),1-(b),2-(c),...)int fail[maxn * dictSize];             //后缀链接 fail[j]表示节点j沿着失配指针往回走时 遇到的下一个单词节点编号int end[maxn * dictSize];              //保存次数int id[maxn * dictSize];               //保存对应编号int rt;                                //根int nodeNum;                           //节点个数void init(){mem0(cnt);nodeNum = 0;rt = newNode();}int newNode(){for (int i = 0; i < dictSize; i++)next[nodeNum][i] = -1;end[nodeNum++] = 0;return nodeNum - 1;}//将字符串str加入Trie前缀树中void insert(char str[], int i){int len = strlen(str);int now = rt;for (int i = 0; i < len; i++){if (next[now][str[i]] == -1){next[now][str[i]] = newNode();}now = next[now][str[i]];}end[now]++;id[now] = i;}//建立后缀链接void build(){queue<int> q;fail[rt] = rt;for (int i = 0; i < dictSize; i++){if (next[rt][i] == -1){next[rt][i] = rt;}else{fail[next[rt][i]] = rt;q.push(next[rt][i]);}}while (!q.empty()){int now = q.front();q.pop();for (int i = 0; i < dictSize; i++){if (next[now][i] == -1){next[now][i] = next[fail[now]][i];}else{fail[next[now][i]] = next[fail[now]][i];q.push(next[now][i]);}}}}//询问子串们在串str中出现的次数void query(char str[]){int len = strlen(str);int now = rt;for (int i = 0; i < len; i++){now = next[now][str[i]];int temp = now;while (temp != rt){cnt[id[temp]] += end[temp];temp = fail[temp];}}}void debug(){for (int i = 0; i < nodeNum; i++){printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);for(int j = 0;j < 26;j++)printf("%2d",next[i][j]);printf("]\n");}}
} ac;const int maxs = 2e6 + 10;
char str[maxs];int main()
{
#ifdef LOCALFIN;
#endif // LOCALint n;while (~scanf("%d", &n)){ac.init();for (int i = 1; i <= n; i++){scanf("%s", name[i]);ac.insert(name[i], i);}ac.build();scanf("%s", str);ac.query(str);for (int i = 1; i <= n; i++){if (cnt[i]){printf("%s: %d\n", name[i], cnt[i]);}}}return 0;
}

这篇关于hdu 3065 AC自动机 匹配串编号以及出现次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---