题目描述

某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。

输入

第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6

输出

输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

样例输入

3

a

aa

aaa

样例输出

6

3

1

---

题解

AC自动机

由fail的定义，可知，求出现次数，就是求有多少个节点可以通过fail链到达目标串末端的位置。

那么我们可以建立一棵fail树，每个节点的子树都包含目标串。

那么答案就变成了子树中所有前缀出现的次数。

把每个字符串的每个节点权值+1，最后向上递推即可。

#include 
     
      #include 
      
       #include 
       
        using namespace std;queue
        
          q;int nt[201][26] , cnt[201] , tot = 1;bool f[1000001];char str[1000001];int main(){    int n , m , i , j , l , t , ans;    scanf("%d%d" , &n , &m);    while(n -- )    {        scanf("%s" , str);        l = strlen(str);        t = 1;        for(i = 0 ; i < l ; i ++ )        {            if(!nt[t][str[i] - 'a'])                nt[t][str[i] - 'a'] = ++tot;            t = nt[t][str[i] - 'a'];        }        cnt[t] ++ ;    }    while(m -- )    {        scanf("%s" , str);        l = strlen(str);        memset(f , 0 , sizeof(f));        f[0] = 1;        for(i = 0 ; i < l ; i ++ )        {            if(f[i])            {                t = 1;                j = i;                while(nt[t][str[j] - 'a'])                {                    t = nt[t][str[j ++ ] - 'a'];                    if(cnt[t]) f[j] |= f[i];                }            }                }        for(i = 0 ; i <= l ; i ++ )            if(f[i])                ans = i;        printf("%d\n" , ans);    }    return 0;}