پرش به محتویات

آرایه پسوندی (Suffix Array)

تعریف

فرض کنید $s$ یک رشته به طول $n$ باشد. $i$-امین پسوند رشته $s$ زیررشته $s[i \ldots n - 1]$ است.

آرایه پسوندی (suffix array) شامل اعداد صحیحی است که اندیس شروع تمام پسوندهای یک رشتهٔ معین را، پس از مرتب‌سازی آن پسوندها، نشان می‌دهد.

به عنوان مثال، رشته $s = abaab$ را در نظر بگیرید. تمام پسوندها به شرح زیر هستند:

$$\begin{array}{ll} 0. & abaab \\ 1. & baab \\ 2. & aab \\ 3. & ab \\ 4. & b \end{array}$$

پس از مرتب‌سازی این رشته‌ها:

$$\begin{array}{ll} 2. & aab \\ 3. & ab \\ 0. & abaab \\ 4. & b \\ 1. & baab \end{array}$$

بنابراین، آرایه پسوندی برای رشته $s$ برابر با $(2,~ 3,~ 0,~ 4,~ 1)$ خواهد بود.

این ساختمان داده به طور گسترده در حوزه‌هایی مانند فشرده‌سازی داده، بیوانفورماتیک و به طور کلی در هر حوزه‌ای که با رشته‌ها و مسائل تطبیق رشته سروکار دارد، استفاده می‌شود.

ساخت

رویکرد $O(n^2 \log n)$

این ساده‌ترین رویکرد است. تمام پسوندها را استخراج کرده و با استفاده از quicksort یا mergesort مرتب می‌کنیم و همزمان اندیس‌های اصلی آن‌ها را نگه می‌داریم. مرتب‌سازی به $O(n \log n)$ مقایسه نیاز دارد و از آنجایی که مقایسه دو رشته نیز $O(n)$ زمان می‌برد، پیچیدگی نهایی $O(n^2 \log n)$ خواهد بود.

رویکرد $O(n \log n)$

به بیان دقیق، الگوریتم زیر پسوندها را مرتب نمی‌کند، بلکه شیفت‌های دوری یک رشته را مرتب می‌کند. با این حال، می‌توانیم به راحتی الگوریتمی برای مرتب‌سازی پسوندها از آن استخراج کنیم: کافی است یک کاراکتر دلخواه که از تمام کاراکترهای رشته کوچک‌تر است را به انتهای رشته اضافه کنیم. معمولاً از نماد $ استفاده می‌شود. در این صورت، ترتیب شیفت‌های دوری مرتب‌شده معادل ترتیب پسوندهای مرتب‌شده خواهد بود، همانطور که در اینجا با رشته $dabbb$ نشان داده شده است.

$$\begin{array}{lll} 1. & abbb\$d & abbb \\ 4. & b\$dabb & b \\ 3. & bb\$dab & bb \\ 2. & bbb\$da & bbb \\ 0. & dabbb\$ & dabbb \end{array}$$

از آنجایی که قصد مرتب‌سازی شیفت‌های دوری را داریم، زیررشته‌های دوری را در نظر خواهیم گرفت. ما از نماد $s[i \dots j]$ برای زیررشته $s$ استفاده خواهیم کرد، حتی اگر $i > j$ باشد. در این حالت، منظور ما در واقع رشته $s[i \dots n-1] + s[0 \dots j]$ است. علاوه بر این، تمام اندیس‌ها را به پیمانه طول رشته $s$ در نظر می‌گیریم و برای سادگی، عمل پیمانه را حذف می‌کنیم.

الگوریتمی که بحث می‌کنیم، $\lceil \log n \rceil + 1$ تکرار انجام می‌دهد. در $k$-امین تکرار ($k = 0 \dots \lceil \log n \rceil$) ما $n$ زیررشتهٔ دوری از $s$ به طول $2^k$ را مرتب می‌کنیم. پس از تکرار $\lceil \log n \rceil$-ام، زیررشته‌هایی به طول $2^{\lceil \log n \rceil} \ge n$ مرتب خواهند شد، که این معادل مرتب‌سازی کامل شیفت‌های دوری است.

