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