@zzzc18
2017-07-31T21:41:10.000000Z
字数 4556
阅读 1063
字符串
找到一份很好的注释代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
struct Tree//字典树
{
int fail;//失配指针
int vis[26];//子节点的位置
int end;//标记有几个单词以这个节点结尾
}AC[1000000];//Trie树
int cnt=0;//Trie的指针
inline void Build(string s)
{
int l=s.length();
int now=0;//字典树的当前指针
for(int i=0;i<l;++i)//构造Trie树
{
if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点
AC[now].vis[s[i]-'a']=++cnt;//构造出来
now=AC[now].vis[s[i]-'a'];//向下构造
}
AC[now].end+=1;//标记单词结尾
}
void Get_fail()//构造fail指针
{
queue<int> Q;//队列
for(int i=0;i<26;++i)//第二层的fail指针提前处理一下
{
if(AC[0].vis[i]!=0)
{
AC[AC[0].vis[i]].fail=0;//指向根节点
Q.push(AC[0].vis[i]);//压入队列
}
}
while(!Q.empty())//BFS求fail指针
{
int u=Q.front();
Q.pop();
for(int i=0;i<26;++i)//枚举所有子节点
{
if(AC[u].vis[i]!=0)//存在这个子节点
{
AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
//子节点的fail指针指向当前节点的
//fail指针所指向的节点的相同子节点
Q.push(AC[u].vis[i]);//压入队列
}
else//不存在这个子节点
AC[u].vis[i]=AC[AC[u].fail].vis[i];
//当前节点的这个子节点指向当
//前节点fail指针的这个子节点
}
}
}
int AC_Query(string s)//AC自动机匹配
{
int l=s.length();
int now=0,ans=0;
for(int i=0;i<l;++i)
{
now=AC[now].vis[s[i]-'a'];//向下一层
for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail)//循环求解
{
ans+=AC[t].end;
AC[t].end=-1;
}
}
return ans;
}
int main()
{
int n;
string s;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>s;
Build(s);
}
AC[0].fail=0;//结束标志
Get_fail();//求出失配指针
cin>>s;//文本串
cout<<AC_Query(s)<<endl;
return 0;
}
Ok the code above is gg;
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 60000
using namespace std;
int n;
char tmp[20][200];
char S[100000000+1];
struct Trie{
bool val[MAXN];
int size,fail[MAXN],last[MAXN],ch[MAXN][27],num[MAXN];
queue<int> que;
int Sigma_Size;
int idx(char c){
return c-'a';
}
void insert(char *s){
int len=strlen(s);int now=0;int i;
for(i=0;i<len;i++){
int c=idx(s[i]);
if(!ch[now][c])
ch[now][c]=++size;
now=ch[now][c];
}
val[now]=1;
}
void Getfail(){
int i;
for(i=0;i<Sigma_Size;i++){
if(ch[0][i]!=0){
que.push(ch[0][i]);
last[ch[0][i]]=fail[ch[0][i]]=0;
}
}
while(!que.empty()){
int fro=que.front();que.pop();
int c;
for(c=0;c<Sigma_Size;c++){
int u=ch[fro][c];
if(!u) continue;
que.push(u);
int j=fail[fro];
while(j && !ch[j][c]) j=fail[j];
fail[u]=ch[j][c];
last[u]=val[fail[u]] ? fail[u] : last[fail[u]];
}
}
}
void print(int j){
if(val[j]) num[j]++;
if(j) print(last[j]);
}
void Find(char *s){
int u=0;
int len=strlen(s);
int i;
int now=0;
for(i=0;i<len;i++){
int c=idx(s[i]);
int j=now;
while(j && !ch[j][c]) j=fail[j];
now=ch[j][c];
if(val[now]) print(now);
else print(last[now]);
}
}
int query(char *s){
int i;
int now=0;
int len=strlen(s);
for(i=0;i<len;i++){
int c=idx(s[i]);
now=ch[now][c];
}
printf("%s %d\n",s,num[now]);
}
void clear(){
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
memset(last,0,sizeof(last));
memset(num,0,sizeof(num));
memset(fail,0,sizeof(fail));
size=0;
}
Trie(){
clear();
}
};
Trie T;
void INIT(){
scanf("%d",&n);
int i;
for(i=1;i<=n;i++){
scanf("%s",tmp[i]);
T.insert(tmp[i]);
}
scanf("%s",S);
T.Getfail();
}
void solve(){
int i;
T.Find(S);
for(i=1;i<=n;i++){
T.query(tmp[i]);
}
}
int main(){
freopen("ACautomata.in","r",stdin);
freopen("ACautomata.out","w",stdout);
T.Sigma_Size=26;
INIT();
solve();
return 0;
}
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 60000
using namespace std;
int n;
char tmp[20][200];
char S[100000000+1];
struct Trie{
bool val[MAXN];
int size,fail[MAXN],last[MAXN],ch[MAXN][27],num[MAXN];
queue<int> que;
int Sigma_Size;
int idx(char c){
return c-'a';
}
void insert(char *s){
int len=strlen(s);int now=0;int i;
for(i=0;i<len;i++){
int c=idx(s[i]);
if(!ch[now][c])
ch[now][c]=++size;
now=ch[now][c];
}
val[now]=1;
}
void Getfail(){
int i;
for(i=0;i<Sigma_Size;i++){
if(ch[0][i]!=0){
que.push(ch[0][i]);
last[ch[0][i]]=fail[ch[0][i]]=0;
}
}
while(!que.empty()){
int fro=que.front();que.pop();
int c;
for(c=0;c<Sigma_Size;c++){
int u=ch[fro][c];
if(!u){
ch[fro][c]=ch[fail[fro]][c];
continue;
}
que.push(u);
int j=fail[fro];
while(j && !ch[j][c]) j=fail[j];
fail[u]=ch[j][c];
last[u]=val[fail[u]] ? fail[u] : last[fail[u]];
}
}
}
void print(int j){
if(val[j]) num[j]++;
if(j) print(last[j]);
}
void Find(char *s){
int u=0;
int len=strlen(s);
int i;
int now=0;
for(i=0;i<len;i++){
int c=idx(s[i]);
int j=now;
now=ch[j][c];
if(val[now]) print(now);
else print(last[now]);
}
}
int query(char *s){
int i;
int now=0;
int len=strlen(s);
for(i=0;i<len;i++){
int c=idx(s[i]);
now=ch[now][c];
}
printf("%s %d\n",s,num[now]);
}
void clear(){
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
memset(last,0,sizeof(last));
memset(num,0,sizeof(num));
memset(fail,0,sizeof(fail));
size=0;
}
Trie(){
clear();
}
};
Trie T;
void INIT(){
scanf("%d",&n);
int i;
for(i=1;i<=n;i++){
scanf("%s",tmp[i]);
T.insert(tmp[i]);
}
scanf("%s",S);
T.Getfail();
}
void solve(){
int i;
T.Find(S);
for(i=1;i<=n;i++){
T.query(tmp[i]);
}
}
int main(){
freopen("ACautomata.in","r",stdin);
freopen("ACautomata.out","w",stdout);
T.Sigma_Size=26;
INIT();
solve();
return 0;
}