UVA 10679 I love Strings!!!(AC自动机) - c++编程基础

TOP

UVA 10679 I love Strings!!!(AC自动机)

2015-07-20 17:33:33 来源: 作者: 【大中小】浏览:2次

Tags：UVA 10679 love Strings 动机

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

abcdefghABCDEFGH

abc

abAB

xyz

Output for Sample Input

Problemsetter: MohammadSajjad Hossain

题意：

给出一个文本串和若干个模式串，问模式串是否在文本串中出现过。

分析：

简单粗暴的AC自动机模板题，要注意模式串可能有重复的情况。

/*
 *
 * Author : fcbruce
 *
 * Time : Sat 04 Oct 2014 03:30:15 PM CST
 *
 */
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #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
                  
                   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]!='';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 ,YN[_id[i]]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：SPOJ 11840. Sum of Squares with..	下一篇：c++命令提示符窗口下打印指定大小..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: