草，调了一年发现我把串的个数当总串长写了……
我寻思我写 CF666E 的时候就注意到这个问题了呀（
线段树合并求出每个状态在多少个字符串里出现了，并标记有哪些状态是出现至少 \(k\) 次的。
那么对于每个串，从每个前缀往上跳 Parent Tree 计算符合条件的子串的个数即可。
然而暴力跳复杂度显然很危险（
然而实际上可以直接从根向下 DP 预处理出个数（
然而实际上只需要向上找一个最深的符合条件的状态即可，因为符合条件在树链上显然有单调性（
代码： 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
using namespace std;
const int N = 1e5;
int n,k;
char s[N + 5];
int ed[N + 5],pos[N + 5],tot;
long long ans[N + 5];
namespace SEG
{
struct node
{
int sum;
int ls,rs;
} seg[(N << 5) + 10];
int tot;
void insert(int x,int &p,int tl,int tr)
{
!p && (p = ++tot);
if(tl == tr)
{
seg[p].sum |= 1;
return ;
}
int mid = tl + tr >> 1;
x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
seg[p].sum = seg[seg[p].ls].sum + seg[seg[p].rs].sum;
}
int merge(int p,int q,int tl,int tr)
{
if(!p || !q)
return p | q;
if(tl == tr)
{
seg[p].sum |= seg[q].sum;
return p;
}
int mid = tl + tr >> 1;
seg[p].ls = merge(seg[p].ls,seg[q].ls,tl,mid),seg[p].rs = merge(seg[p].rs,seg[q].rs,mid + 1,tr);
seg[p].sum = seg[seg[p].ls].sum + seg[seg[p].rs].sum;
return p;
}
}
namespace SAM
{
struct node
{
int ch[26];
int fa,len,rt;
} sam[(N << 1) + 5];
int las = 1,tot = 1;
int c[N + 5],a[(N << 1) + 5];
int vis[(N << 1) + 5],f[(N << 1) + 5];
inline void insert(int x,int pos)
{
if(sam[las].ch[x] && sam[las].len + 1 == sam[sam[las].ch[x]].len)
{
SEG::insert(pos,sam[las = sam[las].ch[x]].rt,1,n);
return ;
}
int cur = las,p = ++tot,flag = 0,nxt;
sam[p].len = sam[cur].len + 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
cur == las && (flag = 1),nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].rt = 0;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
SEG::insert(pos,sam[las = flag ? nxt : p].rt,1,n);
}
inline void build()
{
for(register int i = 1;i <= tot;++i)
++c[sam[i].len];
for(register int i = 1;i <= N;++i)
c[i] += c[i - 1];
for(register int i = tot;i > 1;--i)
a[c[sam[i].len]--] = i;
for(register int i = tot;i > 1;--i)
SEG::seg[sam[a[i]].rt].sum >= k && (vis[a[i]] = 1),sam[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt,1,n);
for(register int i = 2;i <= tot;++i)
f[a[i]] = vis[a[i]] ? sam[a[i]].len : f[sam[a[i]].fa];
}
}
int main()
{
scanf("%d%d",&n,&k);
for(register int i = 1;i <= n;++i)
{
scanf("%s",s),SAM::las = 1;
for(char *c = s;*c;SAM::insert(*c++ - 'a',i),ed[++tot] = SAM::las,pos[tot] = i);
}
SAM::build();
for(register int i = 1;i <= tot;++i)
ans[pos[i]] += SAM::f[ed[i]];
for(register int i = 1;i <= n;++i)
printf("%lld%c",ans[i]," \n"[i == n]);
}