آرایه پسوندی (Suffix Array) یک ساختار داده است که در علوم کامپیوتر کاربرد دارد. به زبان ساده، آرایه پسوندی یک آرایه از اعداد صحیح است که نشان‌دهنده موقعیت شروع همه پسوندهای یک رشته، به ترتیب الفبایی است.

فرض کنید یک رشته به نام $S$ داریم.

1. ابتدا، تمام پسوندهای ممکن از این رشته را استخراج می‌کنیم.
2. سپس، این پسوندها را به صورت الفبایی مرتب می‌کنیم.
3. در نهایت، آرایه پسوندی را می‌سازیم که شامل اندیس‌های شروع این پسوندهای مرتب شده در رشته اصلی است.

مثال:

فرض کنید رشته $\texttt{S = "banana"}$ را داریم.

1. پسوندهای رشته:
   1. "banana" (شروع از اندیس 0)
   2. "anana" (شروع از اندیس 1)
   3. "nana" (شروع از اندیس 2)
   4. "ana" (شروع از اندیس 3)
   5. "na" (شروع از اندیس 4)
   6. "a" (شروع از اندیس 5)
2. مرتب‌سازی الفبایی پسوندها:
   1. "a" (اندیس 5)
   2. "ana" (اندیس 3)
   3. "anana" (اندیس 1)
   4. "banana" (اندیس 0)
   5. "na" (اندیس 4)
   6. "nana" (اندیس 2)
3. آرایه پسوندی:
   1. با توجه به ترتیب بالا، آرایه پسوندی به شکل زیر خواهد بود:
   2. [5, 3, 1, 0, 4, 2]

آرایه پسوندی کاربردهای زیادی دارد، از جمله:

1. جستجوی الگو: با استفاده از جستجوی دودویی بر روی آرایه پسوندی، می‌توان به سرعت وجود یک الگو (زیررشته) را در متن پیدا کرد.
2. فشرده‌سازی داده‌ها: در برخی الگوریتم‌های فشرده‌سازی، مانند الگوریتم BWT (Burrows-Wheeler Transform)، از آرایه پسوندی استفاده می‌شود.
3. بیوانفورماتیک: در تحلیل توالی‌های DNA و پروتئین‌ها برای یافتن الگوهای تکراری و مشابه.
4. شباهت‌سنجی رشته‌ها: برای پیدا کردن طولانی‌ترین زیررشته مشترک بین دو یا چند رشته.

آرایه پسوندی معمولاً با مرتب‌سازی تمامی پسوندهای یک رشته ساخته می‌شود. ساخت آرایه پسوندی با استفاده از جستجوی دودویی (Binary Search) و هش (Hash) یک روش برای مقایسه سریع‌تر پسوندها در طول فرآیند مرتب‌سازی است. این رویکرد به جای مقایسه حرف به حرف، از مقادیر هش برای سرعت بخشیدن به مقایسه‌ها استفاده می‌کند.

در این روش، از هش چندجمله‌ای (Polynomial Hashing) استفاده می‌شود. این تکنیک به هر پسوند یک مقدار عددی (هش) اختصاص می‌دهد. این کار به ما اجازه می‌دهد که پسوندها را در زمان ثابت $\mathcal{O}(1)$ با هم مقایسه کنیم.

1. پیش‌محاسبه هش‌ها: ابتدا، هش تمام پیشوندهای رشته اصلی را محاسبه می‌کنیم و در یک آرایه ذخیره می‌کنیم. با استفاده از این آرایه پیش‌محاسبه‌شده، می‌توانیم هش هر زیررشته (و در نتیجه هر پسوند) را در زمان O(1) به دست آوریم.
2. کاهش زمان مقایسه: به جای مقایسه حرف به حرف دو پسوند که زمان آن به طول پسوندها بستگی دارد، می‌توانیم ابتدا مقادیر هش آن‌ها را مقایسه کنیم. اگر هش‌ها متفاوت باشند، پسوندها نیز متفاوت هستند. اگر هش‌ها یکسان باشند، احتمالاً پسوندها نیز یکسان هستند (با در نظر گرفتن احتمال برخورد هش).

