Дагаврын массив¶

Тодорхойлолт¶

$s$ нь $n$ урттай тэмдэгт мөр байг. $s$-ийн $i$ дахь дагавар нь $s[i \ldots n - 1]$ дэд мөр юм.

Дагаврын массив нь дээр дурдсан дагаврууд эрэмбэлэгдсэний дараа өгөгдсөн тэмдэгт мөрийн бүх дагаврын эхлэлийн индексийг илэрхийлэх бүхэл тоонуудыг агуулна.

Жишээ болгон $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)$ approach¶

Энэ бол хамгийн гэнэн арга юм. Бүх дагаврыг аваад тэдгээрийг quicksort буюу mergesort ашиглан эрэмбэлж, нэгэн зэрэг тэдгээрийн анхны индексийг хадгална. Эрэмбэлэлт $O(n \log n)$ харьцуулалт ашигладаг ба хоёр тэмдэгт мөрийг харьцуулахад нэмэлтээр $O(n)$ хугацаа зарцуулагдах тул бид эцсийн $O(n^2 \log n)$ complexity-г авна.

$O(n \log n)$ approach¶

Чанд хэлэхэд дараах алгоритм нь дагавруудыг биш, харин тэмдэгт мөрийн циклик шилжилтүүдийг эрэмбэлнэ. Гэвч бид үүнээс дагавар эрэмбэлэх алгоритмыг маш амархан гаргаж авч болно: тэмдэгт мөрийн төгсгөлд тэмдэгт мөрийн дурын тэмдэгтээс бага дурын тэмдэгт залгахад хангалттай. $ тэмдэгтийг ашиглах нь түгээмэл. Тэгвэл эрэмбэлэгдсэн циклик шилжилтүүдийн дараалал нь эрэмбэлэгдсэн дагавруудын дараалалтай эквивалент болно, үүнийг энд $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}$$

Бид циклик шилжилтүүдийг эрэмбэлэх гэж байгаа тул циклик дэд мөрүүдийг авч үзнэ. Бид $i > j$ байсан ч $s$-ийн дэд мөрийн хувьд $s[i \dots j]$ тэмдэглэгээг ашиглана. Энэ тохиолдолд бид үнэндээ $s[i \dots n-1] + s[0 \dots j]$ тэмдэгт мөрийг хэлж байгаа юм. Түүнчлэн бид бүх индексийг $s$-ийн уртаар модуль авах ба энгийн байдлын үүднээс модулийн үйлдлийг орхино.

Бидний хэлэлцэх алгоритм $\lceil \log n \rceil + 1$ давталт гүйцэтгэнэ. $k$ дахь давталтад ($k = 0 \dots \lceil \log n \rceil$) бид $s$-ийн $2^k$ урттай $n$ циклик дэд мөрийг эрэмбэлнэ. $\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$ дахь давталтад) бид $1$ урттай циклик дэд мөрүүдийг эрэмбэлэх ёстой, өөрөөр хэлбэл бид тэмдэгт мөрийн бүх тэмдэгтийг эрэмбэлж, тэдгээрийг эквивалент ангиудад хуваах ёстой (ижил тэмдэгтүүд ижил ангид оноогдоно). Үүнийг тривиалаар, жишээ нь тоолох эрэмбэлэлт ашиглан хийж болно. Тэмдэгт бүрийн хувьд бид түүнийг тэмдэгт мөрд хэдэн удаа гарч ирэхийг тоолж, дараа нь энэ мэдээллийг ашиглан $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)$ time complexity-тэй байна.

