史上全网最清晰后缀自动机学习（五）后缀自动机和最长公共子串问题

缘起

最长公共子串（LCS）问题可谓是经典的问题了. 我们使用过DP、后缀树、后缀数组来解决过. 现在我们考虑后缀自动机和LCS问题的联系, 并且来看这一联系的典型例题—— hihocoder #1465 : 后缀自动机五·重复旋律8

分析

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

小Hi发现旋律可以循环，每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”，还可以
对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。

小Hi对此产生了浓厚的兴趣，他有若干段旋律，和一部音乐作品。对于每一段旋律，他想知道有多少在音乐作品中的
子串（重复便多次计）和该旋律是“循环相似旋律”。

解题方法提示

输入
第一行，一个由小写字母构成的字符串S，表示一部音乐作品。字符串S长度不超过100000。

第二行，一个整数N，表示有N段旋律。接下来N行，每行包含一个由小写字母构成的字符串str，表示一段旋律。所有
旋律的长度和不超过 100000。

输出
输出共N行，每行一个整数，表示答案。

样例输入
abac
3
a
ab
ca
样例输出
2
2
1

首先, 本题是涉及子串的题目, 所以考虑使用后缀自动机解决.

首先来理解一下题意.

这道题目让我们求的是若干串T在另一个长串S中各自作为子串出现的次数, 只是匹配的方式从完全相等变成了“循环同构”。如果匹配方式是完全相等的话, 则就可以使用AC自动机解决。

但是本题比较恶心的地方在于匹配的方式改成了循环同构. 比如T="abcd"的话，我们要判断4个串"abcd", "bcda", "cdab", "dabc"在S中出现的次数。

首先, 对于这种循环同构的问题, 有一个常见的技巧. 例如 T="abcd", 则将T改造成 T1 = "abcdabc"——即将 T[1,...,len(T)-1]拼在T的后面构成T1. 则T1中就很自然的包含了T="abcd"的所有4个循环同构了. 那么得到T1之后, 我们就只需要去研究T1和S之间的LCS（最长公共子串）问题了. 我们使用过后缀树、后缀数组研究过LCS的<=O(nlogn)算法. 现在很荣幸, 使用SAM也来切一次LCS问题.

现在, 我们开始考虑用后缀自动机解决串S和T的LCS问题.

首先我们构造S的sam, 然后对于i（1<=i<=len(T)）, 我们想要确定以T[i] 为结尾的LCS属于哪一个sam状态节点u以及最长能匹配多长l. 即对于每个1<=i<=len(T), 我们要确定最大的l, 使得 T[i-l+1,...,i] 也作为S的子串. 而S的sam是一部恰能识别所有S子串的机器（这个说法在【3】中已经说过了）. 所以我们其实就是要求最大的l, 使得 T[i-l+1,...,i]喂入S的sam之后不会出现无路可走的情况, 即一定能最终停留在某个SAM的节点处.

现在我们从T[1]开始, 一个一个字符T[i]的喂S的后缀自动机吃. 期间维护两个变量u和l, 其中l是最大的使得T[i-l+1,...,i]能读入sam之后不会出现无路可走的情况的数. u是T[i-l+1,...,i]所属的sam节点.

我们依旧归纳的考虑这个问题.

最开始时, 我们得到了空串的u和l, 显然, u = 0, l = 0

假设我们已经得到了 T[i] 为结尾的最长匹配串——长为l, 并且SAM读入此匹配串T[i-l+1,...,i]之后将停留在sam的节点u。则 我们考虑以T[i+1]为结尾的最长匹配串.假设其长度为l1, 并且sam读入T[i+1-l1+1,..,i+1]之后sam将停留在u1节点.

其实在 【2】中已经用过了这个观点——就是T[i+1]为结尾的最长匹配串其实就是T[1,..,i]的某个后缀拼接上 T[i+1]而已. 而前缀T[1,...,i]的所有后缀其实就在slink-path(u)上（slink-path(u)的论述参见【2】）. 所以我们要想找到以 T[i+1]为结尾的最长匹配串, 其实只需要沿着slink-path(u)往0走, 遇到第一个读入T[i+1] 之后不会跳转到null（即无路可走）的节点. 假设这个节点是v, 即v.trans[T[i+1]-'a'] = x, x!=null, 那么 l1 = |longest(v)|+1 , u1=x （为了保证求最长, 这是显然的）

