题意

现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。

题解

首先是广义后缀自动机，就是每次将$last$归为$Root$，从而将几个后缀自动机拼在一起处理

那么现在需要知道每个字串在$n$个母串中的出现次数，所谓字串，就是所有前缀的所有后缀，所以可以顺着前缀走，那么通过$Parent$树找后缀，一直往上跳，那么需要加一的所有后缀就是所属母串并非当前母串的那几个

此时再整理出每个所属母串个数$Size >= K$的初始贡献，即$Len[i] - Len[Father[i]]$，反之赋$0$

又子串为前缀的后缀，那么一个节点的贡献即为它祖先至它本身的贡献前缀和，即它所有后缀能够构成的子串数

最后再遍历一遍前缀统计答案即可

代码

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6   7 using namespace std;  8    9 typedef long long LL; 10   11 const int MAXN = 6e05 + 10; 12   13 int N, K; 14 string Str[MAXN >> 2]; 15  16 const int Root = 1; 17 int Tree[MAXN][30]= {
    0}; 18 int Father[MAXN]= {
    0}; 19 int Len[MAXN]= {
    0}, Size[MAXN]= {
    0}; 20 int Belong[MAXN]= {
    0}; 21 int last = Root, nodes = 1; 22 void Append (int c, int bel) { 23     int fa = last, p = ++ nodes; 24     last = p; 25     Len[p] = Len[fa] + 1; 26     while (fa && ! Tree[fa][c]) 27         Tree[fa][c] = p, fa = Father[fa]; 28     if (! fa) 29         Father[p] = 1; 30     else { 31         int x = Tree[fa][c]; 32         if (Len[x] == Len[fa] + 1) 33             Father[p] = x; 34         else { 35             int np = ++ nodes; 36             Len[np] = Len[fa] + 1, Father[np] = Father[x]; 37             Father[p] = Father[x] = np; 38             memcpy (Tree[np], Tree[x], sizeof (Tree[x])); 39             while (fa && Tree[fa][c] == x) 40                 Tree[fa][c] = np, fa = Father[fa]; 41         } 42     } 43 } 44 int Topo[MAXN]; 45 int W[MAXN]= {
    0}; 46 int buck[MAXN]= {
    0}; 47 void Merge () { 48     for (int i = 1; i <= N; i ++) { 49         int n = Str[i].size(); 50         int p = Root; 51         for (int j = 0; j < n; j ++) { 52             p = Tree[p][Str[i][j] - 'a']; 53             int fa = p; 54             while (fa && Belong[fa] != i) { 55                 Size[fa] ++; 56                 Belong[fa] = i; 57                 fa = Father[fa]; 58             } 59         } 60     } 61     for (int i = 1; i <= nodes; i ++) 62         buck[Len[i]] ++; 63     for (int i = 1; i <= nodes; i ++) 64         buck[i] += buck[i - 1]; 65     for (int i = nodes; i >= 1; i --) 66         Topo[buck[Len[i]] --] = i; 67     for (int i = 1; i <= nodes; i ++) 68         if (Size[i] >= K) 69             W[i] = Len[i] - Len[Father[i]]; 70     for (int i = 1; i <= nodes; i ++) 71         W[Topo[i]] += W[Father[Topo[i]]]; 72 } 73   74 LL Answer[MAXN >> 2]= {
    0}; 75   76 int main () { 77     scanf ("%d%d", & N, & K); 78     for (int i = 1; i <= N; i ++) { 79         cin >> Str[i]; 80         int n = Str[i].size(); 81         last = Root; 82         for (int j = 0; j < n; j ++) 83             Append (Str[i][j] - 'a', i); 84     } 85     Merge (); 86     for (int i = 1; i <= N; i ++) { 87         int n = Str[i].size(); 88         int p = Root; 89         for (int j = 0; j < n; j ++) 90             p = Tree[p][Str[i][j] - 'a'], Answer[i] += W[p]; 91     } 92     for (int i = 1; i <= N; i ++) { 93         if (i > 1) 94             putchar (' '); 95         printf ("%lld", Answer[i]); 96     } 97     puts (""); 98   99     return 0;100 }101  102 /*103 3 1104 abc105 a106 ab107 */108 109 /*110 2 2111 aa112 aaa113 */