Үүний тулд $2^k$ урттай циклик дэд мөр нь $2^{k-1}$ урттай хоёр дэд мөрөөс бүрдэх ба тэдгээрийг бид өмнөх үе шатны мэдээлэл буюу эквивалент ангиудын утга $c[]$-г ашиглан $O(1)$-д хооронд нь харьцуулж чадахыг анзаар. Тиймээс $i$ ба $j$ байрлалаас эхлэх $2^k$ урттай хоёр дэд мөрийн хувьд тэдгээрийг харьцуулахад шаардлагатай бүх мэдээлэл $(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{length} = 2^{k-1},~ \text{class} = c[i]} \quad \underbrace{s_{i+2^{k-1}} \dots s_{i+2^k-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[i + 2^{k-1}]} }^{\text{length} = 2^k} \dots \overbrace{ \underbrace{s_j \dots s_{j+2^{k-1}-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[j]} \quad \underbrace{s_{j+2^{k-1}} \dots s_{j+2^k-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[j + 2^{k-1}]} }^{\text{length} = 2^k} \dots $$

Энэ нь бидэнд маш энгийн шийдэл өгнө: $2^k$ урттай дэд мөрүүдийг эдгээр тооны хосоор нь эрэмбэл. Энэ нь бидэнд шаардагдах $p[]$ дарааллыг өгнө. Гэвч ердийн эрэмбэлэлт $O(n \log n)$ хугацаанд ажилладаг бөгөөд бид үүнд сэтгэл хангалуун бус байна. Энэ нь бидэнд дагаврын массивыг $O(n \log^2 n)$ хугацаанд байгуулах алгоритмыг л өгнө.

Ийм хосын эрэмбэлэлтийг бид хэрхэн хурдан гүйцэтгэх вэ? Хосын элементүүд $n$-ээс хэтрэхгүй тул бид дахин тоолох эрэмбэлэлт ашиглаж болно. Гэвч тоолох эрэмбэлэлтээр хос эрэмбэлэх нь хамгийн үр ашигтай биш. Complexity-д илүү сайн нуугдмал тогтмолд хүрэхийн тулд бид өөр заль мэх ашиглана.

Бид энд суурийн эрэмбэлэлт суурилдаг аргыг ашиглана: хосуудыг эрэмбэлэхийн тулд бид эхлээд тэдгээрийг хоёр дахь элементээр, дараа нь эхний элементээр эрэмбэлнэ (тогтвортой эрэмбэлэлтээр, өөрөөр хэлбэл тэнцүү элементүүдийн харьцангуй дарааллыг эвдэхгүйгээр эрэмбэлнэ). Гэвч хоёр дахь элементүүд өмнөх давталтад аль хэдийн эрэмбэлэгдсэн байсан. Тиймээс хосуудыг хоёр дахь элементээр эрэмбэлэхийн тулд бид $p[]$ дэх индексүүдээс $2^{k-1}$-г хасахад л хангалттай (жишээ нь хэрэв $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 мужийг ашигласан.

Хэрэв тэмдэгт мөр зөвхөн тэмдэгтүүдийн дэд олонлог, жишээ нь зөвхөн жижиг үсэг агуулдаг нь мэдэгдэж байвал хэрэгжүүлэлтийг оновчилж болох ч оновчлолын үр нөлөө магадгүй ач холбогдолгүй байх болно, учир нь цагаан толгойн хэмжээ зөвхөн эхний давталтад л чухал. Бусад давталт бүр эквивалент ангиудын тооноос хамаарах ба анх $2$ хэмжээтэй цагаан толгой дээрх тэмдэгт мөр байсан ч энэ нь хурдан $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$-ийн ямар нэг дагаврын угтвар байх ёстой. Бид бүх дагаврыг эрэмбэлсэн тул $p$-ээс $s$-г хоёртын хайлтаар хайж болно. Хоёртын хайлтын дотор одоогийн дагавар ба $s$ дэд мөрийг харьцуулахыг $O(|s|)$ хугацаанд хийж болох тул дэд мөр олох complexity нь $O(|s| \log |t|)$ юм. Мөн хэрэв дэд мөр $t$-д олон удаа гарч ирвэл бүх орц $p$-д зэрэгцэн байрлахыг анзаар. Тиймээс орцын тоог хоёр дахь хоёртын хайлтаар олж болох бөгөөд бүх орцыг амархан хэвлэж болно.

Тэмдэгт мөрийн хоёр дэд мөрийг харьцуулах¶

Бид өгөгдсөн $s$ тэмдэгт мөрийн ижил урттай хоёр дэд мөрийг $O(1)$ хугацаанд харьцуулж чаддаг байхыг хүсэж байна, өөрөөр хэлбэл эхний дэд мөр хоёр дахиасаа бага эсэхийг шалгах.

Үүний тулд бид дагаврын массивыг $O(|s| \log |s|)$ хугацаанд байгуулж, эквивалент ангиуд $c[]$-ийн бүх завсрын үр дүнг хадгална.

Энэ мэдээллийг ашиглан бид урт нь хоёрын зэрэгтэй тэнцүү дурын хоёр дэд мөрийг O(1)-д харьцуулж чадна: үүний тулд хоёр дэд мөрийн эквивалент ангиудыг харьцуулахад хангалттай. Одоо бид энэ аргыг дурын урттай дэд мөрд ерөнхийлөхийг хүсэж байна.

$i$ ба $j$ эхлэлийн индекстэй, $l$ урттай хоёр дэд мөрийг харьцуулъя. Бид энэ урттай дэд мөрийн дотор багтах блокийн хамгийн их уртыг олно: $2^k \le l$ байх хамгийн том $k$. Тэгвэл хоёр дэд мөрийг харьцуулахыг $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{first}} \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{second}} \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{first}} \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{second}} \dots$$

Харьцуулалтын хэрэгжүүлэлт энд байна. Функц аль хэдийн тооцоолсон $k$-тайгаар дуудагдана гэж үзсэн болохыг анзаар. $k$-г $\lfloor \log l \rfloor$-ээр тооцоолж болох ч $l$ бүрийн хувьд бүх $k$ утгыг урьдчилан тооцоолох нь илүү үр ашигтай. Жишээ нь ижил төстэй санаа ашиглаж бүх $\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$ тэмдэгт мөрийн хувьд бид $i$ ба $j$ байрлалтай дурын хоёр дагаврын хамгийн урт нийтлэг угтвар (LCP)-ыг тооцоолохыг хүсэж байна.

