Larik Akhiran

1. Introduction

Struktur data ini berkaitan erat dengan struktur data Pohon Akhiran (Suffix Tree). Kedua struktur data biasanya dipelajari bersamaan.

2. Visualisasi Larik Akhiran

The visualization of Suffix Array is simply a table where each row represents a suffix and each column represents the attributes of the suffixes.

The four (basic) attributes of each row i are:

1. index i, ranging from 0 to n-1,
2. SA[i] is the i-th lexicographically smallest suffix of T is the SA[i]-th suffix
   The SA values (permutation of [0..n-1]) is the one that we need to compute fast,
3. LCP[i] is the Longest Common Prefix between the i-th and the (i-1)-th lexicographically smallest suffixes of T is LCP[i]
   The LCP values also need to be computed fast and we will see the application of this attribute soon, and
4. Suffix T[SA[i]:] is the i-th lexicographically smallest suffix of T is from index SA[i] to the end (index n-1)
   We do not actually compute these suffixes (it is very slow to do so) and these sorted suffixes are only in this visualization to aid quick understanding of the Suffix Array (and LCP) algorithms.

Some operations may add more attributes to each row and are explained when that operations are discussed.

3. Operasi tersedia

Seluruh operasi pada larik akhiran yang tersedia adalah:

1. Buat Larik Akhiran (SA) adalah algoritma konstruksi larik akhiran O(n log n) berdasarkan ide dari Karp, Miller, & Rosenberg (1972) yang mengurutkan awalan dari akhiran berdasarkan panjang yang bertambah besar (1, 2, 4, 8, ...).
2. Cari memanfaatkan fakta bahwa akhiran dalam Larik Akhiran (SA) sudah terurutkan dan memanggil dua pencarian biner dalam waktu O(m log n) untuk menemukan kemunculan pertama dan terakhir dari string dengan pola P dan panjang m.
3. Awalan Persekutuan Terpanjang (LCP / Longest Common Prefix) antara dua akhiran berurutan (selain akhiran pertama) dapat dihitung dalam waktu O(n) menggunakan teorema Permuted LCP (PLCP).
4. Substring Berulang Terpanjang (LRS / Longest Repeated Substring) adalah algoritma sederhana untuk menemukan akhiran dengan nilai LCP terbesar dalam waktu O(n).
5. Substring Persekutuan Terpanjang (LCS / Longest Common Substring) adalah algoritma sederhana untuk menemukan akhiran dengan nilai LCP terbesar yang berasal dari dua string berbeda dalam waktu O(n).

3-1. Pembangunan Larik Akhiran - UI

Dalam visualisasi ini, kami menunjukkan konstruksi Larik Akhiran yang tepat O(n log n) berdasarkan ide Karp, Miller, & Rosenberg (1972) yang men-sort awalan dari akhiran dalam urutan panjang yang meningkat (1, 2, 4, 8, ...), yang dikenal sebagai algoritma Prefix Doubling.

Kami membatasi input hanya menerima 12 karakter huruf BESAR (tidak boleh terlalu panjang karena ruang gambar yang tersedia — tetapi dalam aplikasi nyata Pohon Akhiran, n bisa mencapai ratusan ribu hingga jutaan karakter) dan simbol terminasi khusus '$' (yaitu, [A-Z$]). Jika Anda tidak menulis simbol terminasi '$' di belakang string input Anda, kami akan melakukannya secara otomatis. Jika Anda menempatkan '$' di tengah string input, simbol tersebut akan diabaikan. Dan jika Anda memasukkan string input kosong, kami akan menggunakan default "GATAGACA$".

Untuk kenyamanan, kami menyediakan beberapa string input kasus uji klasik yang biasanya ditemukan dalam kuliah Pohon/Larik Akhiran, tetapi untuk menunjukkan kekuatan alat visualisasi ini, Anda dianjurkan untuk memasukkan string 12 karakter pilihan Anda (diakhiri dengan karakter '$').

Perlu dicatat bahwa kolom Larik LCP tetap kosong dalam operasi ini. Mereka harus dihitung secara terpisah melalui operasi Awalan Persekutuan Terpanjang.

3-2. Algoritma Prefix Doubling

This Prefix Doubling Algorithm runs in O(log n) iterations, where for each iteration, it compares substring T[SA[i]:SA[i+k]] with T[SA[i+k]:SA[i+2*k]], i.e., in layman's terms: first compare two pairs of characters, then compare first two characters with the next two, then compare the first four characters with the next four, and so on.

This algorithm is best explored via visualization, see ConstructSA("GATAGACA$") in action (it is advisable that you exit this e-Lecture mode, run the algorithm in exploration mode, pause the algorithm and replay it frame-by-frame as there are too many elements changing especially during the first sorting iteration).

