UVa 10679-I Love Strings!!

問題概要

100000文字以下の文字列Sが与えられる．Q個の1000文字以下の文字列に対しSの部分文字列となっているか判定せよ．

解法

Aho-Corasick法
Spagetthi Sourceさんを参照

実装(C++)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define REP(i,x) for(int i=0;i<(int)x;i++)

struct PMA{
	PMA* next[256]; //失敗時に0を利用
	vector<int> matched;
	PMA(){REP(i,256)next[i]=0;}
	~PMA(){REP(i,256)if(next[i])delete next[i];}
};
//パターンマッチングオートマトンの生成．生成元パターンをpattern,個数をcountに代入して用いる
PMA *buildPMA(char *pattern[],int count){
	PMA *root=new PMA,*now;
	root->next[0]=root;
	//Phase1.Trie木の生成
	REP(i,count){
		now=root;
		for(int j=0;pattern[i][j]!='\0';j++){
			if(now->next[(int)pattern[i][j]]==0)now->next[(int)pattern[i][j]]=new PMA;
			now=now->next[(int)pattern[i][j]];
		}
		now->matched.push_back(i);
	}

	queue<PMA*> que;
	//Phase2.幅優先探索によるオートマトンの生成．
	for(int i=1;i<256;i++){
		if(!root->next[i])root->next[i]=root; //使われていない部分のnextをrootに
		else{
			root->next[i]->next[0] = root; //失敗時はルートに戻る
			que.push(root->next[i]); 
		}
	}
	while(!que.empty()){
		now=que.front();que.pop();
		for(int i=1;i<256;i++){
			if(now->next[i]){
				PMA *next=now->next[0];
				while(!next->next[i])next=next->next[0];
				now->next[i]->next[0]=next->next[i];
				que.push(now->next[i]);
			}
		}
	}
	return root;
}

void match(PMA *pma,const char *s,vector<int> &res){
	for(int i=0;s[i]!='\0';i++){
		int c=s[i];
		while(!pma->next[c]){
			pma=pma->next[0];
		}
		pma=pma->next[c];
		REP(j,pma->matched.size()){
			res[pma->matched[j]]=true;
		}
	}
}
char S[110000];
char *T[1000];
int main() {
	REP(i,1000)T[i]=new char[1005];
	int TCASE;
	scanf("%d",&TCASE);
	for(;TCASE--;){
		scanf("%s",S);
		int q;scanf("%d",&q);
		REP(i,q){
			scanf("%s",T[i]);
		}
		PMA *root=buildPMA(T,q);
		vector<int> res(q);
		match(root,S,res);
		REP(i,q){
			puts(res[i]?"y":"n");
		}
	}
	return 0;
}