hdu 2222(AC自動機入門テンプレートの問題)

3791 ワード

シリアルとシリアルデータ構造同前 AC自動機

テーマリンク:https://vjudge.net/problem/HDU-2222
Keywords Search
In the moden time,Search engine came into the life of everbody like Google,Baidu,etc. Wiskey also wants to bring this feature to his image retrieval system. Every image have a long description,when users type some keywords to find the mage,the system will match the keywords with description of image and show the most keywordbe chemand. To simplify the proble,giving you a description ofイメージ,and some keywords,you shoul tell me how many keywords will be match.
Input
First line will contain one integer means how many cases will followow by. Each case will contain two integers N means the number of keywords and N keywors follow.(N<=10000) Each keyword will only contains characters'a'-'z',and the length will be not longer than 50. The last line is the description、and the length will be not longer than 1000.
Output
Print how many keywords are contained in the description.
Sample Input

1
5
she
he
say
shr
her
yasherhs

Sample Output

AC自動機入門問題です.
AC自動機概要: まず、AC自動機を紹介します.このアルゴリズムは1975年にベル実験室で生まれました.有名なマルチモードマッチングアルゴリズムの一つです.よくある例としては、n個の単語を与えて、m個の文字を含む文章を与えて、いくつの単語が文章に出てきたかを調べてみましょう.AC自動機を理解するには、まず辞書ツリーTrieとKMPモードマッチングアルゴリズムの基礎知識が必要です.KMPアルゴリズムは単一モードストリングのキャラクタマッチングアルゴリズムであり、AC自動機はマルチモードストリングのキャラクタマッチングアルゴリズムである.
AC自動機の構造:1.Trieを構築し、AC自動機の検索データ構造とする.2.failポインタを作成して、現在の文字を不一致にしたとき、一番長い共通の前のサフィックスを持つ文字にジャンプしてマッチングを続けます.KMPアルゴリズムのように、AC自動機はマッチング時に現在の文字がマッチングに失敗した場合、failポインタを使ってジャンプします.これにより、ジャンプ後の列のプレフィックスは、必ずジャンプ前のパターン列の後付けであり、ジャンプの新しい位置の深さ(一致文字数)は、ジャンプ前のノードよりも小さいことが分かる.したがって、bfsを利用してTrie上でfailポインタの解を行うことができます.3.メイン列をスキャンしてマッチングします.詳しい説明はブログをご覧ください.https://blog.csdn.net/bestsort/article/details/82947639
この問題の例コード

#include //AC      
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define cla(a, sum) memset(a, sum, sizeof(a))
#define rap(i, m, n) for(int i=m; i<=n; i++)
#define rep(i, m, n) for(int i=m; i>=n; i--)
#define bug printf("???
")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair P;
const int Inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 5e5+100;
template  void read(T &x){
    x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}


int T,n;
struct Tire{
	int tree[maxn][26],num[maxn];
	int fail[maxn];
	int cnt,root;//root      
	int tire(){
		rap(i,0,25)tree[cnt][i]=0;
		num[cnt++]=0;
		return cnt-1;
	}
	void init(){
		cnt=0;
		root=tire();
	}
	void insert(char buf[]){
		int len=strlen(buf);
		int now=root;
		for(int i=0;iQ;
		rap(i,0,25){
			if(tree[root][i]){
				fail[tree[root][i]]=root;
				Q.push(tree[root][i]); 
			}
			else tree[root][i]=root;
		} 
		while(!Q.empty() ){
			int now=Q.front() ;
			Q.pop() ;
			rap(i,0,25){
				if(tree[now][i]){
					fail[tree[now][i]]=tree[fail[now]][i];
					Q.push(tree[now][i]);
				}
				else tree[now][i]=tree[fail[now]][i];
			}
		}
	}
	int query(char buf[]){
		int m=strlen(buf);
        int now=root,ans=0;
		for(int i=0;i

多叉樹の階層順は、＋統計的な多叉葉っぱノード1004 Counting Leaves(30分)を通過する.