در هر تکرار الگوریتم، علاوه بر جایگشت $p[0 \dots n-1]$ که در آن $p[i]$ اندیس $i$-امین زیررشته (که از $i$ شروع شده و طول $2^k$ دارد) در ترتیب مرتب‌شده است، یک آرایه $c[0 \dots n-1]$ را نیز نگهداری خواهیم کرد که در آن $c[i]$ متناظر با کلاس هم‌ارزی است که زیررشته به آن تعلق دارد. زیرا برخی از زیررشته‌ها یکسان خواهند بود و الگوریتم باید با آنها به طور یکسان رفتار کند. برای راحتی، کلاس‌ها با اعدادی از صفر شماره‌گذاری می‌شوند. علاوه بر این، اعداد $c[i]$ به گونه‌ای تخصیص داده می‌شوند که اطلاعات مربوط به ترتیب را حفظ کنند: اگر یک زیررشته از دیگری کوچک‌تر باشد، باید برچسب کلاس کوچک‌تری نیز داشته باشد. تعداد کلاس‌های هم‌ارزی در متغیر $\text{classes}$ ذخیره می‌شود.

بیایید به یک مثال نگاه کنیم. رشته $s = aaba$ را در نظر بگیرید. زیررشته‌های دوری و آرایه‌های متناظر $p[]$ و $c[]$ برای هر تکرار آورده شده است:

$$\begin{array}{cccc} 0: & (a,~ a,~ b,~ a) & p = (0,~ 1,~ 3,~ 2) & c = (0,~ 0,~ 1,~ 0)\\ 1: & (aa,~ ab,~ ba,~ aa) & p = (0,~ 3,~ 1,~ 2) & c = (0,~ 1,~ 2,~ 0)\\ 2: & (aaba,~ abaa,~ baaa,~ aaab) & p = (3,~ 0,~ 1,~ 2) & c = (1,~ 2,~ 3,~ 0)\\ \end{array}$$

شایان ذکر است که مقادیر $p[]$ می‌توانند متفاوت باشند. به عنوان مثال، در تکرار 0-ام، آرایه می‌توانست $p = (3,~ 1,~ 0,~ 2)$ یا $p = (3,~ 0,~ 1,~ 2)$ نیز باشد. همه این گزینه‌ها زیررشته‌ها را به ترتیب مرتب‌شده جایگشت می‌دهند. بنابراین همه آنها معتبر هستند. در عین حال، آرایه $c[]$ ثابت است و هیچ ابهامی در آن وجود ندارد.

حال بیایید بر روی پیاده‌سازی الگوریتم تمرکز کنیم. تابعی خواهیم نوشت که یک رشته $s$ را گرفته و جایگشت شیفت‌های دوری مرتب‌شده را برمی‌گرداند.

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;

در ابتدا (در تکرار 0-ام) باید زیررشته‌های دوری به طول ۱ را مرتب کنیم، یعنی باید تمام کاراکترهای رشته را مرتب کرده و آنها را به کلاس‌های هم‌ارزی تقسیم کنیم (نمادهای یکسان در یک کلاس قرار می‌گیرند). این کار را می‌توان به سادگی انجام داد، به عنوان مثال، با استفاده از مرتب‌سازی شمارشی (counting sort). برای هر کاراکتر، تعداد دفعات تکرار آن در رشته را می‌شماریم و سپس از این اطلاعات برای ایجاد آرایه $p[]$ استفاده می‌کنیم. پس از آن، آرایه $p[]$ را پیمایش کرده و با مقایسه کاراکترهای مجاور، $c[]$ را می‌سازیم.

    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }

اکنون باید در مورد مرحله تکرار صحبت کنیم. فرض کنید مرحله $k-1$-ام را انجام داده‌ایم و مقادیر آرایه‌های $p[]$ و $c[]$ را برای آن محاسبه کرده‌ایم. می‌خواهیم مقادیر را برای مرحله $k$-ام در زمان $O(n)$ محاسبه کنیم. از آنجایی که این مرحله را $O(\log n)$ بار انجام می‌دهیم، کل الگوریتم دارای پیچیدگی زمانی $O(n \log n)$ خواهد بود.

