آرایه پسوندی (Suffix Array) یک ساختار داده است که در علوم کامپیوتر کاربرد دارد. به زبان ساده، آرایه پسوندی یک آرایه از اعداد صحیح است که نشاندهنده موقعیت شروع همه پسوندهای یک رشته، به ترتیب الفبایی است.
فرض کنید یک رشته به نام $S$ داریم.
مثال:
فرض کنید رشته $\texttt{S = "banana"}$ را داریم.
آرایه پسوندی کاربردهای زیادی دارد، از جمله:
آرایه پسوندی معمولاً با مرتبسازی تمامی پسوندهای یک رشته ساخته میشود. ساخت آرایه پسوندی با استفاده از جستجوی دودویی (Binary Search) و هش (Hash) یک روش برای مقایسه سریعتر پسوندها در طول فرآیند مرتبسازی است. این رویکرد به جای مقایسه حرف به حرف، از مقادیر هش برای سرعت بخشیدن به مقایسهها استفاده میکند.
در این روش، از هش چندجملهای (Polynomial Hashing) استفاده میشود. این تکنیک به هر پسوند یک مقدار عددی (هش) اختصاص میدهد. این کار به ما اجازه میدهد که پسوندها را در زمان ثابت $\mathcal{O}(1)$ با هم مقایسه کنیم.
جستجوی دودویی برای مقایسه دقیقتر پسوندها به کار میرود و به جای مرتبسازی مستقیم، به سرعت طول طولانیترین پیشوند مشترک (LCP) را بین دو پسوند پیدا میکند.
الگوریتم ساخت آرایه پسوندی با این رویکرد به صورت زیر است:
این روش به طور کلی پیچیدگی زمانی $\mathcal{O}(N log^2 N)$ را برای ساخت آرایه پسوندی فراهم میکند که بهبود قابل توجهی نسبت به روشهای ساده (با پیچیدگی $\mathcal{O}(N^2 log N)$) دارد.
#include <bits/stdc++.h>
using namespace std;
// Global variables for hashing and string
const int P = 31, M = 1e9 + 7;
string s;
vector<int> p_pow;
vector<int> h;
// Function to pre-compute polynomial hashes for all prefixes
void precomputeHashes() {
int n = s.length();
p_pow.resize(n + 1);
h.resize(n + 1, 0);
p_pow[0] = 1;
for (int i = 1; i <= n; ++i)
p_pow[i] = (p_pow[i - 1] * P) % M;
for (int i = 0; i < n; ++i)
h[i + 1] = (h[i] * P + (s[i] - 'a' + 1)) % M;
}
// Function to get the hash of a substring from index l to r
int getHash(int l, int r) {
return (h[r] - (h[l] * p_pow[r - l]) % M + M) % M;
}
// Custom comparator for sorting suffixes
bool compareSuffixes(int i, int j) {
int n = s.length();
int len_i = n - i;
int len_j = n - j;
int low = 0, high = min(len_i, len_j) + 1;
while (high - low > 1) {
int mid = (low + high) / 2;
if (getHash(i, i + mid) == getHash(j, j + mid))
low = mid;
else
high = mid;
}
if (low == len_j)
return false;
if (low == len_i)
return true;
return s[i + low] < s[j + low];
}
// Main function to build the suffix array
vector<int> buildSuffixArray() {
int n = s.length();
vector<int> sa(n);
iota(sa.begin(), sa.end(), 0);
sort(sa.begin(), sa.end(), compareSuffixes);
return sa;
}
int main() {
s = "banana";
// Step 1: Pre-compute hashes
precomputeHashes();
// Step 2: Build the suffix array
vector<int> sa = buildSuffixArray();
// Output the results
cout << "String: " << s << endl;
cout << "Suffix Array: ";
for (size_t i = 0; i < sa.size(); ++i)
cout << sa[i] << (i == sa.size() - 1 ? "" : ", ");
cout << endl << endl;
cout << "Sorted Suffixes:" << endl;
for (int index : sa)
cout << "Index " << index << ": " << s.substr(index) << endl;
}
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_SIZE = 1 << 24;
// Global variables
int length, current_gap;
int suffix_array[MAX_SIZE];
int position[MAX_SIZE];
int temp[MAX_SIZE];
// Compare two suffixes for sorting
bool compare_suffixes(int i, int j) {
if (position[i] != position[j])
return position[i] < position[j];
i += current_gap;
j += current_gap;
return (i < length && j < length) ? position[i] < position[j] : i > j;
}
// Build suffix array for the input string
void build_suffix_array(const string& input) {
length = input.length();
// Initialize arrays
for (int i = 0; i < length; ++i) {
suffix_array[i] = i;
position[i] = input[i];
}
// Main loop: double gap size each iteration
for (current_gap = 1; ; current_gap *= 2) {
sort(suffix_array, suffix_array + length, compare_suffixes);
// Update temporary array with new ranks
temp[0] = 0;
for (int i = 0; i < length - 1; ++i)
temp[i + 1] = temp[i] + compare_suffixes(suffix_array[i], suffix_array[i + 1]);
// Update positions with new ranks
for (int i = 0; i < length; ++i)
position[suffix_array[i]] = temp[i];
// Exit when all suffixes have unique ranks
if (temp[length - 1] == length - 1)
break;
}
}
int main() {
string s;
cin >> s;
s += '$';
build_suffix_array(s);
for (int i = 0; i < s.size(); ++i)
cout << suffix_array[i] << ' ';
}
این کد، پیادهسازی یکی از روشهای کلاسیک برای ساخت آرایه پسوندی است که با نام "الگوریتم دوبرابر کردن" (Doubling Algorithm) شناخته میشود. این الگوریتم به جای مرتبسازی مستقیم پسوندهای رشته، با استفاده از یک رویکرد تکراری و گام به گام، این کار را انجام میدهد.
این الگوریتم در هر مرحله، طول پیشوندی که برای مرتبسازی استفاده میشود را دو برابر میکند.
در ابتدا (با $current\_gap = 1$):
الگوریتم در یک حلقه بینهایت اجرا میشود که در هر تکرار، $current\_gap$ (فاصله) را دو برابر میکند (1، 2، 4، 8 و…).
پس از هر مرتبسازی، رتبههای جدید برای پسوندها محاسبه میشود.
حلقه زمانی به پایان میرسد که تمام پسوندها رتبههای منحصربهفردی پیدا کنند، یعنی $temp[length-1]$ برابر با $length-1$ شود. این به این معنی است که مرتبسازی به طور کامل انجام شده و آرایه پسوندی نهایی ساخته شده است.
افزودن کاراکتر $\\texttt{\$}$ به انتهای رشته برای تضمین این است که تمامی پسوندها از نظر لغتنامهای از هم متمایز باشند و پسوندهای کوتاهتر (که پیشوند پسوندهای بلندتر هستند) همیشه در انتها قرار بگیرند.
این الگوریتم به دلیل وجود حلقه دوبرابر کردن (که $log(N)$ بار اجرا میشود) و فراخوانی تابع $sort$ در داخل آن، دارای پیچیدگی زمانی $\mathcal{O}(N log^2 N)$ است.
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_SIZE = 1 << 20;
// Global variables
int length, current_gap;
int suffix_array[MAX_SIZE];
int position[MAX_SIZE];
int temp[MAX_SIZE];
vector<int> by_second[MAX_SIZE], by_first[MAX_SIZE];
// Compare two suffixes for sorting
bool compare_suffixes(int i, int j) {
if (position[i] != position[j])
return position[i] < position[j];
i += current_gap;
j += current_gap;
return (i < length && j < length) ? position[i] < position[j] : i > j;
}
// Build suffix array for the input string
void build_suffix_array(const string& input) {
length = input.length();
// Initialize arrays
for (int i = 0; i < length; ++i) {
suffix_array[i] = i;
position[i] = input[i];
}
// Main loop: double gap size each iteration
for (current_gap = 1; ; current_gap *= 2) {
// i: position[i], position[i + gap]
for (int i = 0; i < MAX_SIZE; ++i) {
by_first[i].clear();
by_second[i].clear();
}
for (int i = 0; i < length; ++i)
by_second[i + current_gap < length ? position[i + current_gap] : 0].push_back(i);
for (int i = 0; i < MAX_SIZE; ++i)
for (auto &j : by_second[i])
by_first[position[j]].push_back(j);
int sz = 0;
for (int i = 0; i < MAX_SIZE; ++i)
for (auto &j : by_first[i])
suffix_array[sz++] = j;
// Update temporary array with new ranks
temp[0] = 1;
for (int i = 0; i < length - 1; ++i)
temp[i + 1] = temp[i] + compare_suffixes(suffix_array[i], suffix_array[i + 1]);
// Update positions with new ranks
for (int i = 0; i < length; ++i)
position[suffix_array[i]] = temp[i];
// Exit when all suffixes have unique ranks
if (temp[length - 1] == length)
break;
}
}
int main() {
string s;
cin >> s;
s += '$';
build_suffix_array(s);
for (int i = 0; i < s.size(); ++i)
cout << suffix_array[i] << ' ';
}