//众神云集、群魔乱舞、以一抵百、砥砺前行//Keywords Search------AC自动机///内含模板

旧城等待， 2023-03-13 13:01 18阅读 0赞

## 题目描述 ##

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自动机的模板题，这题要注意的地方在于初始化，一定要注意初始化的完全。

## 学到了什么 ##

通过这道模板题，我了解到了以下  
1.  
代码一：

int len=strlen(str);
    for(int i=0;i<str;i++)

代码二：

for(int i=0;i<strlen(str);i++)

代码一花费的时间比代码二少。  
原因在于strlen函数的时间复杂度为O(n)，而代码一只需要执行一次该函数，而代码二每次循环一次，就要进行一次判断，而每进行一次判断，就要调用该函数一次。所以综上比较，代码一的时间复杂度比代码二要小。  
平时都是为了偷懒少写，所以平时写的代码都是写的代码二这种情形，但是后来经过了多次的TL发现必须要改正这种习惯。  
·  
·  
·  
·  
·  
下面是模板部分  
预定义如下

int trie[maxn][27];
    int is_alpha[maxn];
    int fail[maxn];
    int tot=0;
    char str[maxn];

2.字典树建树模板

void build_trie()
    {
        
        int root=0;
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
        
            int id=str[i]-'a';
            if(!trie[root][id])
                trie[root][id]=++tot;
            root=trie[root][id];
        }
        is_alpha[root]++;
    }

3.获取fail数组模板

void get_fail()
    {
        
        queue<int> p;
        for(int i=0; i<26; i++)
            if(trie[0][i])
                p.push(trie[0][i]);
        while(!p.empty())
        {
        
            int x=p.front();
            p.pop();
            for(int i=0; i<26; i++)
            {
        
                if(trie[x][i])
                {
        
                    fail[trie[x][i]]=trie[fail[x]][i];
                    p.push(trie[x][i]);
                }
                else
                    trie[x][i]=trie[fail[x]][i];
            }
        }
    }

4.询问函数

int query()
    {
        
        int root=0,ans=0;
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
        
            root=trie[root][str[i]-'a'];
            for(int j=root; j&&~is_alpha[j]; j=fail[j])
            {
        
                ans+=is_alpha[j];
                is_alpha[j]=-1;
            }
        }
        return ans;
    }

5.初始化函数

void init()
    {
        
        memset(fail,0,sizeof(fail));
        for(int i=0; i<=tot; i++)
        {
        
            is_alpha[i]=0;
            for(int j=0; j<26; j++)
                trie[i][j]=0;
        }
        tot=0;
    }

## 代码如下 ##

//------------------------------AC automachine--------------------------------//
    //*            //-------众神云集、群魔乱舞、以一抵百、砥砺前行---------//       *//
    //-----------------------------Acmer LEO 到此一游------------------------------//
    //#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    #define maxn 1000005
    #define ll long long
    int trie[maxn][27];
    int is_alpha[maxn];
    int fail[maxn];
    int tot=0;
    char str[maxn];
    void build_trie()
    {
        
        int root=0;
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
        
            int id=str[i]-'a';
            if(!trie[root][id])
                trie[root][id]=++tot;
            root=trie[root][id];
        }
        is_alpha[root]++;
    }
    void get_fail()
    {
        
        queue<int> p;
        for(int i=0; i<26; i++)
            if(trie[0][i])
                p.push(trie[0][i]);
        while(!p.empty())
        {
        
            int x=p.front();
            p.pop();
            for(int i=0; i<26; i++)
            {
        
                if(trie[x][i])
                {
        
                    fail[trie[x][i]]=trie[fail[x]][i];
                    p.push(trie[x][i]);
                }
                else
                    trie[x][i]=trie[fail[x]][i];
            }
        }
    }
    int query()
    {
        
        int root=0,ans=0;
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
        
            root=trie[root][str[i]-'a'];
            for(int j=root; j&&~is_alpha[j]; j=fail[j])
            {
        
                ans+=is_alpha[j];
                is_alpha[j]=-1;
            }
        }
        return ans;
    }
    void init()
    {
        
        memset(fail,0,sizeof(fail));
        for(int i=0; i<=tot; i++)
        {
        
            is_alpha[i]=0;
            for(int j=0; j<26; j++)
                trie[i][j]=0;
        }
        tot=0;
    }
    int main()
    {
        
        int T;
        scanf("%d",&T);
        while(T--)
        {
        
            int n;
            scanf("%d",&n);
            for(int i=0; i<n; i++)
            {
        
                scanf("%s",str);
                build_trie();
            }
            get_fail();
            scanf("%s",str);
            printf("%d\n",query());
            init();
        }
        return 0;
    }