后缀数组三·重复旋律3
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。
旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？
输入
共两行。一行一个仅包含小写字母的字符串。字符串长度不超过 100000。
输出
一行一个整数，表示答案。
- 样例输入
abcdefg
abacabca- 样例输出
3
解题方法提示：小Ho：这一次的问题该如何解决呢？
小Hi：嗯，这次的问题是经典的最长公共子串问题。
小Ho：我以前学过kmp，但是似乎不适用这道题目。
小Hi：是的。问题的关键就出在kmp求的是完整的匹配，而本题需要支持子串的匹配。
小Ho：那怎么用后缀数组解决呢？后缀数组求的是一个串的呀。
小Hi：对。但是你有没有想过可以把两个串拼起来成为一个串？
小Ho：啊！好妙的思路。
小Hi：我们不妨将两个串用一个没出现过的＃字符隔开。对这个拼接串求后缀数组和height 数组。
小Ho：喔！既然height和两两后缀之间的最长公共前缀有关，那是不是height的最大值就是答案呀？
小Hi：只说对了一部分。直接这样子做是不对的。举个例子abab和a，我们对abab#a求后缀数组，得到：
#a 5 0 / a 6 0 a ab#a 3 1 abab abab#a 1 2 abab b#a 4 0 abab bab#a 2 1 abab 我们发现height的最大值是2，而正确答案显然是1。
小Ho：这是为什么？
小Hi：由于例子中ab#a和abab#a两个后缀的开始位置同属于前一个字符串，导致计算出了前一个字符串内部的"公共子串"。
小Ho：哦，我明白了。我想想怎么修改这个算法...
小Hi：其实很简单，强行把他们分离就好了。
小Ho：是不是我们只需求排名相邻，原来不在同一个字符串的 height 值的最大值。
小Hi：为什么？
小Ho：你想啊，如果两个后缀在不同串中，计算它们最长前缀时必定要跨越过这些height值。举个例子，比如上面例子中求abab和a的最长前缀时（对应后缀数组中第4个和第2个），我们跨越了第2个后缀和第3个后缀这个不同串的“分界处”。
小Hi：说的太对了！
小Ho：我这就去实现一下！
小Hi：这个做法可以推广到做任意多个串的最长公共子串，如果你有兴趣也可以好好想想。
小Ho：嗯，应该也难不倒我。就把独立思考留给我吧！
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 2e9
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = 2e5+;
const int M = 4e5+;
int cmp(int *r,int a,int b,int l)
{
return (r[a]==r[b]) && (r[a+l]==r[b+l]);
} int wa[N],wb[N],wss[N],wv[N];
int Rank[N];//后缀i在sa[]中的排名
int height[N];//sa[i]与sa[i-1]的LCP
int sa[N];//sa[i]表示排名第i小的后缀的下标
void DA(int *r,int *sa,int n,int m) //此处N比输入的N要多1，为人工添加的一个字符，用于避免CMP时越界
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=; i<m; i++) wss[i]=;
for(i=; i<n; i++) wss[x[i]=r[i]]++;
for(i=; i<m; i++) wss[i]+=wss[i-];
for(i=n-; i>=; i--) sa[--wss[x[i]]]=i; //预处理长度为1
for(j=,p=; p<n; j*=,m=p) //通过已经求出的长度J的SA，来求2*J的SA
{
for(p=,i=n-j; i<n; i++) y[p++]=i; // 特殊处理没有第二关键字的
for(i=; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; //利用长度J的，按第二关键字排序
for(i=; i<n; i++) wv[i]=x[y[i]];
for(i=; i<m; i++) wss[i]=;
for(i=; i<n; i++) wss[wv[i]]++;
for(i=; i<m; i++) wss[i]+=wss[i-];
for(i=n-; i>=; i--) sa[--wss[wv[i]]]=y[i]; //基数排序部分
for(t=x,x=y,y=t,p=,x[sa[]]=,i=; i<n; i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++; //更新名次数组x[],注意判定相同的
}
} void calheight(int *r,int n) // 此处N为实际长度
{
int i,j,k=; // height[]的合法范围为 1-N, 其中0是结尾加入的字符
for(i=; i<=n; i++) Rank[sa[i]]=i; // 根据SA求Rank
for(i=; i<n; height[Rank[i++]] = k ) // 定义：h[i] = height[ Rank[i] ]
for(k?k--:,j=sa[Rank[i]-]; r[i+k]==r[j+k]; k++); //根据 h[i] >= h[i-1]-1 来优化计算height过程
}
int idx;
int belong[N];
int n,m,aa[N];
char s1[N],s2[N];
int Find()
{
DA(aa,sa,n+,);
calheight(aa,n);
int maxn=;
for(int i=;i<=n;i++){
if((sa[i-]<idx&&sa[i]>idx)||(sa[i-]>idx&&sa[i]<idx))maxn=max(maxn,height[i]);
}
return maxn;
} int main ()
{
scanf("%s",s1);
scanf("%s",s2);
idx=strlen(s1);
s1[idx]='#';
s1[idx+]=;
strcat(s1,s2);
n=strlen(s1);
for(int i=; s1[i]; i++){
aa[i]=s1[i]-'a'+;
}aa[idx]=;
int l=,r=n;
int ans=Find();
printf("%d\n",ans);
return ;
}