如果整条 slink-path(u) 一路上都没有节点v能使得读入T[i+1]这个字符之后能跳转到某个节点去而不至于无路可走的话, 则S中一定没有T[i+1]这个字符. 这也是显然的, 因为如果S中存在T[i+1]这个字符的话（假设S[b] = T[i+1]）, 至少0节点(0节点也在slink-path(u)上哦~)读入T[i+1]之后能走到一个合法节点吧~ 因为你考虑一下后缀S[b,...]就知道从0读入S[b] = T[i+1]之后就能跳到一个合法节点吧~ 如果S中不存在 T[i+1]这个字符的话, 则 T[i+1]为结尾的最长匹配串显然l1=0, u1 = 0（不能停留在后缀自动机的任何>0的合法顶点处）, 即回归起点重新开始了——继续读入T[i+2]去了.

所以我们使用SAM作为工具, 就O(|S|+|T|)时间内完美的解决了LCS问题。因为我们只需要取T[i]们中的最大l, 就知道LCS(S,T)长什么样子——T[i-l+1,...,i], 如果你想知道T[i-l+1,...,i]在S的哪个索引出现, 也是可以线性时间知道的. 大不了再做一次KMP（或者直接偷懒用c++ API strstr就行了）嘛~ 反正又不增加复杂度

至此, 使用后缀自动机解决LCS问题考虑完毕

现在想想看, 如何将上面的LCS问题的结论运用到本题中.我们说了, 首先使用T构造T1, 然后考虑LCS(S,T1)问题. 从T1[1]开始不断的喂入S的sam字符, 期间维护u和l（注意, 这里的u和l和上面的LCS问题的u和l的意义稍有不同, 这里的u和l除了满足T[i+1]为结尾的匹配串之外, 还要满足l>=n(这里n是T的长度)且 u包含后缀T[i+1-n+1,..,i+1]）. 找到此过程的v（v指什么, 见上面LCS的分析）之后, 令u是v读入T[i+1]之后跳转的节点. l要自增1（因为拼接上了T[i+1]嘛~）, 不要急, 此时, u和l还没求完,

如果l>=n的话, 则能保证T1[i+1-l+1,...,i+1]在u中, 既然l>=n, 则长度为n的子串T1[i+1-n+1,...,i+1]（即T的一个循环同构）是 T1[i+1-l+1,...,i+1]的后缀. 即 T1[i+1-n+1,...,i+1]是T1[i+1-l+1,...,i+1]删减字符（l=n的话, 则不需要删减字符）得到的结果. 所以T1[i+1-n+1,...,i+1]的endpos集合的大小（即出现的次数）>=T1[i+1-l+1,...,i+1]的endpos集合的大小=|u.endpos|. 所以我们并不能从sam节点u的endpos属性得到匹配串T1(i+1-n+1,...,i+1)出现的次数.

How?

显然, 如果l=n的话, T1(i+1-l+1,...,i+1)=T1(i+1-n+1,...,i+1), 所以T1(i+1-n+1,...,i+1)这个T的循环同构出现的次数就是u.endpos.则T[i+1]时的u和l就求完了. 如果l>n的话呢? 我们就要继续删减字符——即沿着slink-path(u)从v继续出发往0走, 直至 v是slink-path(u)上最后的那个满足v.longest>=n的v为止）. 则T1[i+1]对应的u和l就应该是这个最后的满足v.longest>=n的v（因为 T1[i+1-n+1,...,i+1]属于v节点）， 而l 应该是v.longest.

还有一个问题, 就是维护上述u和l完毕之后, 怎么更新答案的问题. 讲道理, 如果求解出了合理的u和l的话, 则答案应该增加 u.endpos——这很显然啊~ 因为合理的u和l意味着一个长度为n的T1的子串(其实就是T的一个循环同构)属于u节点, 而且u节点的endpos属性恰好就是u中任何一个子串在S中出现的次数. 所以答案要新增u.endpos.

