[UVA][AC自動機] 10679 - I Love Strings!!
I loveStrings!!!
Input / Output:standard I/O
Time Limit: 4 sec
Hmmmmmm…………strings again :) Then it must be aneasy task for you. Well……you are given with a string S of length notmore than 100,000 characters (only ‘a’-‘z’ and ‘A’ – ‘Z’). Then follows q (q< 1000) queries where each query contains a string T of maximumlength 1,000 (also contains only ‘a’-‘z’ and ‘A’ – ‘Z’). You should determinewhether or not T is a substring of S.
Input
First line contains an integer k (k< 10) telling the number of test cases to follow. Each test case beginswith S. It is followed by q. After this line there are qlines each of which has a string T as defined before.
Output
For each query print ‘y’ if it is a substringof S or ‘n’ otherwise followed by a new line. See the sample outputbelow.
Sample Input
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
Sample Output
y
n
y
怕會有重複的 T, 因此多用了一個 map
第一次實做 AC自動機, 請多見諒
//C++ 180ms
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define maxKind 52
using namespace std;
struct Node{
Node *fail;
Node *next[maxKind];
int cnt;
int who;
Node() {
fail = NULL;
cnt = 0;
who = 0;
memset(next, 0, sizeof(next));
}
};
void build_Trie(const char* str, Node *root, int who) {
Node *p = root;
int i = 0, idx;
while(str[i]) {
if(str[i] >= 'A' && str[i] <= 'Z')
idx = str[i]-'A';
else
idx = str[i]-'a'+26;
if(p->next[idx] == NULL) {
p->next[idx] = new Node();
}
p = p->next[idx];
i++;
}
p->cnt++;
p->who = who;
}
void build_AC_automation(Node *root) {
root->fail = NULL;
queue<Node*> Q;
Q.push(root);
Node *tn, *p;
while(!Q.empty()) {
tn = Q.front();
Q.pop();
for(int i = 0; i < maxKind; i++) {
if(tn->next[i] == NULL)
continue;
Q.push(tn->next[i]);
p = tn->fail;
while(p != NULL && p->next[i] == NULL)
p = p->fail;
if(p == NULL)
tn->next[i]->fail = root;
else
tn->next[i]->fail = p->next[i];
}
}
}
void free_AC_automation(Node *root) {
queue<Node*> Q;
Q.push(root);
Node *tn, *p;
while(!Q.empty()) {
tn = Q.front();
Q.pop();
for(int i = 0; i < maxKind; i++) {
if(tn->next[i] != NULL) {
Q.push(tn->next[i]);
}
}
free(tn);
}
}
void query(const char* str, Node *root, int cnt[]) {
int i = 0, idx;
Node *tn, *p;
tn = root;
while(str[i]) {
if(str[i] >= 'A' && str[i] <= 'Z')
idx = str[i]-'A';
else
idx = str[i]-'a'+26;
while(tn->next[idx] == NULL && tn != root)
tn = tn->fail;
tn = tn->next[idx];
tn = (tn == NULL) ? root : tn;
p = tn;
while(p != root && p->cnt != -1) {
/*
cnt += p->cnt;
p->cnt = 0;
*/
cnt[p->who] = 1;
p->cnt = -1;
p = p->fail;
}
i++;
}
}
char buf[100001];
int main() {
int t, n;
scanf("%d", &t);
getchar();
map<string, int> record;
string S, T[1001];
while(t--) {
gets(buf);
S = buf;
scanf("%d", &n);
record.clear();
getchar();
Node *root = new Node();
int encode = 0;
for(int i = 0; i < n; i++) {
gets(buf);
T[i] = buf;
if(record[T[i]] == 0)
record[T[i]] = ++encode;
build_Trie(T[i].c_str(), root, record[T[i]]);
}
int cnt[1001] = {};
build_AC_automation(root);
query(S.c_str(), root, cnt);
free_AC_automation(root);
for(int i = 0; i < n; i++) {
int num = record[T[i]];
printf("%c\n", cnt[num] == 0 ? 'n' : 'y');
}
}
return 0;
}