prefixdoubling.cpp (3) lcparray
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define long long long
#define f1(i, n) for (int i = 1; i <= n; i++)
#define f0(i, n) for (int i = 0; i < n; i++)
void radix_sort(int a[], int b[], int r[], int n, int MaxB) {
vector<int> Count(MaxB + 1), Start(MaxB + 1);
f1(i, n) Count[b[i]]++;
f1(i, MaxB) Start[i] = Start[i - 1] + Count[i - 1];
f1(i, n) r[++Start[b[a[i]]]] = a[i];
}
#define N 200005
char a[N];
int n;
int Suffix[N], Suffix1[N], Rank[N], NewRank[N], LCP[N];
int main() {
gets(a + 1);
n = strlen(a + 1);
f1(i, n) Suffix[i] = i;
f1(i, n) Rank[i] = a[i] - 64;
int RankMax = 26;
f0(k, 20) {
radix_sort(Suffix, Rank + (1 << k), Suffix1, n, RankMax);
radix_sort(Suffix1, Rank, Suffix, n, RankMax);
RankMax = 0;
f1(i, n) {
int k1 = Suffix[i - 1], k2 = Suffix[i];
if (Rank[k1] != Rank[k2] || Rank[k1 + (1 << k)] != Rank[k2 + (1 << k)])
RankMax++;
NewRank[k2] = RankMax;
}
f1(i, n) Rank[i] = NewRank[i];
if (RankMax == n) break;
}
int l = 0;
f1(i, n) {
int j = Suffix[Rank[i] - 1];
while (a[i + l] == a[j + l]) l++;
LCP[Rank[i]] = l;
if (l > 0) l--;
}
long Sum = 0;
f1(i, n) {
int SuffixLen = n - Suffix[i] + 1;
Sum += SuffixLen - LCP[i];
}
cout << Sum << endl;
}