我们定义2个字符串的相似度等于两个串的相同前缀的长度。例如 “abc” 同 “abd” 的相似度为2，“aaa” 同 “aaab” 的相似度为3。
给出一个字符串S，计算S同他所有后缀的相似度之和。例如：S = “ababaa”，所有后缀为：
ababaa 6
babaa 0
abaa 3
baa 0
aa 1
a 1
S同所有后缀的相似度的和 = 6 + 0 + 3 + 0 + 1 + 1 = 11
输入
输入一个字符串S(1 <= L <= 1000000)，L为字符串S的长度，且S由a-z的小写字母组成。
输出
输出S同所有后缀的相似度的和。
输入样例
ababaa
输出样例
11
后缀数组模板题，倍增算法O（nlogn）复杂度的过不去，需要DC3算法O(n)复杂度才能卡过去（正解是exKMP算法）但是我不会
倍增算法
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; char s[maxn]; int height[maxn], sa[maxn], tx[maxn], rak[maxn]; struct node { int x, y, id; }a[maxn], b[maxn]; int n, m, p; void rsort() { for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[a[i].y]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = 1; i <= n; i++) { b[tx[a[i].y]--] = a[i]; } for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[b[i].x]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = n; i >= 1; i--) { a[tx[b[i].x]--] = b[i]; } } void ssort() { rsort(); p = 0; for (int i = 1; i <= n; i++) { if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) { ++p; } rak[a[i].id] = p; } for (int i = 1; i <= n; i++) { a[i].x = rak[i]; a[i].id = sa[rak[i]] = i; a[i].y = 0; } m = p; } void solve() { m = 127; for (int i = 1; i <= n; i++) { a[i].x = a[i].y = s[i]; a[i].id = i; } ssort(); for (int j = 1; j <= n; j <<= 1) { for (int i = 1; i + j <= n; i++) { a[i].y = a[i + j].x; } ssort(); if (p == n) { break; } } } void get_Height() { 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; } } int main() { scanf("%s", s + 1); n = strlen(s + 1); solve(); get_Height(); long long ans = 0; int mm = 1e9; for (int i = rak[1] + 1; i <= n; i++) { mm = min(mm, height[i]); ans += mm; } mm = 1e9; for (int i = rak[1]; i >= 1; i--) { mm = min(mm, height[i]); ans += mm; } cout << ans + n << endl; return 0; }
