题目背景 : L_Y_T同学在最近的模拟赛中考了一道字符串的题,然后发现不会,返现值得了30分, 但会发现一个人用暴力枚举AC了!!!
于是L_Y_T十分的不爽,想要打出80分的暴力,于是就去学习了AC自动机
题目描述
有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。
输入输出格式
输入格式：
输入含多组数据。
每组数据的第一行为一个正整数NN，表示共有NN个模式串，1 ≤ N ≤ 150 1≤N≤150。
接下去N行，每行一个长度小于等于70的模式串。下一行是一个长度小于等于 106
的文本串T。
输入结束标志为N=0。
输出格式：
对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。
输入输出样例
输入样例#1：
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
输出样例#1：
4
aba
2
alpha
haha
以上就是凑字数的题面
说起来AC自动机,这是需要有字典树和KMP作为前置的
但是L_Y_T不知为何感觉和KMP没有多大关系…
我萌先来讲一下字典树的建立
说到字典树,L_Y_T感觉是十分神奇的
比如,如果我们想要插入 ultraman , ultraseven , ultramantero , cosmos , come
原谅我这个看特摄的OIER
那我们构建的树就是这样的
这样就很容易看出规律来了吧???
首先找到根节点,然后一个字母一个字母的加入,如果当前字母已经存在,那么就往下找,直到找不到为止.
然后,就在找不到的地方插入一个新的节点(看图)
然后就是emmmmm看代码
void build(string s,int num) {
int l = s.size() ;
int now = 0 ;
for(int i = 0 ; i < l ; i ++) {
if(tree[now].vis[s[i]-'a'] == 0) {//如果找不到了
tree[now].vis[s[i]-'a'] = ++cnt ;//建立一个新节点
clean(cnt) ;//由于多组数据.....emmmmmm
}
now = tree[now].vis[s[i]-'a'] ;//指向下一个节点
}
tree[now].end = num ;//记录结束位置
}
然后,重难点就是处理类似于KMP的next数组(这里是fail,终止地点)
然后L_Y_T感觉就是理解这么两句话:
1.如果可以找到点,那么**子节点的fail指针指向当前点的fail指针所指向的相同子节点
2.如果没有找到,那么当前节点的这个子节点指向当前子节点的fail所指向的子节点
代码实现
void get_fail() {
queue<int> q ;
for(int i = 0 ; i < 26 ; i ++) {
if(tree[0].vis[i]!=0) {
tree[tree[0].vis[i]].fail = 0 ;
q.push(tree[0].vis[i]) ;
}
}
while(!q.empty()) {
int u = q.front() ;
q.pop() ;
for(int i = 0 ; i < 26 ; i ++) {
if(tree[u].vis[i] != 0) {
tree[tree[u].vis[i]].fail = tree[tree[u].fail].vis[i] ;
q.push(tree[u].vis[i]) ;
}else {
tree[u].vis[i] = tree[tree[u].fail].vis[i] ;
}
}
}
}
然后其他的都比较好说了
总code
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <queue>
#include <algorithm>
#define maxn 210000
using namespace std ;
int n ;
struct Tree{
int fail ;
int vis[30] ;
int end ;
}tree[maxn] ;
struct dy{
int num ;
int los ;
}Ans[maxn] ;
int cnt ;
int cmp(dy x , dy y) ;
int read () ;
string s[maxn] ;
void clean(int x) ;
void get_fail() ;
int query(string s) ;
void build(string s,int num) ;
void clean(int x ) ;
int main() {
while(1) {
cin >> n ;
if(!n) break ;
cnt = 0 ;
clean(cnt) ;
for(int i = 1 ; i <= n ; i ++) {
cin >> s[i] ;
Ans[i].num = 0 ;
Ans[i].los = i ;
build(s[i],i) ;
}
tree[0].fail = 0 ;
get_fail() ;
cin >> s[0] ;
query(s[0]) ;
sort(Ans+1,Ans+1+n,cmp) ;
cout << Ans[1].num << endl ;
cout << s[Ans[1].los] << endl ;
for(int i = 2 ; i <= n ; i ++) {
if(Ans[i].num == Ans[i-1].num) {
cout << s[Ans[i].los] << endl ;
}else break ;
}
}
return 0;
}
void clean(int x) {
memset(tree[x].vis,0,sizeof(tree[x].vis)) ;
tree[x].fail = tree[x].end = 0 ;
}
int query(string s) {
int l = s.size() ;
int now = 0 , ans = 0 ;
for(int i = 0 ; i < l ; i ++) {
now = tree[now].vis[s[i]-'a'] ;
for(int t = now ; t ; t = tree[t].fail) {
Ans[tree[t].end].num ++ ;
}
}
return ans ;
}
void get_fail() {
queue<int> q ;
for(int i = 0 ; i < 26 ; i ++) {
if(tree[0].vis[i]!=0) {
tree[tree[0].vis[i]].fail = 0 ;
q.push(tree[0].vis[i]) ;
}
}
while(!q.empty()) {
int u = q.front() ;
q.pop() ;
for(int i = 0 ; i < 26 ; i ++) {
if(tree[u].vis[i] != 0) {
tree[tree[u].vis[i]].fail = tree[tree[u].fail].vis[i] ;
q.push(tree[u].vis[i]) ;
}else {
tree[u].vis[i] = tree[tree[u].fail].vis[i] ;
}
}
}
}
int cmp (dy x , dy y) {
if(x.num != y.num) {
return x.num > y.num ;
}return x.los < y.los ;
}
void build(string s,int num) {
int l = s.size() ;
int now = 0 ;
for(int i = 0 ; i < l ; i ++) {
if(tree[now].vis[s[i]-'a'] == 0) {
tree[now].vis[s[i]-'a'] = ++cnt ;
clean(cnt) ;
}
now = tree[now].vis[s[i]-'a'] ;
}
tree[now].end = num ;
}
京公网安备 11010502036488号