برای انجام این کار، توجه داشته باشید که زیررشته‌های دوری به طول $2^k$ از دو زیررشته به طول $2^{k-1}$ تشکیل شده‌اند که می‌توانیم آنها را با استفاده از اطلاعات فاز قبلی - یعنی مقادیر کلاس‌های هم‌ارزی $c[]$ - در زمان $O(1)$ با یکدیگر مقایسه کنیم. بنابراین، برای دو زیررشته به طول $2^k$ که از موقعیت $i$ و $j$ شروع می‌شوند، تمام اطلاعات لازم برای مقایسه آنها در زوج‌های $(c[i],~ c[i + 2^{k-1}])$ و $(c[j],~ c[j + 2^{k-1}])$ موجود است.

$$\dots \overbrace{ \underbrace{s_i \dots s_{i+2^{k-1}-1}}_{\text{طول} = 2^{k-1},~ \text{کلاس} = c[i]} \quad \underbrace{s_{i+2^{k-1}} \dots s_{i+2^k-1}}_{\text{طول} = 2^{k-1},~ \text{کلاس} = c[i + 2^{k-1}]} }^{\text{طول} = 2^k} \dots \overbrace{ \underbrace{s_j \dots s_{j+2^{k-1}-1}}_{\text{طول} = 2^{k-1},~ \text{کلاس} = c[j]} \quad \underbrace{s_{j+2^{k-1}} \dots s_{j+2^k-1}}_{\text{طول} = 2^{k-1},~ \text{کلاس} = c[j + 2^{k-1}]} }^{\text{طول} = 2^k} \dots $$

این به ما یک راه حل بسیار ساده می‌دهد: مرتب‌سازی زیررشته‌های به طول $2^k$ بر اساس این زوج اعداد. این کار ترتیب مورد نیاز $p[]$ را به ما می‌دهد. با این حال، یک مرتب‌سازی معمولی در زمان $O(n \log n)$ اجرا می‌شود که ما از آن راضی نیستیم. این تنها الگوریتمی برای ساخت آرایه پسوندی در زمان $O(n \log^2 n)$ به ما می‌دهد.

چگونه می‌توانیم چنین مرتب‌سازی زوج‌ها را به سرعت انجام دهیم؟ از آنجایی که عناصر زوج‌ها از $n$ تجاوز نمی‌کنند، می‌توانیم دوباره از مرتب‌سازی شمارشی استفاده کنیم. با این حال، مرتب‌سازی زوج‌ها با مرتب‌سازی شمارشی کارآمدترین روش نیست. برای دستیابی به یک ثابت پنهان بهتر در پیچیدگی، از ترفند دیگری استفاده خواهیم کرد.

ما در اینجا از تکنیکی استفاده می‌کنیم که مرتب‌سازی مبنایی (radix sort) بر آن استوار است: برای مرتب‌سازی زوج‌ها، ابتدا آن‌ها را بر اساس عنصر دوم مرتب کرده و سپس بر اساس عنصر اول مرتب‌سازی می‌کنیم (با یک مرتب‌سازی پایدار، یعنی مرتب‌سازی بدون برهم زدن ترتیب نسبی عناصر مساوی). اما عناصر دوم در تکرار قبلی از قبل مرتب شده‌اند. بنابراین، برای مرتب‌سازی زوج‌ها بر اساس عنصر دوم، کافی است $2^{k-1}$ را از اندیس‌های موجود در $p[]$ کم کنیم (مثلاً اگر کوچکترین زیررشته به طول $2^{k-1}$ از موقعیت $i$ شروع شود، آنگاه زیررشته به طول $2^k$ با کوچکترین نیمه دوم از موقعیت $i - 2^{k-1}$ شروع می‌شود).

