本文主要是介绍ybtoj 单词频率，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
YBToj AC 自动机第二题 单词频率
*
题目分析
首先便是先把AC自动机模板先敲一遍，因为满足无后效性，所以可以逆BFS序进行类似于递推的操作，因为在插入trie的过程中储存了每个匹配串的最后一个字母，所以可以由此进行多重匹配，保证答案的准确性
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define N 1100001
using namespace std;
int n,trie[N][26],tot=1,s[N][2],las[201],nxt[N],que[N];
char w[N];
void ins(int num)
{int r=1,x,len=strlen(w+1);for(int i=1;i<=len;i++){x=w[i]-'a';if(!trie[r][x]) trie[r][x]=++tot;r=trie[r][x];s[r][0]++;}las[num]=r;return;
}
void bfs()
{for(int i=0;i<26;i++) trie[0][i]=1;que[1]=1,nxt[1]=0;int q1=1,q2=1,r;for(;q1<=q2;q1++){r=que[q1];for(int i=0;i<26;i++){if(!trie[r][i]) trie[r][i]=trie[nxt[r]][i];else que[++q2]=trie[r][i],nxt[trie[r][i]]=trie[nxt[r]][i];}}for(int i=1;i<=tot;i++) s[que[i]][1]=s[que[i]][0];for(int i=tot;i>0;i--) s[nxt[que[i]]][1]+=s[que[i]][1];return;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%s",w+1),ins(i);bfs();for(int i=1;i<=n;i++) printf("%d\n",s[las[i]][1]);return 0;
}
```AC自动机 例2
这篇关于ybtoj 单词频率的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
