题目其实就是给你一段字符串问你类似ABA这种形式的有多少个，其中B的长度给出。 首先要差分，这个就比较明显了。 然后我们初始化ST表，正反各做一遍SA，求出正反的height和rank。 然后由于suf[a],suf[b]的lcp为min(height[a+1]~height[b])所以用ST表处理可以达到O（1）查询。 然后我们对于原串，枚举走势相同的长度为L，每L个设置一个关键点，可以发现，每一个A一定且至多覆盖一个关键点。 枚举关键点i，i和i+B+L往左往右匹配长度l和r(同理r也包括关键点)，如果l+r>=L那么这个地方就有l+r-L+1个满足的子串 接下来引用原文。。
为了做到不重复，左右延伸最大长度为L-1 为什么这样就不重复了？我这个煞笔竟然想了好长时间，因为上面的斜体，每个关键点延伸出来的，第一个L一定覆盖了这个关键点，从其他关键点开始的都不覆盖，所以不重复不遗漏艰难= =搞了一晚上，菜的不行。。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=5e4+5; const int INF=1e9; int B,s[N],mp[N],tot; int n,m,c[N],t1[N],t2[N]; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline int find(int x) { int l=1,r=tot; while (l<=r) { int mid=(l+r)>>1; if (mp[mid]==x)return mid; else if (x<mp[mid])r=mid-1; else l=mid+1; } return 0; } inline bool cmp(int *r,int a,int b,int j){ return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j]; } int Log[N],Pow[20],mn[N][17]; inline void iniST() { Pow[0]=1; fo(i,1,19)Pow[i]=Pow[i-1]*2; Log[0]=-1; fo(i,1,n)Log[i]=Log[i/2]+1; } inline void getST(int mn[N][17],int a[]) { fo(i,1,n)mn[i][0]=a[i]; fo(j,1,Log[n]) for(int i=1;i+Pow[j]-1<=n;i++) { mn[i][j]=min(mn[i][j-1],mn[i+Pow[j-1]][j-1]); } } struct SA{ int sa[N],rank[N],height[N],mn[N][17]; inline void getheight() { int k=0; fo(i,1,n)rank[sa[i]]=i; fo(i,1,n) { if (k)k--; if (rank[i]==1)continue; int j=sa[rank[i]-1]; while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++; height[rank[i]]=k; } } inline void getsa() { int *r=t1,*k=t2; fo(i,0,m)c[i]=0; fo(i,1,n)c[r[i]=s[i]]++; fo(i,1,m)c[i]+=c[i-1]; fd(i,n,1)sa[c[r[i]]--]=i; for(int j=1;j<=n;j<<=1) { int p=0; for(int i=n-j+1;i<=n;i++)k[++p]=i; fo(i,1,n)if (sa[i]>j)k[++p]=sa[i]-j; for(int i=0;i<=m;i++) c[i]=0; for(int i=1;i<=n;i++) c[r[k[i]]]++; for(int i=1;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[r[k[i]]]--]=k[i]; swap(r,k);p=0;r[sa[1]]=++p; for(int i=2;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-1],j)?p:++p; if(p>=n) break;m=p; } } inline int lcp(int x,int y) { x=rank[x],y=rank[y]; if (x>y)swap(x,y); x++; int t=Log[y-x+1]; return min(mn[x][t],mn[y-Pow[t]+1][t]); } inline void ini() { getsa(); getheight(); getST(mn,height); } }a,b; int ans; inline void solve(int L) { for(int i=1;i+B+L<=n;i+=L) if (s[i]==s[i+B+L]) { int r=a.lcp(i,i+B+L),l=b.lcp(n-i+2,n-i-B-L+2); l=min(l,L-1);r=min(r,L); if (l+r>=L)ans+=l+r+1-L; } } int main() { n=read(); B=read(); fo(i,1,n) { s[i]=read(); if (i!=1)mp[++tot]=s[i-1]=s[i]-s[i-1]; } n--; sort(mp+1,mp+1+n); tot=0,mp[++tot]=mp[1]; fo(i,2,n)if (mp[i]!=mp[i-1])mp[++tot]=mp[i]; fo(i,1,n)s[i]=find(s[i]); m=n; iniST(); a.ini(); reverse(s+1,s+1+n); b.ini(); reverse(s+1,s+1+n); for(int l=1;l+l+B<=n;l++)solve(l); printf("%d\n",ans); }