HDU2896+AC自动机

ac自动机 模板题

 /*

 */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int maxm = ;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-; struct Tree{
int id;
Tree *fail;
Tree *next[ maxn ];
};
Tree root;
Tree *q[ ];
char str[ maxm ];
int tot;
int cnt[ ];
int Index_cnt ;
bool vis[ ]; void init(){
root.id = ;
root.fail = NULL;
for( int i=;i<maxn;i++ )
root.next[ i ] = NULL;
} void build( char str[],int ID ){
int len = strlen( str );
Tree *p = &root;
Tree *tmp = NULL;
for( int i=;i<len;i++ ){
int id = str[i]-;
if( p->next[ id ]==NULL ){
tmp = (Tree *)malloc(sizeof( root ));
tmp->id = ;
for( int j=;j<maxn;j++ )
tmp->next[ j ] = NULL;
p->next[ id ] = tmp;
p = p->next[ id ];
}
else
p = p->next[ id ];
}
p->id = ID;
return ;
} void build_AC(){
int head = ,tail = ;
Tree *p = &root;
Tree *tmp = NULL;
q[ tail++ ] = p;
while( head!=tail ){
p = q[ head++ ];
for( int i=;i<maxn;i++ ){
if( p->next[i]!=NULL ){
if( p==(&root) ){
p->next[i]->fail = &root;
}
else{
tmp = p->fail;
while( tmp!=NULL ){
if( tmp->next[i]!=NULL ){
p->next[i]->fail = tmp->next[i];
break;
}
tmp = tmp->fail;
}
if( tmp==NULL )
p->next[i]->fail = &root;
}
q[ tail++ ] = p->next[i];
}
}
}
} void query( char str[] ){
int len = strlen( str );
Tree *p = &root;
Tree *tmp = NULL;
for( int i=;i<len;i++ ){
int id = str[i]-;
while( p->next[id]==NULL&&p!=(&root) ){
p = p->fail;
}
p = p->next[ id ];
if( p==NULL )
p = &root;
tmp = p;
while( tmp!=(&root) ){
if( tmp->id!=&&vis[tmp->id]==false ){
vis[tmp->id] = true;
cnt[ Index_cnt++ ] = tmp->id;
}
tmp = tmp->fail;
}
}
return ;
} int main(){
int n,m;
while( scanf("%d",&n)!=EOF ){
init();
char s[ ];
for( int i=;i<=n;i++ ){
scanf("%s",s);
build( s,i );
}
build_AC();
scanf("%d",&m);
tot = ;
for( int i=;i<=m;i++ ){
scanf("%s",str);
Index_cnt = ;
memset( vis,false,sizeof( vis ) );
query( str );
if( Index_cnt!= ) {
tot++;sort( cnt,cnt+Index_cnt );
printf("web %d:",i);
for( int j=;j<Index_cnt;j++ )
printf(" %d",cnt[j]);
printf("\n");
}
}
printf("total: %d\n",tot);
}
return ;
}
上一篇:读取全球ip获取用户地区


下一篇:2个监听器+ dialog + replysubject + extends