Time complexity: There are O(log n) prefix doubling iterations, and each iteration we call O(n) Radix Sort, thus it runs in O(n log n) — good enough to handle up to n ≤ 200K characters in typical programming competition problems involving long strings.

3-3. Pencarian

After we construct the Suffix Array of T in O(n log n), we can search for the occurrence of Pattern string T in O(m log n) by binary searching the sorted suffixes to find the lower bound (the first occurrence of P as a prefix of any suffix of T) and the upper bound positions (thelast occurrence of P as a prefix of any suffix of T).

Time complexity: O(m log n) and it will return an interval of size k where k is the total number of occurrences.

For example, on the Suffix Array of T = "GATAGACA$" above, try these scenarios:

1. P returns a range of rows: Search("GA"), occurrences = {4, 0}
2. P returns one row only: Search("CA"), occurrences = {2}
3. P is not found in T: Search("WONKA"), occurrences = {NIL}

PS: There is a slightly faster O(m+log n) variant that has not been visualized yet.

3-4. Longest Common Prefix (LCP) - Part 1

We can compute the Longest Common Prefix (LCP) of two adjacent suffixes (in Suffix Array order) in O(n) time using three phases of Kasai's algorithm. This algorithm takes advantage that if we have a long LCP between two adjacent suffixes (in Suffix Array order), that long LCP has lots of overlap with another suffix in positional order when its first character is removed.

The first phase: Compute the value of Phi[], where Phi[SA[i]] = SA[i-1] in O(n). This is to help the algorithm knows in O(1) time of which Suffix is behind Suffix-SA[i] in Suffix Array order. Try LCP("GATAGACA$") and focus on the first part on filling column Phi[] (it is advisable that you exit this e-Lecture mode, run the algorithm in exploration mode, pause the algorithm and replay it frame-by-frame as there are too many elements changing).

3-5. Longest Common Prefix (LCP) - Part 2

The second phase: Compute the PLCP[] values between a Suffix-i in positional order with Suffix-Phi[i] (the one behind Suffix-i in Suffix Array order). When we advance to the next index i+1 in positional order, we will remove the front most character of the suffix, but possibly retain lots of LCP value between Suffix-(i+1) and Suffix-Phi[(i+1)].

PLCP Theorem (not proven) shows that the LCP values can only be incremented up to n times, and thus can only be decremented at most n times too, making the overall complexity of the second phase to be also O(n).

Now, retry LCP("GATAGACA$") again and focus on the middle part on filling column PLCP[] (again, it is advisable that you exit this e-Lecture mode, run the algorithm in exploration mode, pause the algorithm and replay it frame-by-frame as there are too many elements changing).

3-6. Longest Common Prefix (LCP) - Part 3

The third phase: We compute the value of LCP[], where LCP[i] = PLCP[SA[i]] in O(n). This LCP values are the one that we use for other Suffix Array applications later.

Finally, retry LCP("GATAGACA$") again and focus on the last part on filling column LCP[] (as usual, exit this e-Lecture mode, run the algorithm in exploration mode, pause the algorithm and replay it frame-by-frame as there are too many elements changing).

Time complexity: Kasai's algorithm utilizes the PLCP theorem where the total number of increase (and decrease) operations of the value of the LCP is at most O(n). Thus Kasai's algorithm runs in O(n) overall. Thus, the combination of O(n log n) Suffix Array construction (via the Prefix Doubling algorithm) and the O(n) computation of LCP Array using this Kasai's algorithm is good enough to handle up to n ≤ 200K characters in typical programming competition problems involving long strings.

3-7. Substring Terulang Terpanjang (LRS)

3-8. Substring Persekutuan Terpanjang (LCS)

Setelah ita membangun larik akhiran untuk dari penggabungan kedua string T1$T2# dengan panjang n = n1+n2 dalam O(n log n) dan menghitung larik LCPnya dalam O(n), kita bisa mencari Substring Terulang Terpanjang (LRS) dalam T dengan cara mengiterasi semua nilai LCP dan keluarkan nilai terbesar yang muncul dari dua string berbeda.

Cobalah LCS("GATAGACA$", "CATA#") pada larik akhiran dari string T1 = "GATAGACA$" dan T2 = "CATA#". Kita punya LCS = "ATA".

4. Implementasi

Anda dapat menggunakan/memodifikasi kode implementasi kita untuk algoritma cepat Larik Akhiran + LCP: sa_lcp.cpp | py | java | ml untuk menyelesaikan soal kontes pemrograman yang memerlukannya.