首页 > 代码库 > UVa 10679 - I Love Strings!!
UVa 10679 - I Love Strings!!
题目:给你一个目标串,和一些模式串,问每个模式串是否在目标串中出现。
分析:字符串,AC自动机。一开始用KMP算法,TLE了才发现会超时,改用AC自动机;
直接利用AC自动机存储,查询即可,然后按顺序输出;
如果模式串中有重复的,直接利用并查集合并即可,只须判断父节点。
说明:╮(╯▽╰)╭计算复杂度时,数据组数被忽略了;注意初始化。
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; char s[100002],t[1002]; #define nodesize 40004 //节点个数 #define dictsize 52 //字符集大小 typedef struct node1 { int flag; //值域 node1* fail; node1* next[dictsize]; }tnode; tnode dict[nodesize+1]; tnode* Q[nodesize+1]; int ID[256]; int visit[1002]; int father[1002]; class AC_DFA { private: int size; tnode* root; public: AC_DFA() {makeID();init();} void makeID() { for ( int i = 0 ; i < 26 ; ++ i ) { ID['a'+i] = i; ID['A'+i] = i+26; } } void init() { memset( dict, 0, sizeof( dict ) ); root=NULL; size=0; root=newnode(); for ( int i = 0 ; i < 1001 ; ++ i ) father[i] = i; } tnode* newnode() { dict[size].fail = root; return &dict[size ++]; } void insert( char* word, int id ) { tnode* now = root; for ( int i = 0 ; word[i] ; ++ i ) { if ( !now->next[ID[word[i]]] ) now->next[ID[word[i]]] = newnode(); now = now->next[ID[word[i]]]; } if ( now->flag ) father[id] = now->flag; else now->flag = id; } void setfail() { Q[0] = root; root->fail = NULL; for ( int move = 0,save = 1 ; move < save ; ++ move ) { tnode* now = Q[move]; for ( int i = 0 ; i < dictsize ; ++ i ) if ( now->next[i] ) { tnode* p = now->fail; while ( p && !p->next[i] ) p = p->fail; now->next[i]->fail = p?p->next[i]:root; Q[save ++] = now->next[i]; } } } void query( char* line, int q ) { memset( visit, 0, sizeof( visit ) ); tnode* now = root; for ( int i = 0 ; line[i] ; ++ i ) { while ( now && !now->next[ID[line[i]]] ) now = now->fail; now = now?now->next[ID[line[i]]]:root; for ( tnode* p = now ; p ; p = p->fail ) visit[p->flag] = 1; } for ( int i = 1 ; i <= q ; ++ i ) if ( visit[father[i]] ) printf("y\n"); else printf("n\n"); return; } }dfa; /* AC_DFA end */ int main() { int k,q; scanf("%d",&k); while ( k -- ) { dfa.init(); scanf("%s%d",s,&q); for ( int i = 1 ; i <= q ; ++ i ) { scanf("%s",t); dfa.insert( t, i ); } dfa.setfail(); dfa.query(s, q); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。