【1】+【2】我们已经入门了后缀自动机, 并且给出了后缀自动机 O(n) 的构造算法. 现在继续前行. hihocoder #1449 : 后缀自动机三·重复旋律6
时间限制:15000ms
单点时限:3000ms
内存限制:512MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的,小Hi想知道对
于所有的K的答案。
输入
共一行,包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。
输出
共Length(S)行,每行一个整数,表示答案。
样例输入
aab
样例输出
2
1
1
hint
长度为1的子串出现次数最多的是a, 出现次数是2.
长度为2的子串出现次数最多的是aa(当然,不唯一, 也可以是ab), 出现次数是1
长度为3的子串出现次数最多的是aab,出现次数是1
所以输出
2
1
1
本题是SAM的运用. 通过【1】的学习, 我们知道了一个字符串S的后缀自动机其实是一部用于识别S的所有子串的机器, 而且通过【2】进一步的学习, 我们知道如果一个字符串不是S的子串的话, 则将其一个字符一个字符的喂进SAM中的话, 则将必定在喂入某个字符的时候出现无路可走的情况(即喂入字符c, trans[c]=null, 而不能正确的转移到sam的某个节点去). 换言之, 文本串S的后缀自动机是一部恰好只能识别S的全部子串的机器!
那本题该如何求解呢? 毫无疑问, 先构建S的sam. 我们首先断言, 如果能求出sam中每个节点的enspos集合的大小, 那么此题至少有如下暴力解法. 因为我们完全可以写出如下伪代码
FOREACH State st:
FOR i = shortest(st) .. longest(st):
ans[i] = max(ans[i], |endpos(st)|)
其中ans[i] 表示出现次数最多的长度为i的子串的出现次数. 复杂度是O(N^2)的. 至于如何优化, 我们后面再说. 先至少保证能写出这个暴力算法来. 后面再优化复杂度.
那么SAM的每个节点的endpos的大小怎么求出来呢? 我们还是以 S="aabbabd" 为例, 它的SAM如下(这个在【1】中已经画过了)
image
然后我们将trans去掉, 仅仅考虑slink. 则我们发现SAM在slink下形成了一棵以起点0为根的树(一定是一棵有根树, 因为回想一下【1】中slink是怎么形成的? 不就是不断的删掉字符最终删光了走到节点0么? ).
然后各个节点如下
状态 | 子串 | endpos |
---|---|---|
S | 空串 | {0,1,2,3,4,5,6,7} |
1 | a | {1,2,5} |
2 | aa | {2} |
3 | aab | {3} |
4 | aabb,abb,bb | {4} |
5 | b | {3,4,6} |
6 | aabba,abba,bba,ba | {5} |
7 | aabbab,abbab,bbab,bab | {6} |
8 | ab | {3,6} |
9 | aabbabd,abbabd,bbabd,babd,abd,bd,d | {7} |
注意, 图2中除了起点0之外, 其余的9个顶点被着以两种颜色——一种是浅粉色, 一种是绿色. 绿色的节点表示是【2】中代码第28行新建的节点z——即S[1,...,i+1]所属的节点(【2】中的附录图1中的z), 换言之是每次新读入字符产生的新的前缀属于的节点. 而浅粉色的节点是【2】中代码48行从x拆分出来的y(【2】中的附录图3中的y), 换言之, 是拆分出来的节点. 也就是S的sam节点的个数>=S的长度. 多出来的都是拆分出来的节点. 例如上图中的5和8就是就是拆分出来的节点.
很明显的事情是, 绿色的节点中一定包含前缀, 而且前缀就是该节点中最长的那个子串(根据【2】的代码就知道).而浅粉色节点中一定不包含前缀, 因为浅粉色的节点(即【2】中的y)是【2】中的u=S[1,..,i]不断的删除前面的字符走到的节点v然后再读入S[i+1]这个字符产生的节点. 既然已经删掉了一些前面的字符, 当然不可能是前缀啦~
因为刚刚说了, sam用slink已经形成了一棵有根树. 所以我们寻思着能不能构造完毕sam之后, 再自底向上递归地将每个 顶点的endpos大小求出来. 我们想当然的认为 父节点的endpos大小恰好等于所有子节点们的endpos大小之和 (下面简称这个断言为A). 然鹅, 事实上, 这是不正确的.
例子1:
状态8有两个儿子分别是状态3和状态7(即slink[7]=slink[3]=8),其中endpos(3)={3}, endpos(7)={6},
endpos(8) = {3,6}, 所以 |endpos(8)| = |endpos(3)| + |endpos(7)|, 没毛病~
例子2:
状态1有两个儿子分别是状态2和状态6,其中endpos(2)={2}, endpos(6)={5},but endpos(1)={1,2,5}
所以 |endpos(1)| > |endpos(2)| + |endpos(6)|
所以父节点的enpos大小=子节点们的endpos大小之和并不成立! 那是不是我们不能利用上面优美的树形结构了呢? 非也, 非也, 情况事实上没有辣么的糟糕!
结论: 对于浅粉色的节点, A是成立的, 对于绿色的节点, A是不成立的, 而要将A的叙述改成
父节点的endpos大小恰好等于所有子节点们的endpos大小之和再加1, 而且加的这个1就是父节点中的最长的那个
子串————也就是前缀S[1,...,i].
为什么上面的结论对呢? 首先根据【1】的引理, 我们知道父节点的诸多子节点之间是不可能endpos交非空的. 否则这些子节点之间就存在后缀关系, 这些子节点之间就会存在slink关系. 就不会是兄弟关系了. 其次, 如果父节点的endpos中存在一个不在任何子节点的endpos中出现的值, 假设这个值是q, 并且产生这个q的父节点中的子串是sub = S[p,..,q], 则如果p>1(浅粉色节点)的话, 可以想象sub一定会属于某个子节点的! 除非p=1(绿色节点), 即产生这个q的是一个前缀! 那么根据我们sam的构造算法, 就不可能属于任何一个子节点!
这就是为什么我们要区分浅粉色节点和绿色节点的理由!
那么既然是树上的递归, 我们还有一个要考虑的问题就是叶子节点的值是多少? 我们说 ,叶子节点的endpos大小一定是1. 因为节点就只有浅粉色和绿色两种, 而浅粉色节点是拆分出来的节点, 根据【2】中的构造算法, 浅粉色的节点一定不可能是叶子. 所以叶子只可能是绿色节点(简称绿叶). 绿叶一定不可能endpos的大小>1, 否则说明绿叶中最长的那个子串——即前缀S[1,...,i]出现次数>1——即不仅仅在i处出现, 还在j处出现, 显然j>i. 那么考虑S[1,..,j]所在的节点. 则不难知道此绿叶必定不是叶子节点了. 所以叶子的endpos的大小一定是 1
至此, 我们知道了如何得到每个sam节点中的endpos大小的算法.
注意, 上面三步的复杂度是O(N)的. 而且因为自动机的节点数至多2N个, 所以不难知道上面三步算法的常数比较小. 是很优秀的.
那么怎么得到答案呢? 如果使用本文开头的暴力算法的话, 复杂度堕入O(n^2) 那岂不是迄今为止slink树的努力全部白费了? 非也非也!
对于每个节点, 我们不需要去更新节点所有的子串对应长度的答案, 也就是我们不需要对每个节点执行下面的O(n)伪代码
FOR i = shortest(st) .. longest(st):
ans[i] = max(ans[i], |endpos(st)|)
只需要更新节点中的longest对应的答案就行了. 即对每个节点, 只需要执行下面的O(1)伪代码即可
ans[maxlen(st)] = max(ans[maxlen(st)], |endpos(st)|)
然后注意到ans[1], ans[2], ... ans[length(S)]一定递减(因为一个长度为i的子串出现了, 则长度为i-1、i-2、...、1的子串一定也都出现了). 所以我们只需要继续
FOR i = length(S) - 1 .. 1:
ans[i] = max(ans[i], ans[i+1])
即可。还是以 S="aabbabd"为例. 我们要求 ans[4]. 那么根据上面的表格, 我们知道长为4的子串在4、6、7、9 这四个节点中出现过. 所以按道理, ans[4]应该在遍历4、6、7、9这4个状态的时候, 对于每个状态st, 来一次
ans[4] = max(ans[4], endpos(st))
这个过程就是文初的O(n^2)暴力算法. 但是其实没必要. 因为例如 abba 这个长度为4的子串在6这个状态出现过. 但是它的endpos和longest(6) = aabba 是一毛一样的! 所以我们只需要得到 ans[5]即可. 然后用ans[5]来max化 ans[4].
综上所述, 我们应该使用下面的伪代码来完成对答案的计算
FOREACH State st:
ans[longest(st)] = max(ans[longest(st)], |endpos(st)|) // 只更新longest的
FOR i = length(S) - 1 .. 1:
ans[i] = max(ans[i], ans[i+1])
上述伪代码的复杂度是O(n)的.
好了, 说了这么多, 来愉快的切代码吧~
//#include "stdafx.h"
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
//#define LOCAL
typedef long long ll;
const int maxn = 1e6+5, SZ = 26;
int n, head[maxn<<1], cnt;
char s[maxn];
ll ans[maxn];
struct SamNode
{
int trans[SZ], slink;
int longest, shortest, endpos; // endpos 表示该节点的endpos集合的大小
bool flag; // 是不是绿色节点? true表示是, false表示不是
}sam[maxn<<1];
struct Arc
{
int from, to, nxt;
}g[maxn<<1];
void addarc(int from, int to)
{
g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from];
head[from] = cnt++;
}
int newnode(int shortest, int longest, int *trans, int slink, bool flag)
{
sam[n].shortest = shortest;
sam[n].longest = longest;
sam[n].slink = slink;
sam[n].flag = flag;
sam[n].endpos = sam[n].flag; // 如果是绿色节点的话, 则等于子节点的endpos之和再加1, 否则等于子节点之和
trans?memcpy(sam[n].trans, trans, SZ*sizeof(int)):memset(sam[n].trans, -1, SZ*sizeof(int));
return n++;
}
int insert(char ch, int u)
{
int c = ch - 'a';
int z = newnode(-1, sam[u].longest + 1, 0, -1, true); // 绿色
int v = u;
while(~v && !~sam[v].trans[c])
{
sam[v].trans[c] = z;
v = sam[v].slink;
}
if (!~v)
{
sam[z].shortest = 1;
sam[z].slink = 0;
return z;
}
int x = sam[v].trans[c];
if (sam[x].longest == sam[v].longest + 1)
{
sam[z].shortest = sam[x].longest + 1;
sam[z].slink = x;
return z;
}
int y = newnode(-1, sam[v].longest+1, sam[x].trans, sam[x].slink, false); // 浅粉色
sam[x].slink = y;
sam[x].shortest = sam[y].longest + 1;
sam[z].slink = y;
sam[z].shortest = sam[y].longest + 1;
while (~v && sam[v].trans[c] == x)
{
sam[v].trans[c] = y;
v = sam[v].slink;
}
sam[y].shortest = sam[sam[y].slink].longest + 1;
return z;
}
void slinktree()
{
memset(head, -1, sizeof(head));
for (int i = 1, to; i < n; i++)
{
to = sam[i].slink;
if (~to)
{
addarc(to, i);
}
}
}
void dfs(int cur)
{
for (int h = head[cur], to; ~h; h = g[h].nxt)
{
to = g[h].to;
dfs(to);
sam[cur].endpos += sam[to].endpos;
}
}
inline void mmax(ll &a,ll b)
{
if (a<b)
{
a = b;
}
}
int main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
freopen("d:\\my.out", "w", stdout);
#endif
scanf("%s", s+1);
int u = newnode(0,0,0,-1, true),i = 1, len = strlen(s+1);
while(s[i])
{
u = insert(s[i], u);
++i;
}
slinktree(); // 利用反向slink弧构建slink树
dfs(0); // 树上dfs求所有节点的endpos
for (int i = 1;i<n; i++)
{
mmax(ans[sam[i].longest], sam[i].endpos);
}
for (int i = len - 1; i; i--)
{
mmax(ans[i], ans[i+1]);
}
for (int i = 1;i<=len; i++)
{
printf("%lld\n", ans[i]);
}
return 0;
}
ac情况
Accepted