prefixdoubling.cpp
Bài toán
Sinh ra suffix array.
Độ phức tạp
O(n logn)
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++)
#define N 400005
char s[N];
int n, Rank[21][N], SA[21][N], SA1[N];
void radix_sort(int a[], int b[], int n, int r[], int K) {
vector<int> Count(K + 1), Start(K + 1);
f0(i, n) Count[r[a[i]]]++;
f1(i, K) Start[i] = Start[i - 1] + Count[i - 1];
f0(i, n) b[Start[r[a[i]]]++] = a[i];
}
int main() {
gets(s);
n = strlen(s);
f0(i, n) Rank[0][i] = s[i];
f0(i, n) SA1[i] = i;
radix_sort(SA1, SA[0], n, Rank[0], 128);
int Name = 128, Gap = 1;
f1(k, 17) {
radix_sort(SA[k - 1], SA1, n, Rank[k - 1] + Gap, Name);
radix_sort(SA1, SA[k], n, Rank[k - 1], Name);
Name = 0;
f0(i, n) {
if (i == 0 || Rank[k - 1][SA[k][i]] != Rank[k - 1][SA[k][i - 1]]
|| Rank[k - 1][SA[k][i] + Gap] != Rank[k - 1][SA[k][i - 1] + Gap])
Name++;
Rank[k][SA[k][i]] = Name;
}
Gap *= 2;
}
f0(i, n) printf("%d\n", SA[17][i]);
}
Nhận xét