这是基于后缀数组的O（n log n）版本。后缀数组有O（n）个构造算法，我只是没有耐心对它们进行编码。
输出示例（此输出不是O（n），但这只是为了表明我们确实可以计算所有分数）：
4*1 a3*3 aba2*5 ababa1*7 abababa3*2 ab2*4 abab1*6 ababab
基本上，您必须反转字符串，并计算后缀数组（SA）和最长公共前缀（LCP）。
然后，您将向后遍历SA数组，以查找与整个后缀（原始字符串中的前缀）匹配的LCP。如果存在匹配项，请增加计数器，否则将其重置为1。每个后缀（前缀）都会收到一个“分数”（SCR），该分数对应于它在原始字符串中出现的次数。
#include <iostream>#include <cstring>#include <string>#define MAX 10050using namespace std;int RA[MAX], tempRA[MAX];int SA[MAX], tempSA[MAX];int C[MAX]; int Phi[MAX], PLCP[MAX], LCP[MAX];int SCR[MAX];void suffix_sort(int n, int k) { memset(C, 0, sizeof C); for (int i = 0; i < n; i++) C[i + k < n ? RA[i + k] : 0]++; int sum = 0; for (int i = 0; i < max(256, n); i++) { int t = C[i]; C[i] = sum; sum += t; } for (int i = 0; i < n; i++) tempSA[C[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i]; memcpy(SA, tempSA, n*sizeof(int));}void suffix_array(string &s) { int n = s.size(); for (int i = 0; i < n; i++) RA[i] = s[i] - 1; for (int i = 0; i < n; i++) SA[i] = i; for (int k = 1; k < n; k *= 2) { suffix_sort(n, k); suffix_sort(n, 0); int r = tempRA[SA[0]] = 0; for (int i = 1; i < n; i++) { int s1 = SA[i], s2 = SA[i-1]; bool equal = true; equal &= RA[s1] == RA[s2]; equal &= RA[s1+k] == RA[s2+k]; tempRA[SA[i]] = equal ? r : ++r; } memcpy(RA, tempRA, n*sizeof(int)); } }void lcp(string &s) { int n = s.size(); Phi[SA[0]] = -1; for (int i = 1; i < n; i++) Phi[SA[i]] = SA[i-1]; int L = 0; for (int i = 0; i < n; i++) { if (Phi[i] == -1) { PLCP[i] = 0; continue; } while (s[i + L] == s[Phi[i] + L]) L++; PLCP[i] = L; L = max(L-1, 0); } for (int i = 1; i < n; i++) LCP[i] = PLCP[SA[i]];}void score(string &s) { SCR[s.size()-1] = 1; int sum = 1; for (int i=s.size()-2; i>=0; i--) { if (LCP[i+1] < s.size()-SA[i]-1) { sum = 1; } else { sum++; } SCR[i] = sum; }}int main() { string s = "abababa"; s = string(s.rbegin(), s.rend()) +"."; suffix_array(s); lcp(s); score(s); for(int i=0; i<s.size(); i++) { string ns = s.substr(SA[i], s.size()-SA[i]-1); ns = string(ns.rbegin(), ns.rend()); cout << SCR[i] << "*" << ns.size() << " " << ns << endl; }}我在比赛中使用了很多年的大部分代码（特别是后缀数组和LCP实现）。我改编自几年前写的这个版本。
