缘起
最长公共子串（LCS）问题可谓是经典的问题了. 我们使用过DP、后缀树、后缀数组来解决过. 现在我们考虑后缀自动机和LCS问题的联系, 并且来看这一联系的典型例题—— hihocoder #1465 : 后缀自动机五·重复旋律8
分析
代码语言：javascript复制时间限制: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树的方法已经解决了.
另外, 本题的多串对于上述算法并没有什么影响~ 一个一个来就好了~
好了, 说了这么多. 开心的切代码好伐~
代码语言：javascript复制//#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("%dn", kk());
}
return 0;
}
ac情况
代码语言：javascript复制Accepted
参考
【1】《史上全网最清晰后缀自动机学习(一)基本概念入门》
【2】《史上全网最清晰后缀自动机学习(二)后缀自动机的线性时间构造算法》
【3】《史上全网最清晰后缀自动机学习（三）后缀自动机里的树结构》
【4】《史上全网最清晰后缀自动机学习（四）后缀自动机里的DAG结构》
