程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10679 I love Strings!!!(AC自動機)

UVA 10679 I love Strings!!!(AC自動機)

編輯：C++入門知識

UVA 10679 I love Strings!!!(AC自動機)

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;i0 && 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;
}