但是如果T的循环同构有重复呢? 比如T=aa, 则T1=aaa, 则考虑T1[2]和T1[3]的u和l时候就会重复更新答案了——即重复统计aa 在S中出现的次数.

怎么办呢? 其实, T1[2-n+1] 和T1[3-n+1]（n=2） 是相同的两个子串（都是"aa"）, 所以沿着SAM走的话是会走到同一个节点u的. 但是我们只能让u.endpos更新一次的答案, 而不能用它更新2次. 所以自然的, 我们需要使用visited数组. 让一个节点u仅仅参与一次的更新答案. 这里就要回答一个问题——你怎么保证两次走到这个节点u的时候一定是T的相同的循环同构? 很简单——因为sam的性质——同一个节点中的子串长度是连续严格递减1的（参见【1】, 所以sam的数学结构得有多优美!）. 所以两个长度都为n的子串都走到sam的同一个节点一定是相同的子串, 也就是同一个循环同构, 所以要开一个bool的visited数组确保更新一次答案.

而一个节点的endpos大小在【4】中通过slink树的方法已经解决了.

另外, 本题的多串对于上述算法并没有什么影响~ 一个一个来就好了~

好了, 说了这么多. 开心的切代码好伐~

//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 1e5+5, SZ = 26;
char s[maxn],t[maxn<<1];
int n, len, head[maxn<<1], num;
bool vis[maxn<<1];

struct Arc
{
	int from, to, nxt;
}g[maxn<<1];

struct SamNode
{
	int trans[SZ], slink, longest, shortest;
	int endpos;
	bool flag;
}sam[maxn<<1];

void addarc(int from, int to)
{
	g[num].from = from, g[num].to = to, g[num].nxt = head[from];
	head[from] = num++;
}

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 = flag;
	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].slink = 0;
		sam[z].shortest = 1;
		return z;
	}
	int x = sam[v].trans[c];
	if (sam[v].longest + 1 == sam[x].longest)
	{
		sam[z].slink = x;
		sam[z].shortest = sam[x].longest + 1;
		return z;
	}
	int y = newnode(-1, sam[v].longest+1, sam[x].trans, sam[x].slink, false);
	sam[x].slink = sam[z].slink = y;
	sam[x].shortest = 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;
}

int kk()
{
	memset(vis, 0, sizeof(vis));
	int ans = 0, u = 0, l = 0, i = 1, c;
	while(t[i])
	{
		c = t[i]  - 'a';
		while(u && !~sam[u].trans[c])
		{
			u = sam[u].slink;
			l = sam[u].longest;
		}
		if (~sam[u].trans[c]) // 和ac自动机跳fail类似(参见【1】的58~62行以及77~81行)
		{
			u = sam[u].trans[c];
			++l;
		}
		else
		{
			u = l = 0; // 重新从0开始
		}
		if (l>len) // 不要急, 此时, u和l还没求完,
		{
			while(sam[sam[u].slink].longest>=len)
			{
				u = sam[u].slink;
				l = sam[u].longest;
			}
		} // 此时 u 和 l 已经求完了
		if (l>=len && !vis[u]) // 防止重复的循环同构重复计数
		{
			vis[u] = true;
			ans += sam[u].endpos;
		}
		++i;
	}
	return ans;
}

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;
	}
}

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;
	while(s[i])
	{
		u = insert(s[i], u);
		++i;
	}
	slinktree();
	dfs(0);
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%s", t+1);
		len = strlen(t+1);
		int i = 1;
		while(i<=len)
		{
			t[len+i] = t[i];
			++i;
		}
		t[len + i - 1] = 0; // 构造T1
		printf("%d\n", kk());
	}
	return 0;
}

ac情况

Accepted

参考

【1】《史上全网最清晰后缀自动机学习(一)基本概念入门》

【2】《史上全网最清晰后缀自动机学习(二)后缀自动机的线性时间构造算法》

【3】《史上全网最清晰后缀自动机学习（三）后缀自动机里的树结构》

【4】《史上全网最清晰后缀自动机学习（四）后缀自动机里的DAG结构》