بنابراین تنها با تفریق‌های ساده می‌توانیم عناصر دوم زوج‌ها را در $p[]$ مرتب کنیم. اکنون باید یک مرتب‌سازی پایدار بر اساس عناصر اول انجام دهیم. همانطور که قبلاً ذکر شد، این کار را می‌توان با مرتب‌سازی شمارشی انجام داد.

تنها کار باقی‌مانده محاسبه کلاس‌های هم‌ارزی $c[]$ است، اما مانند قبل، این کار را می‌توان با پیمایش ساده جایگشت مرتب‌شده $p[]$ و مقایسه زوج‌های همسایه انجام داد.

در اینجا پیاده‌سازی باقی‌مانده آمده است. ما از آرایه‌های موقت $pn[]$ و $cn[]$ برای ذخیره جایگشت بر اساس عناصر دوم و اندیس‌های کلاس هم‌ارزی جدید استفاده می‌کنیم.

    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}
این الگوریتم به زمان $O(n \log n)$ و حافظه $O(n)$ نیاز دارد. برای سادگی، ما از کل دامنه ASCII به عنوان الفبا استفاده کردیم.

اگر مشخص باشد که رشته فقط شامل زیرمجموعه‌ای از کاراکترها است، به عنوان مثال فقط حروف کوچک انگلیسی، پیاده‌سازی را می‌توان بهینه‌سازی کرد، اما ضریب بهینه‌سازی احتمالاً ناچیز خواهد بود، زیرا اندازه الفبا فقط در تکرار اول اهمیت دارد. هر تکرار دیگر به تعداد کلاس‌های هم‌ارزی بستگی دارد که ممکن است به سرعت به $O(n)$ برسد حتی اگر در ابتدا رشته‌ای بر روی الفبایی به اندازه ۲ باشد.

همچنین توجه داشته باشید که این الگوریتم فقط شیفت‌های دوری را مرتب می‌کند. همانطور که در ابتدای این بخش ذکر شد، می‌توانیم ترتیب مرتب‌شده پسوندها را با اضافه کردن کاراکتری که از تمام کاراکترهای دیگر رشته کوچکتر است، تولید کنیم و سپس این رشته حاصل را بر اساس شیفت‌های دوری مرتب کنیم، به عنوان مثال با مرتب‌سازی شیفت‌های دوری $s + \$$. این کار به وضوح آرایه پسوندی $s$ را به ما می‌دهد، با این تفاوت که $|s|$ در ابتدای آن قرار دارد.

