首页 > 代码库 > UVA 10679 I love Strings!!!(AC自动机)
UVA 10679 I love Strings!!!(AC自动机)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620
题意:
给出一个文本串和若干个模式串,问模式串是否在文本串中出现过。
分析:
简单粗暴的AC自动机模板题,要注意模式串可能有重复的情况。
/* * * Author : fcbruce * * Time : Sat 04 Oct 2014 03:30:15 PM CST * */ #include <cstdio> #include <iostream> #include <sstream> #include <cstdlib> #include <algorithm> #include <ctime> #include <cctype> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #ifdef _WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define maxm #define maxn 1000007 #define maxsize 52 using namespace std; int q[maxn<<1]; int _id[1007]; char YN[1007]; char query[1007]; char T[maxn]; struct Trie { int ch[maxn][maxsize]; int val[maxn]; int sz; Trie() { sz=1; val[0]=0; memset(ch[0],0,sizeof ch[0]); } void clear() { sz=1; val[0]=0; memset(ch[0],0,sizeof ch[0]); } int idx(const char ch) { if (islower(ch)) return ch-'a'+26; return ch-'A'; } int insert(const char *s,int v=1) { int u=0,l=strlen(s); for (int i=0;i<l;i++) { int c=idx(s[i]); if (ch[u][c]==0) { val[sz]=0; memset(ch[sz],0,sizeof ch[0]); ch[u][c]=sz++; } u=ch[u][c]; } if (val[u]!=0) return val[u]; return val[u]=v; } }; struct ACauto :public Trie { int cnt; int last[maxn]; int nex[maxn]; ACauto() { cnt=0; sz=1; val[0]=0; memset(ch[0],0,sizeof ch[0]); } void clear() { cnt=0; sz=1; val[0]=0; memset(ch[0],0,sizeof ch[0]); } void calc(int j) { if (j!=0) { YN[val[j]]='y'; calc(last[j]); } } void get_fail() { int f=0,r=-1; nex[0]=0; for (int c=0;c<maxsize;c++) { int u=ch[0][c]; if (u!=0) { nex[u]=0; q[++r]=u; last[u]=0; } } while (f<=r) { int x=q[f++]; for (int c=0;c<maxsize;c++) { int u=ch[x][c]; if (u==0) continue; q[++r]=u; int v=nex[x]; while (v>0 && ch[v][c]==0) v=nex[v]; nex[u]=ch[v][c]; last[u]=val[nex[u]]>0?nex[u]:last[nex[u]]; } } } void find(const char *T) { get_fail(); for (int i=0,j=0;T[i]!='\0';i++) { int c=idx(T[i]); while (j>0 && ch[j][c]==0) j=nex[j]; j=ch[j][c]; if (val[j]!=0) calc(j); else if (last[j]!=0) calc(last[j]); } } }acauto; int main() { #ifdef FCBRUCE freopen("/home/fcbruce/code/t","r",stdin); #endif // FCBRUCE int T_T; scanf ("%d",&T_T); while (T_T--) { acauto.clear(); scanf("%s",T); int n; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%s",query); _id[i]=acauto.insert(query,i); YN[i]='n'; } acauto.find(T); for (int i=1;i<=n;i++) printf("%c\n",YN[_id[i]]); } return 0; }
UVA 10679 I love Strings!!!(AC自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。