Larik Akhiran

1. Introduction

Larik Akhiran (Suffix Array) adalah sebuah array terurut dari semua akhiran (sufiks) sebuah string T dengan panjang n (n dapat mencapai ratusan ribu karakter).
Struktur data ini sederhana namun bermanfaat besar yang digunakan, diantara struktur data lainnya, dalam mengindeks teks secara keseluruhan, algoritma kompresi data, dan dalam bidang bioinformatika.

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

2. Visualisasi Larik Akhiran

Visualisasi dari Larik Akhiran hanyalah sebuah tabel di mana tiap baris merepresentasikan sebuah akhiran dan setiap kolom merepresentasikan atribut dari akhiran-akhiran tersebut.

Empat atribut (dasar) untuk setiap baris i adalah:
  1. indeks i, merentang dari 0 ke n-1,
  2. SA[i]: akhiran leksikografis terkecil ke-i dari T merupakan akhiran ke-SA[i].
  3. LCP[i]: Awalan Persekutuan Terpanjang (Longest Common Prefix) antara akhiran terkecil ke-i dan akhiran terkecil ke-(i-1) secara leksikografis dari T adalah LCP[i] (kita akan melihat aplikasi dari atribut ini nanti), dan
  4. Akhiran T[SA[i]:] - akhiran terkecil ke-i secara leksikografis dari T dimulai dari indeks SA[i] hingga akhir (indeks n-1).
Beberapa operasi mungkin menambahkan lebih banyak atribut ke setiap baris dan dijelaskan saat operasi tersebut dibahas.

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

Algoritma Prefix Doubling ini berjalan dalam O(log n) iterasi, di mana untuk setiap iterasi, ia membandingkan substring T[SA[i]:SA[i+k]] dengan T[SA[i+k]:SA[i+2k]], yaitu pertama membandingkan dua pasang karakter, kemudian membandingkan dua karakter pertama dengan dua berikutnya, kemudian membandingkan empat karakter pertama dengan empat berikutnya, dan seterusnya.


Algoritma ini paling baik dieksplorasi melalui visualisasi, lihat ConstructSA("GATAGACA$") dalam aksi.


Kompleksitas waktu: Terdapat O(log n) iterasi Prefix Doubling, dan setiap iterasi kita memanggil Radix Sort O(n), sehingga berjalan dalam O(n log n) — cukup baik untuk menangani hingga n ≤ 200K karakter dalam masalah kompetisi pemrograman yang melibatkan string panjang

3-3. Pencarian

Setelah kita membangun Larik Akhiran dari T dalam O(n log n), kita dapat mencari kemunculan string Pola P dalam O(m log n) dengan melakukan pencarian biner pada sufiks-sufiks yang diurutkan untuk menemukan posisi batas bawah (kemunculan pertama P sebagai awalan dari sufiks mana pun dari T) dan posisi batas atas (kemunculan terakhir P sebagai awalan dari sufiks mana pun dari T).

Kompleksitas waktu: O(m log n) dan akan mengembalikan interval dengan ukuran k di mana k adalah jumlah total kemunculan.

Sebagai contoh, pada Array Sufiks dari T = "GATAGACA$" di atas, coba skenario berikut:

P mengembalikan rentang baris: Search("GA"), kemunculan = {4, 0}
P mengembalikan satu baris saja: Search("CA"), kemunculan = {2}
P tidak ditemukan dalam T: Search("WONKA"), kemunculan = {NIL}

3-4. Awalan Persekutuan Terpanjang (LCP)

Kita dapat menghitung Awalan Umum Terpanjang (LCP) dari dua akhiran yang berdekatan (dalam urutan Larik Akhiran) dalam waktu O(n) menggunakan tiga fase algoritma Kasai. Algoritma ini memanfaatkan bahwa jika kita memiliki LCP yang panjang antara dua akhiran yang berdekatan (dalam urutan Larik Akhiran), LCP panjang tersebut memiliki banyak tumpang tindih dengan akhiran lain dalam urutan posisi ketika karakter pertama dihapus.


Fase pertama: Menghitung nilai Phi[], di mana Phi[SA[i]] = SA[i-1] dalam waktu O(n). Ini untuk membantu algoritma mengetahui dalam waktu O(1) akhiran mana yang berada di belakang Akhiran-SA[i] dalam urutan Larik Akhiran.

Fase kedua: Menghitung nilai PLCP[] antara Akhiran-i dalam urutan posisi dengan Akhiran-Phi[i] (yang berada di belakang Akhiran-i dalam urutan Larik Akhiran). Ketika kita maju ke indeks berikutnya i+1 dalam urutan posisi, kita akan menghapus karakter terdepan dari akhiran, tetapi mungkin mempertahankan banyak nilai LCP antara Akhiran-(i+1) dan Akhiran-Phi[(i+1)]. Teorema PLCP (tidak terbukti) menunjukkan bahwa nilai LCP hanya bisa ditingkatkan hingga n kali, dan dengan demikian hanya bisa dikurangi paling banyak n kali juga, sehingga kompleksitas keseluruhan fase kedua juga O(n).


Fase ketiga: Kami menghitung nilai LCP[], di mana LCP[i] = PLCP[SA[i]] dalam O(n). Nilai LCP ini adalah yang kami gunakan untuk aplikasi Larik Akhiran lainnya nanti.


Kompleksitas waktu: Algoritma Kasai memanfaatkan teorema PLCP di mana jumlah total operasi peningkatan (dan penurunan) nilai LCP paling banyak adalah O(n). Dengan demikian, algoritma Kasai berjalan dalam O(n) secara keseluruhan. Jadi, kombinasi dari konstruksi Larik Akhiran O(n log n) (melalui algoritma Prefix Doubling) dan perhitungan O(n) dari Larik LCP menggunakan algoritma Kasai ini cukup baik untuk menangani hingga n ≤ 200K karakter dalam masalah kompetisi pemrograman yang melibatkan string panjang.

3-5. Substring Terulang Terpanjang (LRS)

Setelah kita membangun Suffix Array dari T dalam O(n log n) dan menghitung larik LCP dalam O(n), kita dapat menemukan Longest Repeated Substring (LRS) dalam T dengan cukup mengiterasi semua nilai LCP dan melaporkan yang terbesar.

Ini karena setiap nilai LCP[i] pada LCP Array berarti prefix terpanjang yang sama antara dua suffix yang berdekatan secara leksikografis: Suffix-i dan Suffix-(i-1). Ini berkaitan dengan simpul internal dari Suffix Tree yang setara dari T yang bercabang ke setidaknya dua (atau lebih) suffix, sehingga prefix yang sama dari suffix yang berdekatan ini berulang.

3-6. 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.