本文主要是介绍UVA 10679 I love Strings!!!(AC自动机)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620
ProblemG
ILove Strings!!!
Input:Standard Input
Output:Standard Output
TimeLimit: 4 Seconds
Hmmmmmm…………strings again :) Then it must be an easy task for you. You are given with a string S of length less than 100,001, containing only characters from lower and uppercase English alphabet (‘a’-‘z’and ‘A’ – ‘Z’). Then follows q (q < 100) queries where each query contains a string T of maximum length 1,000(also contains only ‘a’-‘z’ and ‘A’ – ‘Z’). You have to determine whether or not T is a sub-string of S.
Input
First line contains aninteger k (k < 10) telling the number of test cases to follow.Each test case begins with S. It is followed by q.After this line there are q lines each of which has a string T as defined before.
Output
For each query print ‘y’if it is a sub-string of S or ‘n’ otherwise followed by a newline. See the sample output below.
Sample Input
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
Output for Sample Input
y
n
y
Problemsetter: MohammadSajjad Hossain
题意：
给出一个文本串和若干个模式串，问模式串是否在文本串中出现过。
分析：
简单粗暴的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 52using 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 FCBRUCEfreopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCEint 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自动机)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
