题意

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

题解

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

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

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

typedef long long LL;

const int MAXN = 6e05 + 10;

int N, K;
string Str[MAXN >> 2];

const int Root = 1;
int Tree[MAXN][30]= {0};
int Father[MAXN]= {0};
int Len[MAXN]= {0}, Size[MAXN]= {0};
int Belong[MAXN]= {0};
int last = Root, nodes = 1;
void Append (int c, int bel) {
    int fa = last, p = ++ nodes;
    last = p;
    Len[p] = Len[fa] + 1;
    while (fa && ! Tree[fa][c])
        Tree[fa][c] = p, fa = Father[fa];
    if (! fa)
        Father[p] = 1;
    else {
        int x = Tree[fa][c];
        if (Len[x] == Len[fa] + 1)
            Father[p] = x;
        else {
            int np = ++ nodes;
            Len[np] = Len[fa] + 1, Father[np] = Father[x];
            Father[p] = Father[x] = np;
            memcpy (Tree[np], Tree[x], sizeof (Tree[x]));
            while (fa && Tree[fa][c] == x)
                Tree[fa][c] = np, fa = Father[fa];
        }
    }
}
int Topo[MAXN];
int W[MAXN]= {0};
int buck[MAXN]= {0};
void Merge () {
    for (int i = 1; i <= N; i ++) {
        int n = Str[i].size();
        int p = Root;
        for (int j = 0; j < n; j ++) {
            p = Tree[p][Str[i][j] - 'a'];
            int fa = p;
            while (fa && Belong[fa] != i) {
                Size[fa] ++;
                Belong[fa] = i;
                fa = Father[fa];
            }
        }
    }
    for (int i = 1; i <= nodes; i ++)
        buck[Len[i]] ++;
    for (int i = 1; i <= nodes; i ++)
        buck[i] += buck[i - 1];
    for (int i = nodes; i >= 1; i --)
        Topo[buck[Len[i]] --] = i;
    for (int i = 1; i <= nodes; i ++)
        if (Size[i] >= K)
            W[i] = Len[i] - Len[Father[i]];
    for (int i = 1; i <= nodes; i ++)
        W[Topo[i]] += W[Father[Topo[i]]];
}

LL Answer[MAXN >> 2]= {0};

int main () {
    scanf ("%d%d", & N, & K);
    for (int i = 1; i <= N; i ++) {
        cin >> Str[i];
        int n = Str[i].size();
        last = Root;
        for (int j = 0; j < n; j ++)
            Append (Str[i][j] - 'a', i);
    }
    Merge ();
    for (int i = 1; i <= N; i ++) {
        int n = Str[i].size();
        int p = Root;
        for (int j = 0; j < n; j ++)
            p = Tree[p][Str[i][j] - 'a'], Answer[i] += W[p];
    }
    for (int i = 1; i <= N; i ++) {
        if (i > 1)
            putchar (' ');
        printf ("%lld", Answer[i]);
    }
    puts ("");

    return 0;
}

/*
3 1
abc
a
ab
*/

/*
2 2
aa
aaa
*/