Description
形如 (ABA) 的字符串,其中 (A) 是非空字符串,且 (B) 的长度恰好是 (L),则称之为 (L-gap) 字符串。给定一个字符串 (S) 和正整数 (L),求 (S) 中有多少个 (L-gap) 子串。
Solution
考虑枚举 (A) 的长度 (i),将 (i,2i,3i,...) 位置视为关键点,分别考虑左侧的 (A) 横跨每一个关键点时的情况,由于 (A) 会横跨一个且仅一个关键点,这样统计是不重不漏的
假设当前枚举的关键点为 (p),则在右侧的 (A) 上与之对应的点是 (p+i+m),其中 (m) 为题目中的 (L)
求出 (lcp=lcp(p,p+i+m), lcs=lcs(p,p+i+m)),则左侧的 (A) 块可以存在的区间是 ([p-lcs+1,p+lcp-1])
为了确保不重不漏,(lcs,lcp) 需要对 (i) 取 (min),即不能滑到别的块上去
这个区间的长度为 (lcs+lcp-1),而 (A) 块的长度为 (i),故 (A) 块可能存在的位置数目为 (lcs+lcp-i),即本关键点的贡献
求 (lcs,lcp) 就是后缀数组 + ST 表的板子了
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
const int dbg = 0;
namespace sa
{
struct st
{
int a[N][21];
void build(int *src,int n)
{
for(int i=1; i<=n; i++) a[i][0]=src[i];
for(int i=1; i<=20; i++)
for(int j=1; j<=n-(1<<i)+1; j++)
a[j][i]=min(a[j][i-1],a[j+(1<<(i-1))][i-1]);
}
int query(int l,int r)
{
int j=log2(r-l+1);
return min(a[l][j],a[r-(1<<j)+1][j]);
}
} rmq;
int n,m=256,sa[N],y[N],u[N],v[N],o[N],r[N],h[N],T;
// sa: Suffix Array
// r: Rank Array
// h: Height Array (between sa[i] & sa[i-1])
char str[N];
long long ans;
void presolve(string _str)
{
for(int i=1; i<=_str.length(); i++) str[i]=_str[i-1];
n=strlen(str+1);
for(int i=1; i<=n; i++) u[str[i]]++;
for(int i=1; i<=m; i++) u[i]+=u[i-1];
for(int i=n; i>=1; i--) sa[u[str[i]]--]=i;
r[sa[1]]=1;
for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for(int l=1; r[sa[n]]<n; l<<=1)
{
memset(u,0,sizeof u);
memset(v,0,sizeof v);
memcpy(o,r,sizeof r);
for(int i=1; i<=n; i++) u[r[i]]++, v[r[i+l]]++;
for(int i=1; i<=n; i++) u[i]+=u[i-1], v[i]+=v[i-1];
for(int i=n; i>=1; i--) y[v[r[i+l]]--]=i;
for(int i=n; i>=1; i--) sa[u[r[y[i]]]--]=y[i];
r[sa[1]]=1;
for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+((o[sa[i]]!=o[sa[i-1]])||(o[sa[i]+l]!=o[sa[i-1]+l]));
}
{
int i,j,k=0;
for(int i=1; i<=n; h[r[i++]]=k)
for(k?k--:0,j=sa[r[i]-1]; str[i+k]==str[j+k]; k++);
}
rmq.build(h,n);
}
int query(int p,int q)
{
if(p==q) return n-p+1;
p=r[p];
q=r[q];
if(p>q) swap(p,q);
return rmq.query(p+1,q);
}
void test()
{
if(dbg)
{
for(int i=1; i<=n; i++) cout<<h[i]<<" ";
cout<<endl;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cout<<query(i,j)<<" ";
}
cout<<endl;
}
}
}
} // namespace sa
void presolve(string s)
{
string str;
str+=s;
str+='#';
reverse(s.begin(),s.end());
str+=s;
reverse(s.begin(),s.end());
sa::presolve(str);
}
int n;
int getlcs(int p,int q)
{
return min(min(n-p+1,n-q+1),sa::query(p,q));
}
int getlcp(int p,int q)
{
p=n+n+1-p+1;
q=n+n+1-q+1;
return min(min(p,q),sa::query(p,q));
}
void test()
{
if(dbg)
{
cout<<"lcp:"<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<getlcp(i,j)<<" ";
}
cout<<endl;
}
cout<<"lcs:"<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<getlcs(i,j)<<" ";
}
cout<<endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
int m;
string s;
cin>>m;
cin>>s;
n=s.length();
presolve(s);
test();
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j*i+m+i<=n;j++)
{
int p=j*i;
int q=p+m+i;
int lcs=getlcs(p,q), lcp=getlcp(p,q);
lcs=min(lcs,i);
lcp=min(lcp,i);
int len=lcs+lcp-i;
if(len>0) ans+=len;
}
}
cout<<ans<<endl;
}