如果一个字符串可以被拆分为AABBAABB的形式，其中 A和 B是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串aabaabaa，如果令 A=aab，B=a，我们就找到了这个字符串拆分成 AABB的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 A=a，B=baa，也可以用 AABB表示出上述字符串；但是，字符串 abaabaa 就没有优秀的拆分。
现在给出一个长度为 n的字符串S，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
在一个拆分中，允许出现A=B。例如 cccc 存在拆分A=B=c。
字符串本身也是它的一个子串。
每个输入文件包含多组数据。
输入的第一行只有一个整数T，表示数据的组数。保证 1≤T≤10。
接下来 T行，每行包含一个仅由英文小写字母构成的字符串S，意义如题所述。
输出 T行，每行包含一个整数，表示字符串S 所有子串的所有拆分中，总共有多少个是优秀的拆分。
aabbbb cccccc aabaabaabaa bbaabaababaaba
5 4 7
给定一个字符串，从里面查找一共有多少个字符串满足AABB形式，输出个数
【算法分析】
考虑这个拼接的情况，AABB
所以我们只需要找所有的AA/BB，然后左乘右获得最终答案
然后问题就转化成了如何求AA和BB
利用后缀数组我们能够在nlogn的时间复杂度内求取出LCP
同时我们把字符串翻转，然后就能够求到LCS
而这两个字符串如果重合，就说明能够出现AA的这种形式的重复
定义：
f [ i ] 为以 i 开头的符合条件的AA型字符串
g [ i ] 为以 i 结尾的符合条件的AA型字符串
然后我们只需要把他们 相乘累加即可
注意：
最后一个不能够重叠，所以最后一个位置（ n ）不符合要求
【代码】
#include<cstdio> #include<cstring> #include<string> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 30000+ 5; int lg[MAXN], f[MAXN], g[MAXN]; struct suff_string { int n,m; int x[MAXN] = { 0 }, y[MAXN] = { 0 }, c[MAXN] = { 0 }; int SA[MAXN], rak[MAXN], height[MAXN]; int st[17][MAXN]; void build_SA(char *s) { n = strlen(s + 1); m = 128; for (int i = 1; i <= 30000; i++) x[i] = y[i] = c[i] = 0; for (int i = 1; i <= n; i++) SA[i] = rak[i] = height[i] = 0; for (int i = 1; i <= n; i++) ++c[x[i] = s[i]]; //计算每一个字符的数量，同样的放在一起 for (int i = 2; i <= m; i++) c[i] += c[i - 1]; //求前缀和 for (int i = n; i >= 1; i--) SA[c[x[i]]--] = i; //从后往前，这样就能求出最开始顺序 for (int k = 1; k <= n; k <<= 1) { int num = 0; for (int i = n - k + 1; i <= n; i++) y[++num] = i; //把最后几个字符放进去 for (int i = 1; i <= n; i++) //按照顺序遍历 if (SA[i] > k) //如果长度大于k y[++num] = SA[i] - k; //把第一个放进去 for (int i = 1; i <= m; i++) c[i] = 0; for (int i = 1; i <= n; i++) c[x[i]]++; //x[i]是第一关键字 for (int i = 2; i <= m; i++) c[i] += c[i - 1]; //求前缀和 for (int i = n; i >= 1; i--) SA[c[x[y[i]]]--] = y[i], y[i] = 0; swap(x, y); x[SA[1]] = 1; num = 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]) ? num : ++num; if (num == n) break; m = num; } for (int i = 1; i <= n; i++) rak[SA[i]] = i; return; } void get_height(char *s) { int k = 0; for (int i = 1; i <= n; i++) { if (k) k--; int j = SA[rak[i] - 1]; while (i+k<=n && j+k<=n &&s[i + k] == s[j + k]) k++; height[rak[i]] = k; } } void build_ST() { memset(st, 0, sizeof(st)); for (int i = 1; i <= n; i++) st[0][i] = height[i]; //printf("1\n"); for (int i = 1; i <= 16; i++) for (int j = 1; j <= n; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); //printf("2\n"); } int query(int l, int r) { l = rak[l],r = rak[r]; if (l > r) swap(l, r); l++; int t = lg[r + 1 - l]; return min(st[t][l], st[t][r - (1 << t) + 1]); } }A,B; char s[MAXN]; void solve() { //printf("%s\n", s+1); //printf("**\n"); scanf("%s", s + 1); A.build_SA(s); A.get_height(s); A.build_ST(); int N = A.n; reverse(s + 1, s + 1 + N); //printf("%s\n", s + 1); B.build_SA(s); B.get_height(s); B.build_ST(); //printf("%d %d \n",A.n,B.n); for (int i = 1; i <=N; i++) f[i] = 0, g[i] = 0; for (int len = 1; len <= N / 2; len++) { for (int i = len, j = i + len; j <= N; i += len, j += len) { // printf("**\n"); int lcp = min(A.query(i, j), len), lcs = min(B.query(N - i + 2, N - j + 2), len - 1); // printf("**\n"); int t = lcp + lcs - len + 1; if (lcp + lcs >= len) { g[i - lcs]++, g[i - lcs + t]--; f[j + lcp - t]++, f[j + lcp]--; } } } //printf("**\n"); for (int i = 1; i <= N; i++) f[i] += f[i - 1], g[i] += g[i - 1]; long long ans = 0; for (int i = 1; i <N; i++) ans += 1ll * f[i] * g[i + 1]; printf("%lld\n", ans); } int main() { int T; for (int i = 2; i <= 30000; i++) lg[i] = lg[i >> 1] + 1; scanf("%d", &T); while (T--) { solve(); } return 0; }
纪念我水过的第二道黑题
原文：https://www.cnblogs.com/rentu/p/11426187.html
