题目传送门
题目大意：
给一个字符串，当一个子串既是它的前缀也是它的后缀时，称其为一个特殊子串，注意，该串本身也是一个特殊串
要统计这种串的出现的总次数
应该有很简单的做法但是我不会(毕竟zzq把这题秒了。。。)
嗯，官方题解是kmp的性质，反而zzq也是SA，但是都比我简单
曾经判断是否为特殊串我用的hash，O(1)比较
然后被教做人了
更新数据之后被hack成瓜皮
事实上可以直接用SA判断……反正都注定是nlogn的……注意这样会漏掉串本身这种情况就对了……
统计的时候可以考虑子串的本质：后缀的前缀
根据字典序，相同前缀的子串在按字典序排列的情况下是相邻的
所以可以用SA进行统计，在height数组上分两段二分查找，结合ST表，找到两个位置使得这之间的后缀共有一个特殊串前缀即可
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;template <typename T> inline void read(T &x) {int c = getchar();bool f = false;for (x = 0; !isdigit(c); c = getchar()) {if (c == '-') {f = true;}}for (; isdigit(c); c = getchar()) {x = x * 10 + c - '0';}if (f) {x = -x;}
}ull base = 233;
ull po[400400], hs[400400];
char s2[400400];
int n;ull geth(int l,int r) {return (ull) hs[r] - po[r - l + 1] * hs[l - 1];
}namespace SA_ {const int MAXN = 400400;const int INF = 0x3f3f3f3f;char s[MAXN];int * x, * y;int a[MAXN], fir[MAXN], sec[MAXN];int rnk[MAXN], sa[MAXN], h[MAXN], len, n, sum[MAXN];inline void init() {x = rnk; y = sec;len = strlen(s + 1);for(int i = 1; i <= (int) strlen(s + 1); i++) a[i] = s[i];}inline void radix_sort(int * f) {memset(sum, 0, sizeof(sum));for(int i = 1; i <= len; i++) sum[f[i]] ++;for(int i = 1; i <= n; i++) sum[i] += sum[i - 1];for(int i = len; i; i--) sa[sum[f[i]] --] = y[i];}inline void SA() {int i, j, p; n = 255;memset(sum, 0, sizeof(sum));for(i = 1; i <= len; i++) sum[(x[i] = a[i])] ++;for(i = 1; i <= n; i++) sum[i] += sum[i - 1];for(i = len; i; i--) sa[sum[x[i]] --] = i;for(j = 1, p = 1; p < len; j <<= 1, n = p) {for(i = len - j + 1, p = 0; i <= len; i++) y[++p] = i;for(i = 1; i <= len; i++) (sa[i] - j > 0) && (y[++p] = sa[i] - j);for(i = 1; i <= len; i++) fir[i] = x[y[i]]; radix_sort(fir);swap(x, y); x[sa[1]] = 1;for(i = 2, p = 1; i <= len; i++) {if((y[sa[i - 1]] != y[sa[i]]) || (y[sa[i] + j] != y[sa[i - 1] + j]))p++;x[sa[i]] = p;}}for(i = 1; i <= len; i++) rnk[sa[i]] = i;}inline void GetH() {int k = 0; for(int i = 1; i <= len; i++) {if(rnk[i] == 1) h[rnk[i]] = 0;else {int j = sa[rnk[i] - 1];while(a[i + k] == a[j + k]) k++;h[rnk[i]] = k;if(k > 0) k--;}} }int f[MAXN][20];void update() {int l = strlen(s + 1);for(int i = 1; i <= l; i++) f[i][0] = h[i];for(int j = 1; (1 << j) <= l; j++) {for(int i = 1; i + (1 << j) - 1 <= l; i++) {f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}}int query(int l, int r) {if(l > r) swap(l, r);l++;int p = 0; while((1 << (p + 1)) <= (r - l + 1)) p++;return min(f[l][p], f[r - (1 << p) + 1][p]);}int calc(int le, int pos) {int l = 1, r = pos, ans1 = pos, ans2 = pos;while(l <= r) {int mid = (l + r) >> 1;if(query(mid, pos) >= le) ans1 = mid, r = mid - 1;else l = mid + 1;}l = pos + 1, r = len;while(l <= r) {int mid = (l + r) >> 1;if(query(pos, mid) >= le) ans2 = mid, l = mid + 1;else r = mid - 1;}return ans2 - ans1 + 1;}void solve() {memset(a, 0, sizeof(a));memset(fir, 0, sizeof(fir));memset(sec, 0, sizeof(sec));memset(sa, 0, sizeof(sa));memset(rnk, 0, sizeof(rnk));init(), SA(), GetH();update();}
}//#define LOCAL
#define Debug(...) fprintf(stderr, __VA_ARGS__)signed main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifread(n);scanf("%s", s2 + 1);int l2 = (int) strlen(s2 + 1);memset(SA_::s, 0, sizeof(SA_::s));for(int i = 1; i <= l2; i++) SA_::s[i] = s2[i];SA_::solve(); long long ans = 0;for(int i = 1; i <= n; i++) {if(SA_::query(SA_::rnk[1], SA_::rnk[n - i + 1]) == i) {ans += (long long) SA_::calc(i, SA_::rnk[n - i + 1]);}}cout << ans + 1 << endl;
#ifdef LOCALDebug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endifreturn 0;
}
/*
6
aabaaa
*/