HDU2222-Keywords Search

Keywords Search

Problem Description

In the modern time, Search engine came into the life of everybody 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 image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

Input

First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords 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 1000000.

Output

Print how many keywords are contained in the description.

Sample Input

1
5
she
he
say
shr
her
yasherhs

Sample Output

3

题解：

这道题可以说是AC自动机的模板题，什么是AC自动机，AC自动机是一个多模字符串匹配算法，是利用tire(字典树)和KMP算法结合的一个算法，快速找出一段字符串中出现过多少个我们给出的单词，避免回溯的一个搞笑算法，所以在学习这个算法的时候需要提前了解一下tire树和KMP算法。

AC自动机的第一步是建tire字典树，如何建字典树呢？

下面引用别人博客的图片和代码来解释：

(引用： https://blog.csdn.net/bestsort/article/details/82947639 )

例如给定几个模式串： “ash”,“shex”,“bcd”,“sha”

代码：

//新建节点
struct node{
	node *fail;//失败节点 
	node *next[26];//下一个节点 
	int count;//是否为单词末尾 
	node(){//初始化 
		fail=NULL;
		count=0;
		for(int i=0;i<26;i++){
			next[i]=NULL;
		}
	}
}*q[N];

//创建字典树tire 
void buildtire(char *s){ 
	node *p=root;
	int temp;
	int len=strlen(s);
	for(int i=0;i<len;i++){
		temp=s[i]-'a';
		if(p->next[temp]==NULL)//如果节点不存在，新建节点 
			p->next[temp]=new node();
		p=p->next[temp];
	}
	p->count++;
}

创建字典树应该挺简单的，所以略过，重点是讲fail指针。

fail指针的含义和KMP算法的next数组含义一样，是为了避免匹配失败的时候回溯字符串。

从上图很容易看得出来，其实失败的时候就是为了跳到另一个字符串继续匹配。

比如ash，当匹配到s的时候，当下一个字符不是h，是e的时候，ash匹配失败了，但是我as匹配过了，我可以利用这个信息去找前缀，我找到shex有一个s，那么我就不用匹配这个s,减少了一次匹配，然后继续找这个s有没有e，那没有e那就继续跳到别的地方继续找，这就是多模匹配算法的好处，不一定要从shex的s又开始匹配，提高了匹配效率。

当然我们建立完tire树的时候，还没有fail指针，我们需要自己建。那怎么建这个fail指针呢，我们用了BFS去建，喜闻见乐的模板又来了。

//BFS,建立fail指针 
void buildfail(){
	q[tail++]=root;
	while(head!=tail){
		node *p=q[head++];//取出队首元素 
		node *temp=NULL;
		for(int i=0;i<26;i++){
			if(p->next[i]!=NULL){//如果有这个字符 
				if(p==root)//如果当前节点是根节点，失配指针指向根节点 
					p->next[i]->fail=root;
				else{//如果不是根节点 
					temp=p->fail;//找到当前指针的失配指针 
					while(temp!=NULL){//当前指针的失配指针不为空(p->fail)
						if(temp->next[i]!=NULL){//如果当前指针的失配指针的next[i]不为空(p->fail->next[i])
							p->next[i]->fail=temp->next[i];//那么p->next[i]->fail=p->fail->next[i] 
							break;
						}
						temp=temp->fail;//当第一个找不到，找temp->fail，以此类推，公共前缀 
					}
					if(temp==NULL)//如果temp(p->fail)没有指向，即没有公共前缀，指向root 
						p->next[i]->fail=root;
				}
				q[tail++]=p->next[i];//入队 
			}
		}
	}
}

我们一步一步来模仿这个算法的过程：

1.root是根节点，没有什么作用，仅仅是一个入口（其实我也是东抄抄西抄抄）

2.开始扩展root，当前p是root，我们结合代码来跑一次，很明显当第一个字母都失配，那么p->next[i]->fail都指向root。

if(p==root)//如果当前节点是根节点，失配指针指向根节点 
    p->next[i]->fail=root;

3.到了第二层，开始扩展a，发现字母s，a不是根节点，所以执行下面的代码，

​ 3.1先找到当前a节点的失配指针（temp=p->fail），那么temp指向root，发现temp(即root)不为空

​ 3.2然后去找temp->next[i]，即temp有没有next[i]这个字母s，发现有这个字母s

​ 3.3然后另p->next[i]->fail=temp->next[i]；这样a的s的fail指针就指向了root的s

else{//如果不是根节点 
    temp=p->fail;//找到当前指针的失配指针 
    while(temp!=NULL){//当前指针的失配指针不为空(p->fail)
        if(temp->next[i]!=NULL){//如果当前指针的失配指针的next[i]不为空(p->fail->next[i])
            p->next[i]->fail=temp->next[i];//那么p->next[i]->fail=p->fail->next[i] 
            break;
        }
        temp=temp->fail;//当第一个找不到，找temp->fail，以此类推，公共前缀 
    }
    if(temp==NULL)//如果temp(p->fail)没有指向，即没有公共前缀，指向root 
        p->next[i]->fail=root;
}

以此类推，就可以得到下图：

建立完fail指针之后，我们就可以开始匹配字符串了。

匹配的过程很简单，那我们建好的tire树去匹配主字符串，如果失败就直接跳，算法效率出奇的高，直接上代码。

int query(){
	int index,len,result;
	node *p=root;
	result=0;
	len=strlen(str);
	for(int i=0;i<len;i++){
		index=str[i]-'a';
		while(p->next[index]==NULL&&p!=root)//判断str[i]在不在tire树中 
			p=p->fail;
		p=p->next[index];//p跳到p->next[index] 
		if(p==NULL)//如果没有下一个节点了 
			p=root;//p回到根，因为有没有失配节点，且没有下一个节点 
		node *temp=p;//匹配结束，进行判断 
		while(temp!=root&&temp->count!=-1){ 
			result+=temp->count;
			temp->count=-1;
			temp=temp->fail; 
		}	
	}
	return result;
}

这道题遇到了一个坑，刚开始直接用string去输入，发现怎么改都超时，一直找问题，没找出来，还是用字符数组才AC了。

AC代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 500010
using namespace std;
char str[1000010],keyword[51];
int head,tail;
//新建节点 
struct node{
	node *fail;//失败节点 
	node *next[26];//下一个节点 
	int count;//是否为单词末尾 
	node(){//初始化 
		fail=NULL;
		count=0;
		for(int i=0;i<26;i++){
			next[i]=NULL;
		}
	}
}*q[N];
//定义跟节点 
node *root; 

//创建字典树tire 
void buildtire(char *s){ 
	node *p=root;
	int temp;
	int len=strlen(s);
	for(int i=0;i<len;i++){
		temp=s[i]-'a';
		if(p->next[temp]==NULL)//如果节点不存在，新建节点 
			p->next[temp]=new node();
		p=p->next[temp];
	}
	p->count++;
}

//BFS,建立fail指针 
void buildfail(){
	q[tail++]=root;
	while(head!=tail){
		node *p=q[head++];//取出队首元素 
		node *temp=NULL;
		for(int i=0;i<26;i++){
			if(p->next[i]!=NULL){//如果有这个字符 
				if(p==root)//如果当前节点是根节点，失配指针指向根节点 
					p->next[i]->fail=root;
				else{//如果不是根节点 
					temp=p->fail;//找到当前指针的失配指针 
					while(temp!=NULL){//当前指针的失配指针不为空(p->fail)
						if(temp->next[i]!=NULL){//如果当前指针的失配指针的next[i]不为空(p->fail->next[i])
							p->next[i]->fail=temp->next[i];//那么p->next[i]->fail=p->fail->next[i] 
							break;
						}
						temp=temp->fail;//当第一个找不到，找temp->fail，以此类推，公共前缀 
					}
					if(temp==NULL)//如果temp(p->fail)没有指向，即没有公共前缀，指向root 
						p->next[i]->fail=root;
				}
				q[tail++]=p->next[i];//入队 
			}
		}
	}
}
int query(){
	int index,len,result;
	node *p=root;
	result=0;
	len=strlen(str);
	for(int i=0;i<len;i++){
		index=str[i]-'a';
		while(p->next[index]==NULL&&p!=root)//判断str[i]在不在tire树中 
			p=p->fail;
		p=p->next[index];//p跳到p->next[index] 
		if(p==NULL)//如果没有下一个节点了 
			p=root;//p回到根，因为有没有失配节点，且没有下一个节点 
		node *temp=p;//匹配结束，进行判断 
		while(temp!=root&&temp->count!=-1){ 
			result+=temp->count;
			temp->count=-1;
			temp=temp->fail; 
		}	
	}
	return result;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		root=new node();
		head=tail=0;
		int n;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>keyword;
			buildtire(keyword);
		}
		buildfail();
		scanf("%s",str);
		cout<<query()<<endl;
	}
	return 0;
}