Description：

给一个字符串，求 $ABA$ 形子串的个数，其中 $|B|=m$ 。

$1\leqslant n\leqslant 50000$

Solution：

类似优秀的拆分那样的做法，枚举 $A$ 的长度 $l$ ，然后每隔 $l$ 标一个关键点，然后计算 $i$ 和 $i+m+l$ 的 $lcp$ 和 $lcs$ ，这个可以用后缀数组求，然后如果能构成就统计一下答案即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

int h[MAXN],s[MAXN];

int s_[MAXN];

int sa1[MAXN],rnk1[MAXN],height1[MAXN];

int sa2[MAXN],rnk2[MAXN],height2[MAXN];

int c1[MAXN],c2[MAXN];

int c[MAXN];

void make_SA(int n,int m,int s[],int sa[],int rnk[],int height[])

{

	int *x = c1,*y = c2;

	for(int i = 1;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 >= 1;--i)sa[c[x[i]]--] = i;

	int p = 0;

	for(int k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(int i = n - k + 1;i <= n;++i)y[++p] = i;

		for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

		for(int i = 1;i <= m;++i)c[i] = 0;

		for(int i = 1;i <= n;++i)++c[x[y[i]]];

		for(int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		p = 1;

		swap(x,y);

		x[sa[1]] = 1;

		for(int i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		}

		if(p >= n)break;

		m = p;

	}

	for(int i = 1;i <= n;++i)rnk[sa[i]] = i;

	int k = 0;

	for(int i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		int j = sa[rnk[i] - 1];

		while(j + k <= n && i + k <= n && s[i + k] == s[j + k])++k;

		height[rnk[i]] = k;

	}

	return;

}

int f1[MAXN][17],f2[MAXN][17];

int lg[MAXN];

int lcp(int a,int b)

{

	if(a == 0 || b == 0)return 0;

	if(a == b)return n - a + 1;

	a = rnk1[a];b = rnk1[b];if(a > b)swap(a,b);++a;

	int len = lg[b - a + 1];

	return min(f1[a][len],f1[b - (1 << len) + 1][len]);

}

int lcs(int a,int b)

{

	if(a == 0 || b == 0)return 0;

	a = n - a + 1;b = n - b + 1;

	if(a == b)return n - a + 1;

	a = rnk2[a];b = rnk2[b];if(a > b)swap(a,b);++a;

	int len = lg[b - a + 1];

	return min(f2[a][len],f2[b - (1 << len) + 1][len]);

}

int ans = 0;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&h[i]);

	--n;

	for(int i = 1;i <= n;++i)s_[i] = s[i] = h[i + 1] - h[i];

	sort(s_ + 1,s_ + 1 + n);

	s_[0] = unique(s_ + 1,s_ + 1 + n) - s_ - 1;

	for(int i = 1;i <= n;++i)s[i] = lower_bound(s_ + 1,s_ + 1 + s_[0],s[i]) - s_;

	make_SA(n,s_[0],s,sa1,rnk1,height1);

	for(int i = 1,j = n;i < j;++i,--j)swap(s[i],s[j]);

	make_SA(n,s_[0],s,sa2,rnk2,height2);

	for(int i = 1;i <= n;++i)f1[i][0] = height1[i];

	for(int i = 1;i <= n;++i)f2[i][0] = height2[i];

	for(int k = 1;k <= 16;++k)

		for(int i = 1;i <= n;++i)

			f1[i][k] = min(f1[i][k - 1],f1[i + (1 << (k - 1))][k - 1]);

	for(int k = 1;k <= 16;++k)

		for(int i = 1;i <= n;++i)

			f2[i][k] = min(f2[i][k - 1],f2[i + (1 << (k - 1))][k - 1]);

	for(int i = 2;i <= n;++i)lg[i] = lg[i >> 1] + 1;

	for(int l = 1;l <= (n - m) / 2;++l)

	{

		for(int i = 1;i + m + l <= n;i += l)

		{

			int l1 = min(lcs(i,i + l + m),l),l2 = min(lcp(i,i + l + m),l);

			ans += max(l1 + l2 - l,0);

		}

	}

	cout << ans << endl;

	return 0;

}