vector<int> suffix_array_construction(string s) {
    s += "$";
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

کاربردها

یافتن کوچکترین شیفت دوری

الگوریتم بالا تمام شیفت‌های دوری را مرتب می‌کند (بدون اضافه کردن کاراکتر به رشته)، و بنابراین $p[0]$ موقعیت کوچکترین شیفت دوری را نشان می‌دهد.

یافتن یک زیررشته در یک رشته

وظیفه یافتن یک رشته $s$ در داخل یک متن $t$ به صورت آنلاین است - ما متن $t$ را از قبل می‌دانیم، اما رشته $s$ را نه. ما می‌توانیم آرایه پسوندی را برای متن $t$ در زمان $O(|t| \log |t|)$ ایجاد کنیم. اکنون می‌توانیم به روش زیر به دنبال زیررشته $s$ بگردیم. وقوع $s$ باید پیشوندی از یکی از پسوندهای $t$ باشد. از آنجایی که ما تمام پسوندها را مرتب کرده‌ایم، می‌توانیم یک جستجوی دودویی برای $s$ در $p$ انجام دهیم. مقایسه پسوند فعلی و زیررشته $s$ در داخل جستجوی دودویی در زمان $O(|s|)$ قابل انجام است، بنابراین پیچیدگی یافتن زیررشته $O(|s| \log |t|)$ است. همچنین توجه داشته باشید که اگر زیررشته چندین بار در $t$ تکرار شود، تمام وقوع‌ها در $p$ کنار یکدیگر قرار خواهند گرفت. بنابراین، تعداد وقوع‌ها را می‌توان با یک جستجوی دودویی دوم پیدا کرد و تمام وقوع‌ها را به راحتی چاپ کرد.

مقایسه دو زیررشته از یک رشته

می‌خواهیم بتوانیم دو زیررشته با طول یکسان از یک رشته $s$ را در زمان $O(1)$ مقایسه کنیم، یعنی بررسی کنیم که آیا زیررشته اول از دومی کوچکتر است یا نه.

برای این کار، آرایه پسوندی را در زمان $O(|s| \log |s|)$ می‌سازیم و تمام نتایج میانی کلاس‌های هم‌ارزی $c[]$ را ذخیره می‌کنیم.

با استفاده از این اطلاعات، می‌توانیم هر دو زیررشته‌ای که طول آنها توانی از دو باشد را در O(1) مقایسه کنیم: برای این کار کافی است کلاس‌های هم‌ارزی هر دو زیررشته را مقایسه کنیم. اکنون می‌خواهیم این روش را برای زیررشته‌هایی با طول دلخواه تعمیم دهیم.

بیایید دو زیررشته به طول $l$ با اندیس‌های شروع $i$ و $j$ را مقایسه کنیم. بزرگترین طول بلوکی که در یک زیررشته با این طول قرار می‌گیرد را پیدا می‌کنیم: بزرگترین $k$ به طوری که $2^k \le l$. سپس مقایسه دو زیررشته را می‌توان با مقایسه دو بلوک همپوشان به طول $2^k$ جایگزین کرد: ابتدا باید دو بلوک که از $i$ و $j$ شروع می‌شوند را مقایسه کنید، و اگر اینها مساوی بودند، دو بلوک که در موقعیت‌های $i + l - 1$ و $j + l - 1$ تمام می‌شوند را مقایسه کنید:

$$\dots \overbrace{\underbrace{s_i \dots s_{i+l-2^k} \dots s_{i+2^k-1}}_{2^k} \dots s_{i+l-1}}^{\text{اولی}} \dots \overbrace{\underbrace{s_j \dots s_{j+l-2^k} \dots s_{j+2^k-1}}_{2^k} \dots s_{j+l-1}}^{\text{دومی}} \dots$$
$$\dots \overbrace{s_i \dots \underbrace{s_{i+l-2^k} \dots s_{i+2^k-1} \dots s_{i+l-1}}_{2^k}}^{\text{اولی}} \dots \overbrace{s_j \dots \underbrace{s_{j+l-2^k} \dots s_{j+2^k-1} \dots s_{j+l-1}}_{2^k}}^{\text{دومی}} \dots$$

در اینجا پیاده‌سازی مقایسه آمده است. توجه داشته باشید که فرض بر این است که تابع با $k$ از قبل محاسبه شده فراخوانی می‌شود. $k$ را می‌توان با $\lfloor \log l \rfloor$ محاسبه کرد، اما کارآمدتر است که تمام مقادیر $k$ را برای هر $l$ از قبل محاسبه کنیم. به عنوان مثال، مقاله مربوط به جدول پراکنده (Sparse Table) را ببینید که از ایده مشابهی استفاده می‌کند و تمام مقادیر $\log$ را محاسبه می‌کند.

int compare(int i, int j, int l, int k) {
    pair<int, int> a = {c[k][i], c[k][(i+l-(1 << k))%n]};
    pair<int, int> b = {c[k][j], c[k][(j+l-(1 << k))%n]};
    return a == b ? 0 : a < b ? -1 : 1;
}

طولانی‌ترین پیشوند مشترک دو زیررشته با حافظه اضافی

برای یک رشته داده شده $s$، می‌خواهیم طولانی‌ترین پیشوند مشترک (LCP) دو پسوند دلخواه با موقعیت $i$ و $j$ را محاسبه کنیم.

روشی که در اینجا شرح داده شده است از حافظه اضافی $O(|s| \log |s|)$ استفاده می‌کند. رویکردی کاملاً متفاوت که فقط از مقدار خطی حافظه استفاده می‌کند در بخش بعدی شرح داده شده است.

ما آرایه پسوندی را در زمان $O(|s| \log |s|)$ می‌سازیم و نتایج میانی آرایه‌های $c[]$ را از هر تکرار به خاطر می‌سپاریم.

بیایید LCP را برای دو پسوند که از $i$ و $j$ شروع می‌شوند محاسبه کنیم. ما می‌توانیم هر دو زیررشته با طولی برابر با توانی از دو را در $O(1)$ مقایسه کنیم. برای انجام این کار، رشته‌ها را بر اساس توان‌های دو (از بزرگ‌ترین به کوچک‌ترین توان) مقایسه می‌کنیم و اگر زیررشته‌های این طول یکسان بودند، طول برابر را به پاسخ اضافه کرده و به بررسی LCP در سمت راست بخش برابر ادامه می‌دهیم، یعنی به $i$ و $j$ توان فعلی دو اضافه می‌شود.

int lcp(int i, int j) {
    int ans = 0;
    for (int k = log_n; k >= 0; k--) {
        if (c[k][i % n] == c[k][j % n]) {
            ans += 1 << k;
            i += 1 << k;
            j += 1 << k;
        }
    }
    return ans;
}

در اینجا log_n یک ثابت است که برابر با لگاریتم $n$ در پایه ۲ گرد شده به پایین است.

طولانی‌ترین پیشوند مشترک دو زیررشته بدون حافظه اضافی

ما همان وظیفه بخش قبل را داریم. باید طولانی‌ترین پیشوند مشترک (LCP) را برای دو پسوند از یک رشته $s$ محاسبه کنیم.

برخلاف روش قبلی، این روش فقط از حافظه $O(|s|)$ استفاده می‌کند. نتیجه پیش‌پردازش یک آرایه خواهد بود (که خود منبع مهمی از اطلاعات در مورد رشته است و بنابراین برای حل مسائل دیگر نیز استفاده می‌شود). پرس‌وجوهای LCP را می‌توان با انجام پرس‌وجوهای RMQ (پرس‌وجوهای کمینه بازه) در این آرایه پاسخ داد، بنابراین برای پیاده‌سازی‌های مختلف امکان دستیابی به زمان پرس‌وجوی لگاریتمی و حتی ثابت وجود دارد.

اساس این الگوریتم ایده زیر است: ما طولانی‌ترین پیشوند مشترک را برای هر جفت پسوند مجاور در ترتیب مرتب‌شده محاسبه می‌کنیم. به عبارت دیگر، ما یک آرایه $\text{lcp}[0 \dots n-2]$ می‌سازیم، که در آن $\text{lcp}[i]$ برابر با طول طولانی‌ترین پیشوند مشترک پسوندهایی است که از $p[i]$ و $p[i+1]$ شروع می‌شوند. این آرایه پاسخی برای هر دو پسوند مجاور رشته به ما می‌دهد. سپس پاسخ برای دو پسوند دلخواه، که لزوماً همسایه نیستند، را می‌توان از این آرایه به دست آورد. در واقع، فرض کنید درخواست، محاسبه LCP پسوندهای $p[i]$ و $p[j]$ باشد. آنگاه پاسخ به این پرس‌وجو برابر با $\min(lcp[i],~ lcp[i+1],~ \dots,~ lcp[j-1])$ خواهد بود.

بنابراین اگر چنین آرایه $\text{lcp}$ ای داشته باشیم، مسئله به RMQ کاهش می‌یابد که راه‌حل‌های بسیار متنوعی با پیچیدگی‌های مختلف دارد.

بنابراین وظیفه اصلی ساختن این آرایه $\text{lcp}$ است. ما از الگوریتم Kasai استفاده خواهیم کرد که می‌تواند این آرایه را در زمان $O(n)$ محاسبه کند.

دو پسوند مجاور در ترتیب مرتب‌شده (ترتیب آرایه پسوندی) را در نظر بگیرید. فرض کنید موقعیت شروع آنها $i$ و $j$ و $\text{lcp}$ آنها برابر با $k > 0$ باشد. اگر حرف اول هر دو پسوند را حذف کنیم - یعنی پسوندهای $i+1$ و $j+1$ را در نظر بگیریم - واضح است که $\text{lcp}$ این دو برابر $k - 1$ خواهد بود. با این حال، نمی‌توانیم از این مقدار استفاده کرده و آن را در آرایه $\text{lcp}$ بنویسیم، زیرا این دو پسوند ممکن است در ترتیب مرتب‌شده کنار هم نباشند. پسوند $i+1$ البته از پسوند $j+1$ کوچکتر خواهد بود، اما ممکن است پسوندهای دیگری بین آنها وجود داشته باشد. اما از آنجایی که می‌دانیم LCP بین دو پسوند، کمینه مقدار تمام گذارهاست، می‌دانیم که LCP بین هر دو جفت در آن بازه باید حداقل $k-1$ باشد، به ویژه بین $i+1$ و پسوند بعدی‌اش. و ممکن است بزرگ‌تر هم باشد.

اکنون می‌توانیم الگوریتم را پیاده‌سازی کنیم. ما روی پسوندها به ترتیب موقعیتشان در رشته اصلی پیمایش می‌کنیم. به این ترتیب می‌توانیم از مقدار آخر $k$ دوباره استفاده کنیم، زیرا رفتن از پسوند $i$ به پسوند $i+1$ دقیقاً مانند حذف حرف اول است. به یک آرایه اضافی $\text{rank}$ نیاز خواهیم داشت که موقعیت یک پسوند را در لیست مرتب‌شده پسوندها به ما می‌دهد.

vector<int> lcp_construction(string const& s, vector<int> const& p) {
    int n = s.size();
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;

    int k = 0;
    vector<int> lcp(n-1, 0);
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k])
            k++;
        lcp[rank[i]] = k;
        if (k)
            k--;
    }
    return lcp;
}

