这是基于后缀数组的O（n log n）版本。后缀数组有O（n）个构造算法，我只是没有耐心对它们进行编码。

输出示例（此输出不是O（n），但这只是为了表明我们确实可以计算所有分数）：

4*1 a
3*3 aba
2*5 ababa
1*7 abababa
3*2 ab
2*4 abab
1*6 ababab

基本上，您必须反转字符串，并计算后缀数组（SA）和最长公共前缀（LCP）。

然后，您将向后遍历SA数组，以查找与整个后缀（原始字符串中的前缀）匹配的LCP。如果存在匹配项，请增加计数器，否则将其重置为1。每个后缀（前缀）都会收到一个“分数”（SCR），该分数对应于它在原始字符串中出现的次数。

#include <iostream>
#include <cstring>
#include <string>
#define MAX 10050
using 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实现）。我改编自几年前写的这个版本。