prefixdoubling.cpp (3) lcparray

Bài toán

Sinh ra mảng LCP bằng suffix array tạo bởi thuật toán nhân đôi tiền tố.

Độ phức tạp

tạo suffix array: O(n logn)

tạo mảng LCP: O(n)

bộ nhớ: O(n)

Code này của Nguyễn Tiến Trung Kiên

#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++)

int cmp(int x, int y, int Rank[], int n, int k) {

    if (Rank[x] != Rank[y]) return Rank[x] - Rank[y];

    if (x + k > n || y + k > n) return y - x;

    return Rank[x + k] - Rank[y + k];

}

void radix_sort(int a[], int b[], int n, int r[], int K) {

    vector<int> Count(K + 1), Start(K + 1);

    f1(i, n) Count[r[a[i]]]++;

    f1(i, K) Start[i] = Start[i - 1] + Count[i - 1];

    f1(i, n) b[++Start[r[a[i]]]] = a[i];

}

void sort_suffix(int Rank[], int sa[], int n, int K) {

    int k = 1, *zz = new int[n + 1];

    do {

        radix_sort(sa, zz, n, Rank + k, K);

        radix_sort(zz, sa, n, Rank, K);

        K = 0;

        f1(i, n) {

            if (i == 1 || cmp(sa[i], sa[i - 1], Rank, n, k) != 0) K++;

            zz[sa[i]] = K;

        }

        f1(i, n) Rank[i] = zz[i];

    } while (K != n);

}

void make_lcp(int Rank[], int sa[], char s[], int n, int LCP[]) {

    int l = 0;

    f1(i, n) {

        int k = Rank[i], j = sa[k - 1];

        while (s[i + l] == s[j + l]) l++;

        LCP[k] = l;

        if (l > 0) l--;

    }

}

bool maximize(int &a, int b) {

    if (a < b)

        a = b;

    else

        return false;

    return true;

}

#define N 100005

int n, t;

char s[N];

int Rank[2 * N], sa[2 * N], LCP[2 * N];

int main() {

    scanf("%d", &t);

    while (t--) {

        scanf("%s", s + 1);

        n = strlen(s + 1);

        f1(i, n) {

            Rank[i] = s[i], sa[i] = i;

            LCP[i] = 0;

        }

        sort_suffix(Rank, sa, n, 128);

        make_lcp(Rank, sa, s, n, LCP);

        int Max = 0, Dcs = 0, DcsLen = 0;

        f1(i, n) if (maximize(Max, LCP[i])) Dcs = i;

        if (Max == 0)

            printf("No repetitions found!\n");

        else {

            while (LCP[Dcs + DcsLen] == Max) DcsLen++;

            printf("%.*s %d\n", Max, s + sa[Dcs], DcsLen + 1);

        }

        f1(i, 2 * n) Rank[i] = s[i] = sa[i] = LCP[i] = 0;

    }

}

Nhận xét

Code này đã được dùng để nộp cho một bài tập trên UVa.

Tham khảo

http://uva.onlinejudge.org/external/115/11512.html