Энд тайлбарласан арга $O(|s| \log |s|)$ нэмэлт санах ой ашиглана. Зөвхөн шугаман хэмжээний санах ой ашиглах огт өөр аргыг дараагийн хэсэгт тайлбарлав.

Бид дагаврын массивыг $O(|s| \log |s|)$ хугацаанд байгуулж, давталт бүрийн $c[]$ массивуудын завсрын үр дүнг санана.

$i$ ба $j$-ээс эхлэх хоёр дагаврын LCP-г тооцоолъё. Бид урт нь хоёрын зэрэгтэй тэнцүү дурын хоёр дэд мөрийг $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$-ийн $2$ суурьт логарифмыг доош бүхэлчилсэнтэй тэнцүү тогтмолыг тэмдэглэнэ.

Нэмэлт санах ойгүй хоёр дэд мөрийн хамгийн урт нийтлэг угтвар¶

Бидэнд өмнөх хэсэг дэхтэй ижил бодлого байна. Бид $s$ тэмдэгт мөрийн хоёр дагаврын хамгийн урт нийтлэг угтвар (LCP)-ыг тооцоолох ёстой.

Өмнөх аргаас ялгаатай нь энэ нь ердөө $O(|s|)$ санах ой ашиглана. Урьдчилсан боловсруулалтын үр дүн нь массив байх болно (энэ нь өөрөө тэмдэгт мөрийн тухай чухал мэдээллийн эх сурвалж бөгөөд тиймээс бусад бодлого бодоход мөн ашиглагддаг). LCP асуулгад энэ массивт RMQ асуулга (интервал дахь минимумын асуулга) гүйцэтгэх замаар хариулж болох тул өөр өөр хэрэгжүүлэлтийн хувьд логарифм, бүр тогтмол асуулгын хугацаанд хүрэх боломжтой.

Энэ алгоритмын үндэс нь дараах санаа юм: бид эрэмбэлэгдсэн дараалал дахь зэргэлдээ дагаврын хос бүрийн хамгийн урт нийтлэг угтварыг тооцоолно. Өөрөөр хэлбэл бид $\text{lcp}[0 \dots n-2]$ массивыг байгуулна, энд $\text{lcp}[i]$ нь $p[i]$ ба $p[i+1]$-ээс эхлэх дагавруудын хамгийн урт нийтлэг угтварын урттай тэнцүү. Энэ массив бидэнд тэмдэгт мөрийн дурын хоёр зэргэлдээ дагаврын хариуг өгнө. Тэгвэл заавал хөрш биш дурын хоёр дагаврын хариуг энэ массиваас авч болно. Үнэндээ хүсэлт нь $p[i]$ ба $p[j]$ дагавруудын LCP-г тооцоолох байг. Тэгвэл энэ асуулгын хариу нь $\min(lcp[i],~ lcp[i+1],~ \dots,~ lcp[j-1])$ байх болно.

Тиймээс хэрэв бидэнд ийм $\text{lcp}$ массив байвал бодлого нь өөр өөр complexity-тэй маш олон янзын шийдэлтэй RMQ болж хураагдана.

Тэгэхээр гол бодлого бол энэ $\text{lcp}$ массивыг байгуулах явдал юм. Бид энэ массивыг $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$-ээс бусад тохиолдолд, тэнд бид түүнийг шууд $0$ болгож дахин тохируулна), хоёр тэмдэгт мөрийн хоорондох LCP хамгийн ихдээ $n-1$ байдаг тул бид $k$-г мөн ердөө $O(n)$ удаа нэмэгдүүлнэ гэдгийг харахад амархан. Тиймээс алгоритм $O(n)$ хугацаанд ажиллана.

Ялгаатай дэд мөрийн тоо¶

Бид дагаврын массив ба LCP массивыг тооцоолох замаар $s$ тэмдэгт мөрийг урьдчилан боловсруулна. Энэ мэдээллийг ашиглан бид тэмдэгт мөр дэх ялгаатай дэд мөрийн тоог тооцоолж чадна.

Үүний тулд бид $p[0]$ байрлалд, дараа нь $p[1]$-д гэх мэтчилэн аль шинэ дэд мөрүүд эхэлж байгаа тухай бодно. Үнэндээ бид дагавруудыг эрэмбэлэгдсэн дарааллаар аваад аль угтварууд шинэ дэд мөр өгч байгааг харна. Ингэснээр бид санамсаргүйгээр аль нэгийг нь орхигдуулахгүй.

Дагаврууд эрэмбэлэгдсэн тул одоогийн дагавар $p[i]$ нь дагавар $p[i-1]$-тэй давхцах угтваруудаас бусад бүх угтварынхаа хувьд шинэ дэд мөр өгөх нь ойлгомжтой. Тиймээс эхний $\text{lcp}[i-1]$-ээс бусад бүх угтвар. Одоогийн дагаврын урт нь $n - p[i]$ тул $p[i]$-д $n - p[i] - \text{lcp}[i-1]$ шинэ угтвар эхэлнэ. Бүх дагаврын хувьд нийлбэрлэвэл бид эцсийн хариуг авна:

$$\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]$$