题面
https://www.luogu.com.cn/problem/P2463
求 N 个串中有多少个子串的相邻差值相同
分析
解题思路还是很清晰的,可以发现无论如何增减数字,各子串中的相对大小不变
所以把原串 a[i] 转化为 b[i]=a[i+1]-a[i] (i
然后找相同的一段子串,是比较明显的SA了,把各串用分割符拼接成一个串就行
最后通过 height 数组的性质,二分答案并找到 height 的一段连续区间包含所有串而且最小值大于等于二分值即可
代码
#include
#include
using namespace std;
const int N=1e3+10;
int n,m,cnt,cut=1865,l,r;
int v[110],s[110*N],x[110*N],y[110*N],sa[110*N],id[110*N],rk[110*N],height[110*N],c[110*N],a[N];
bool used[N];
void Suffix_Array(int n,int *s,int *sa,int *rk) {
int m=cut-1,cnt;
for (int i=0;i<=m;i++) c[i]=0;
for (int i=1;i<=n;i++) c[x[i]=s[i]]++;
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i;i--) sa[c[x[i]]--]=i;
for (int j=1;j<=n;j<<=1) {
cnt=0;
for (int i=n-j+1;i<=n;i++) y[++cnt]=i;
for (int i=1;i<=n;i++) if (sa[i]>j) y[++cnt]=sa[i]-j;
for (int i=0;i<=m;i++) c[i]=0;
for (int i=1;i<=n;i++) c[x[i]]++;
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);cnt=x[sa[1]]=1;
for (int i=2;i<=n;i++) x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[min(sa[i-1]+j,n+1)]==y[min(sa[i]+j,n+1)])?cnt:++cnt;
m=cnt;if (m==n) break;
}
for (int i=1;i<=n;i++) rk[sa[i]]=i;
}
void Get_Height(int n,int *s,int *sa,int *rk,int *height) {
int z=0;
for (int i=1;i<=n;i++) {
if (rk[i]==1) {height[1]=0;continue;}
if (z) z--;
while (i+z<=n&&sa[rk[i]-1]+z<=n&&s[i+z]==s[sa[rk[i]-1]+z]) z++;
height[rk[i]]=z;
}
}
bool Check(int x) {
int m=0;
for (int i=1;i<=cnt;i++) {
if (height[i]<x) {
for (int j=1;j<=m;j++) used[a[j]]=0;m=0;
}
if (!used[id[sa[i]]]) used[a[++m]=id[sa[i]]]=1;
if (m==n) {for (int j=1;j<=m;j++) used[a[j]]=0;return 1;}
}
return 0;
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d",&m);scanf("%d",&v[1]);r=max(r,m);
for (int j=2;j<=m;j++) scanf("%d",&v[j]),v[j-1]=v[j]-v[j-1];
for (int j=1;j;
}
Suffix_Array(cnt,s,sa,rk);
Get_Height(cnt,s,sa,rk,height);
r--;
while (l<=r) {
int mid=l+r>>1;
if (Check(mid)) l=mid+1; else r=mid-1;
}
printf("%d",l);
}