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;

}