BZOJ3277 串

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 2.9k | 阅读时长 ≈ 3 分钟

BZOJ3277 串

传送门

BZOJ

题目描述

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

输入输出格式

输入格式：

第一行两个整数$n$，$k$。
接下来$n$行每行一个字符串。
$n,k,l \le 100000$

输出格式：

输出一行$n$个整数，第$i$个整数表示第$i$个字符串的答案。

输入输出样例

输入样例：

3 1
abc
a
ab

输出样例：

6 1 3

分析

广义$SAM$模板题(应该是)。
不知道为什么，用了快读读数字，再用cin读string就爆炸了。

参考资料

广义$SAM$

dwjshift的 用SAM建广义后缀树 提供在线和离线建法。话说这篇资料里提到的不在Trie上建$SAM$是怎么做的？？？
wangzhen_yu的 广义后缀自动机 提供很好的例题及代码讲解。以前不懂什么叫进行内容更新，菜啊
phile的 关于广义后缀树（多串SAM）的总结

本题

自为风月马前卒的题解 主要参考题解，这篇题解是枚举前缀的后缀(即子串)进行内容更新，而不是插入时更新，换句话说，这篇题解是从上至下更新，而不是一般的插入时从下至上更新。
clover_hxy的 题解 这篇题解是在建自动机的时候统计的每个状态的出现次数，最后求答案时连边跳，不过没看懂其中的mark数组是干什么的。

代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,m,las,cnt=1,times[maxn<<1],sum[maxn<<1],vis[maxn<<1],len[maxn<<1],fa[maxn<<1],ch[maxn<<1][26];
string str[maxn];
void add(int cc)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1;
	for(;p&&!ch[p][cc];p=fa[p])ch[p][cc]=np;
	if(!p)fa[np]=1;
	else
	{
		int q=ch[p][cc];
		if(len[q]==len[p]+1)fa[np]=q;
		else
		{
			int nq=++cnt;
			fa[nq]=fa[q];
			len[nq]=len[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[q]=fa[np]=nq;
			for(;p&&ch[p][cc]==q;p=fa[p])ch[p][cc]=nq;
		}
	}
}
void dfs(int x)
{
	if(!x||vis[x])return ;
	vis[x]=true;
	dfs(fa[x]);
	sum[x]+=sum[fa[x]];
}
void GetTimes()
{
	for(int i=1;i<=n;i++)
	{
		int now=1;
		for(int j=0;j<(int)str[i].length();j++)
		{
			now=ch[now][str[i][j]-'a'];
			int tmp=now;
			while(tmp&&vis[tmp]!=i)
			{
				vis[tmp]=i;
				times[tmp]+=1;
				tmp=fa[tmp];
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		las=1;
		cin>>str[i];
		for(int j=0;j<(int)str[i].length();j++)add(str[i][j]-'a');
	}
	GetTimes();
	for(int i=1;i<=cnt;i++)sum[i]=(times[i]>=m)*(len[i]-len[fa[i]]);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=cnt;i++)dfs(i);
	for(int i=1;i<=n;i++)
	{
		int ans=0,now=1;
		for(int j=0;j<(int)str[i].length();j++)
			now=ch[now][str[i][j]-'a'],ans+=sum[now];
		printf("%d ",ans);
	}
    return 0;
}