جستجوی دودویی برای مقایسه دقیق‌تر پسوندها به کار می‌رود و به جای مرتب‌سازی مستقیم، به سرعت طول طولانی‌ترین پیشوند مشترک (LCP) را بین دو پسوند پیدا می‌کند.

1. یافتن LCP با جستجوی دودویی: برای مقایسه دو پسوند $S[i..]$ و $S[j..]$، از جستجوی دودویی برای پیدا کردن طول بلندترین پیشوند مشترک آن‌ها استفاده می‌کنیم.
2. استفاده از هش‌ها در جستجوی دودویی: در هر مرحله از جستجوی دودویی، به جای مقایسه زیررشته‌ها، هش آن‌ها را مقایسه می‌کنیم تا بفهمیم آیا تا یک طول مشخص (مثلاً $k$) با هم برابر هستند یا نه. این کار مقایسه را بسیار سریع‌تر می‌کند.

الگوریتم ساخت آرایه پسوندی با این رویکرد به صورت زیر است:

1. پیش‌محاسبه: هش پیشوندهای رشته اصلی را محاسبه کنید.
2. تعریف تابع مقایسه: یک تابع مقایسه تعریف کنید که دو پسوند را به عنوان ورودی می‌گیرد و از جستجوی دودویی و هش‌ها برای تعیین ترتیب آن‌ها استفاده می‌کند. این تابع ابتدا با جستجوی دودویی طول طولانی‌ترین پیشوند مشترک دو پسوند را پیدا می‌کند و سپس اولین حرف پس از این طول مشترک را برای تعیین ترتیب نهایی مقایسه می‌کند.
3. مرتب‌سازی: از یک الگوریتم مرتب‌سازی سریع استفاده کنید تا تمامی پسوندها را بر اساس تابع مقایسه‌ای که تعریف کردید، مرتب کنید.
4. ساخت آرایه پسوندی: پس از مرتب شدن پسوندها، آرایه‌ای از اندیس‌های شروع آن‌ها را به ترتیب ایجاد کنید که همان آرایه پسوندی است.

این روش به طور کلی پیچیدگی زمانی $\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$):

• $suffix\_array$: آرایه‌ای از اندیس‌ها است که در ابتدا به صورت $[0, 1, 2, …, length-1]$ پر شده است. این آرایه در نهایت پس از مرتب‌سازی، اندیس شروع پسوندها را نگهداری می‌کند.
• $position$: آرایه‌ای است که رتبه هر پسوند را بر اساس اولین حرف آن نگه می‌دارد. در واقع، $position[i]$ برابر با کد اسکی حرف $input[i]$ است.

الگوریتم در یک حلقه بی‌نهایت اجرا می‌شود که در هر تکرار، $current\_gap$ (فاصله) را دو برابر می‌کند (1، 2، 4، 8 و…).

• مرتب‌سازی: در هر تکرار، $std::sort$ بر روی $suffix\_array$ با استفاده از تابع مقایسه‌گر سفارشی $compare\_suffixes$ فراخوانی می‌شود.
  • تابع $compare\_suffixes$: این تابع کلید اصلی الگوریتم است. برای مقایسه دو پسوند که از اندیس $i$ و $j$ شروع می‌شوند، از رتبه‌های قبلی ($position$) استفاده می‌کند.
• ابتدا، رتبه‌های دو بلوک اول به طول $current\_gap$ را مقایسه می‌کند: $position[i]$ و $position[j]$.
• اگر این رتبه‌ها برابر باشند، رتبه‌های دو بلوک دوم به طول $current\_gap$ را مقایسه می‌کند: $position[i + current\_gap]$ و $position[j + current\_gap]$.
• به این ترتیب، در هر گام، پسوندها را بر اساس ۲ * $current\_gap$ حرف اولشان مرتب می‌کند.

پس از هر مرتب‌سازی، رتبه‌های جدید برای پسوندها محاسبه می‌شود.

• آرایه $temp$ با رتبه‌های جدید پر می‌شود. اگر دو پسوند پشت سر هم در $suffix\_array$ با هم برابر باشند، رتبه یکسانی می‌گیرند.
• سپس، آرایه $position$ با رتبه‌های جدید به‌روزرسانی می‌شود.

حلقه زمانی به پایان می‌رسد که تمام پسوندها رتبه‌های منحصربه‌فردی پیدا کنند، یعنی $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] << ' ';
}