后缀数组、重复子串、回文子串
题意：
分析：
刚拿到这题我是崩溃的，这可咋求啊？！AABB的，太吓人了！！
然后我仔细看了看，其实问题的关键在于如何判断一个连续的AA串！！
如果我们能够计算出哪里有AA串就好了。
比如：
a[i]记录了一索引i结尾的AA串有多少个
b[i]记录了一索引i开始的AA串有多少个
然后我们只需要遍历一下原字符串ans+=a[i]*b[i+1]就可以了！
但是，如何计算出哪里有AA串呢？？？
正当我一筹莫展的时候，突然我意识到：这是一个重复子串问题！！！废话
但是，提起重复子串你会想到什么？？最长重复子串问题！！！！！
如果你还不知道什么是最长重复字串问题，我建议你先去学习最长重复字串问题。他是后缀数组的经典应用！
现在你已经知道了如何求解最长重复字串问题了！
然后你将发现本问题和最长重复子串问题极度地相似！
我们同样可以枚举距离i，然后隔着距离i枚举j与j+i
我们求解AA一个经过j，一个经过j+i
如此求出所有的AA组然后记录a与b。
具体如何操作呢？
利用后缀数组我们先求出j与i+j向右方向的最长公共前缀
然后我们再想办法求出j与i+j想左方向的最长公共前缀
这样我们就知道了[left,j,right]他与[left+i,j+i,right+i]相等
但是我们限制是距离i所以应该是
[max(left,j-i+1),j,min(right,j+i-1)]
这里是第一个A的活动范围
具体到A的开头的首位就更小了[max(left,j-i+1),min(right-i+1,j)；
我们可以确定将第一个A开头的首位放在这个区间里，一定也是AA的首位
这部分有点难懂，是我讲解的不好。。。。。。
至于，我们如何求解j与j+i左方向的最长公共前缀？？
还记得最长回文子串是怎么求的吗？求看看，不用会做，只需知道做法。
我们在这里应用到了同样的技巧，我们reverse一下再求一个SA
或者再中间添一个绝对不会撞车的数字，然后在后面添加reverse后的字符串就好了(稍微慢点)
如此，此题得解
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define re register
const int max_n = 6e4 + 100;
int ranks[max_n], SA[max_n], height[max_n];
int wa[max_n], wb[max_n], wvarr[max_n], wsarr[max_n];
inline int cmp(int* r, int a, int b, int l) {
return r[a] == r[b] && r[a + l] == r[b + l];
}
inline void get_sa(int* r, int* sa, int n, int m) {
//r:原数组
//sa:SA
//n:原数组长度
//m:原数组种类数，用于基数排序
++n;
re int i, j, p, * x = wa, * y = wb, * t;
for (i = 0; i < m; ++i) wsarr[i] = 0;
for (i = 0; i < n; ++i) wsarr[x[i] = r[i]]++;
for (i = 1; i < m; ++i) wsarr[i] += wsarr[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wsarr[x[i]]] = i;
for (j = 1, p = 1; p < n; j <<= 1, m = p) {
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; ++i) wvarr[i] = x[y[i]];
for (i = 0; i < m; ++i) wsarr[i] = 0;
for (i = 0; i < n; ++i) wsarr[wvarr[i]]++;
for (i = 1; i < m; ++i) wsarr[i] += wsarr[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wsarr[wvarr[i]]] = y[i];
for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
}//求解高度数组，height[i]指排名
void get_height(int* r, int* sa, int n) {
re int i, j, k = 0;
for (i = 1; i <= n; ++i) ranks[sa[i]] = i;
for (i = 0; i < n; height[ranks[i++]] = k)
for (k ? k-- : 0, j = sa[ranks[i] - 1]; r[i + k] == r[j + k]; k++);
return;
}
//后缀数组
//附加rmq_st 专门对后缀数组
int st[max_n][32];
void initSt(int a[], int n) {
for (int i = 0;i <= n;++i)st[i][0] = height[i];
int mxk = (int)log2(n + 1);
for (int k = 1;k <= mxk;++k) {
for (int i = 0;i <= n;++i) {
if (i + (1 << k) - 1 > n)break;
st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
}
}
int que(int l, int r) {
l = ranks[l];r = ranks[r];
if (l > r)swap(l, r);
++l;
int len = (int)log2(r - l + 1);
return min(st[l][len], st[r - (1 << len) + 1][len]);
}
string s;
int a[max_n];
int b[max_n];
int c[max_n];
void init(int n) {
fill(a, a + n + 3, 0);
fill(b, b + n + 3, 0);
fill(c, c + n + 3, 0);
fill(ranks, ranks + n + 3, 0);
fill(SA, SA + n + 3, 0);
fill(height, height + n + 3, 0);
fill(wa, wa + n + 3, 0);
fill(wb, wb + n + 3, 0);
fill(wsarr, wsarr + n + 3, 0);
fill(wvarr, wvarr + n + 3, 0);
}
int main() {
ios::sync_with_stdio(0);
int T;cin >> T;
while (T--) {
cin >> s;
int n = s.size();init(n * 2 + 1);
for (re int i = 0;i < s.size();++i)a[i] = (s[i] - 'a' + 1);
reverse(s.begin(), s.end());
a[n] = 29;
for (re int i = 0;i < s.size();++i)a[i + n + 1] = (s[i] - 'a' + 1);
n = n * 2 + 1;
get_sa(a, SA, n, 30);
get_height(a, SA, n);
initSt(a, n);
for (re int i = 1;i < s.size();++i) {
for (re int j = 0;j + i < s.size();j += i) {
if (a[j] != a[i + j])continue;
int right = que(j, j + i);
int t1 = n - j - 1;int t2 = n - (j + i) - 1;
int left = que(t1, t2);
left = max(j - left + 1, j - i + 1);
right = min(j, j + right - i);
for (re int k = left;k <= right;++k) {
++b[k];
++c[k + i + i - 1];
}
}
}ll ans = 0;
for (re int i = 0;i < s.size();++i)
ans += (ll)c[i] * b[i + 1];
cout << ans << endl;
}
}
京公网安备 11010502036488号