Description：

求一个字符串所有能被划分成 $ABA$ 的子串的个数，其中 $|A|\geqslant k$ 。

$1\leqslant n\leqslant 15000$

Solution：

$O(n^2)$ 可过， $ABA$ 的实际意思是存在一个长度 $<l/2$ 的 $border$ ，于是就像NOI2014动物园那题一样，先进行一次 $KMP$ 求出 $nxt$ ，然后第二次 $KMP$ 的时候维护一个长度 $<l/2$ 的 $border$ 的位置，如果长度 $\geqslant k$ 答案就加一。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 15010

char c[MAXN],s[MAXN];

int nxt[MAXN];

int main()

{

	scanf("%s",c + 1);

	scanf("%d",&k);

	n = strlen(c + 1);

	long long ans = 0;

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

	{

		int d = n - l + 1;

		for(int i = 1;i <= d;++i)s[i] = c[i + l - 1];

		for(int i = 2,j = 0;i <= d;++i)

		{

			while(j && s[j + 1] != s[i])j = nxt[j];

			if(s[j + 1] == s[i])++j;

			nxt[i] = j;

		}

		for(int i = 2,j = 0;i <= d;++i)

		{

			while(j && s[j + 1] != s[i])j = nxt[j];

			if(s[j + 1] == s[i])++j;

			while(j * 2 + 1 > i)j = nxt[j];

			ans += (j >= k);

		}

	}

	cout << ans << endl;

	return 0;

}