به راحتی می‌توان دید که ما $k$ را حداکثر $O(n)$ بار کاهش می‌دهیم (در هر تکرار حداکثر یک بار، به جز زمانی که $\text{rank}[i] == n-1$ باشد که مستقیماً آن را به ۰ بازنشانی می‌کنیم)، و از آنجا که LCP بین دو رشته حداکثر $n-1$ است، ما همچنین $k$ را فقط $O(n)$ بار افزایش خواهیم داد. بنابراین، الگوریتم در زمان $O(n)$ اجرا می‌شود.

تعداد زیررشته‌های مختلف

ما رشته $s$ را با محاسبه آرایه پسوندی و آرایه LCP پیش‌پردازش می‌کنیم. با استفاده از این اطلاعات، می‌توانیم تعداد زیررشته‌های مختلف در رشته را محاسبه کنیم.

برای انجام این کار، به این فکر می‌کنیم که کدام زیررشته‌های جدید از موقعیت $p[0]$ شروع می‌شوند، سپس از $p[1]$ و غیره. در واقع، ما پسوندها را به ترتیب مرتب‌شده در نظر می‌گیریم و می‌بینیم کدام پیشوندها زیررشته‌های جدیدی ایجاد می‌کنند. بنابراین، به طور تصادفی هیچ‌کدام را از قلم نخواهیم انداخت.

از آنجایی که پسوندها مرتب شده‌اند، واضح است که پسوند فعلی $p[i]$ برای تمام پیشوندهایش زیررشته‌های جدیدی ایجاد می‌کند، به جز پیشوندهایی که با پسوند $p[i-1]$ مشترک هستند. بنابراین، تمام پیشوندهای آن به جز $\text{lcp}[i-1]$ تای اول. از آنجایی که طول پسوند فعلی $n - p[i]$ است، تعداد $n - p[i] - \text{lcp}[i-1]$ پیشوند جدید از $p[i]$ شروع می‌شود. با جمع زدن روی تمام پسوندها، به پاسخ نهایی می‌رسیم:

$$\sum_{i=0}^{n-1} (n - p[i]) - \sum_{i=0}^{n-2} \text{lcp}[i] = \frac{n^2 + n}{2} - \sum_{i=0}^{n-2} \text{lcp}[i]$$

مسائل تمرینی