Kebiasaan saya kalau sedang mau mengerjakan soal-soal di SPOJ adalah menatapi halaman status. Jika melihat ada orang melakukan pengumpulan untuk soal yang kodenya menarik, akan saya coba lihat soalnya. Kali ini saya mendapati soal sederhana yang menyenangkan untuk didiskusikan, yaitu tentang string. Sepengalaman saya bertanding, soal string jarang keluar di perlombaan (kecuali ICPC Jakarta).
Inti soalnya sederhana, Anda dapat langsung mengaksesnya di sini. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.
Solusi paling naif adalah dengan mencoba semua kemungkinan prefix, lalu untuk masing-masing prefix dicari periodenya. Seperti biasa, cara ini akan TLE. Untuk mencoba semua kemungkinan prefix saja sudah ada N kemungkinan. Oleh karena itu, untuk mempercepat pendekatan ini setidaknya untuk menghitung periode harus dilakukan dalam O(1).
Dalam mengerjakan soal string, biasanya pendekatan yang saya pikirkan adalah:
Ketika hendak menggunakan hashing, kelihatannya agak sulit karena yang ingin kita lakukan tidak terlihat seperti string matching. Oleh sebab itu saya beralih ke KMP (Knuth Morris Pratt). Nyatanya, pendekatan KMP dapat digunakan (terutama failure-function-nya yang sangat sakti).
Mari kita lihat sebenarnya apa itu failure function. Misalkan terdapat string S, lalu i menyatakan suatu posisi karakter pada string S, dan f[i] menyatakan failure function dari i. Nilai dari f[i] sebenarnya adalah satu posisi sesudah border dari string S[0..i-1]. Border merupakan proper prefix dan proper suffix yang sama dan terpanjang dari suatu string. Perhatikan gambar berikut untuk lebih jelasnya:
Manfaat dari failure function bisa dirasakan pada saat dilakukan string matching. Bila pada karakter ke-i terjadi ketidakcocokan (mismatch), maka langsung lanjut untuk mencocokkan karakter ke-f[i]. Misalkan terdapat sebuah string S = "abcxabcd" dan T = "abcxabcebcade", dan ketidakcocokkan terjadi pada karakter terakhir S:
Dengan begitu, kita membuang banyak proses-proses membandingkan ulang beberapa karakter pertama yang tidak perlu. Dengan bantuan failure function, kompleksitas string matching pada KMP adalah O(N+M), dengan N dan M adalah panjang kedua string tersebut. Mengapa demikian? Karena kita seperti menggerakkan string yang ingin dicocokkan pada string yang besar ke kanan, tanpa perlu mencocokkan kembali karakter yang sudah pernah dicocokkan sebelumnya.
Baik, mari kembali ke persoalan sebelumnya. Bagaimana cara menentukan periode dari sebuah string? Yang sederhana untuk diamati adalah string dengan periode 2. Pada kasus tersebut, failure function-nya seperti ini:
Ternyata, border mereka harus berhimpit. Dengan kata lain, banyaknya karakter dari 0 sampai i-1 harus habis dibagi oleh banyaknya karakter dari f[i] sampai i-1, dan hasil baginya harus sama dengan 2.
Untuk periode 3 dan 4:
Ternyata border mereka saling tumpang tindih! Lebih jauh lagi, tumpang tindih border ini memastikan bahwa terdapat properti khusus. Perhatikan gambar berikut:
Karena properti dari border, maka karakter ke-0 pasti sama dengan karakter ke-3. Secara bersamaan, hal ini juga mengakibatkan karakter ke-3 dengan karakter ke-6 sama. Hal ini terjadi terus secara berantai, sehingga bisa dikatakan bahwa strukturnya membentuk string dengan periode 3.
Berdasarkan analisis tersebut, sebuah substring dari karakter 0 sampai i-1 bisa memiliki periode jika border mereka berhimpit/tumpang tindih, dan banyaknya karakter dari 0 sampai i-1 habis dibagi dengan banyaknya karakter dari f[i] sampai i-1. Dari mana nilai periode sebuah string bisa didapatkan? Jawabannya sederhana, yaitu banyaknya karakter dari 0 sampai i-1 dibagi dengan banyaknya karakter dari f[i] sampai i-1 (hasilnya harus bilangan bulat).
Bila Anda sudah pernah mengimplementasikan KMP, sisanya sederhana. Berikut ini implementasi saya dengan menambahkan karakter dummy berupa '.'. Anda juga bisa mencoba soal serupa di UVa 12012 - Detection of Extraterrestrial.
Inti soalnya sederhana, Anda dapat langsung mengaksesnya di sini. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.
Solusi paling naif adalah dengan mencoba semua kemungkinan prefix, lalu untuk masing-masing prefix dicari periodenya. Seperti biasa, cara ini akan TLE. Untuk mencoba semua kemungkinan prefix saja sudah ada N kemungkinan. Oleh karena itu, untuk mempercepat pendekatan ini setidaknya untuk menghitung periode harus dilakukan dalam O(1).
Dalam mengerjakan soal string, biasanya pendekatan yang saya pikirkan adalah:
- Hashing
- KMP
- Suffix array
Ketika hendak menggunakan hashing, kelihatannya agak sulit karena yang ingin kita lakukan tidak terlihat seperti string matching. Oleh sebab itu saya beralih ke KMP (Knuth Morris Pratt). Nyatanya, pendekatan KMP dapat digunakan (terutama failure-function-nya yang sangat sakti).
Mari kita lihat sebenarnya apa itu failure function. Misalkan terdapat string S, lalu i menyatakan suatu posisi karakter pada string S, dan f[i] menyatakan failure function dari i. Nilai dari f[i] sebenarnya adalah satu posisi sesudah border dari string S[0..i-1]. Border merupakan proper prefix dan proper suffix yang sama dan terpanjang dari suatu string. Perhatikan gambar berikut untuk lebih jelasnya:
Manfaat dari failure function bisa dirasakan pada saat dilakukan string matching. Bila pada karakter ke-i terjadi ketidakcocokan (mismatch), maka langsung lanjut untuk mencocokkan karakter ke-f[i]. Misalkan terdapat sebuah string S = "abcxabcd" dan T = "abcxabcebcade", dan ketidakcocokkan terjadi pada karakter terakhir S:
Dengan begitu, kita membuang banyak proses-proses membandingkan ulang beberapa karakter pertama yang tidak perlu. Dengan bantuan failure function, kompleksitas string matching pada KMP adalah O(N+M), dengan N dan M adalah panjang kedua string tersebut. Mengapa demikian? Karena kita seperti menggerakkan string yang ingin dicocokkan pada string yang besar ke kanan, tanpa perlu mencocokkan kembali karakter yang sudah pernah dicocokkan sebelumnya.
Baik, mari kembali ke persoalan sebelumnya. Bagaimana cara menentukan periode dari sebuah string? Yang sederhana untuk diamati adalah string dengan periode 2. Pada kasus tersebut, failure function-nya seperti ini:
Ternyata, border mereka harus berhimpit. Dengan kata lain, banyaknya karakter dari 0 sampai i-1 harus habis dibagi oleh banyaknya karakter dari f[i] sampai i-1, dan hasil baginya harus sama dengan 2.
Untuk periode 3 dan 4:
Ternyata border mereka saling tumpang tindih! Lebih jauh lagi, tumpang tindih border ini memastikan bahwa terdapat properti khusus. Perhatikan gambar berikut:
Berdasarkan analisis tersebut, sebuah substring dari karakter 0 sampai i-1 bisa memiliki periode jika border mereka berhimpit/tumpang tindih, dan banyaknya karakter dari 0 sampai i-1 habis dibagi dengan banyaknya karakter dari f[i] sampai i-1. Dari mana nilai periode sebuah string bisa didapatkan? Jawabannya sederhana, yaitu banyaknya karakter dari 0 sampai i-1 dibagi dengan banyaknya karakter dari f[i] sampai i-1 (hasilnya harus bilangan bulat).
Bila Anda sudah pernah mengimplementasikan KMP, sisanya sederhana. Berikut ini implementasi saya dengan menambahkan karakter dummy berupa '.'. Anda juga bisa mencoba soal serupa di UVa 12012 - Detection of Extraterrestrial.
izin share ya mas
BalasHapusya, silakan :)
HapusMaaf mas boleh tanya ga?
BalasHapusFailure function dan border function sama ndak mas?
kan di contoh2 di atas patternnya memiliki huruf2 yg berurutan/ada polanya.
nah klo misal Pattern nya spt ini : render. ini nentuin failure functionnya gimana mas?
Mohon dijawab ya mas, soale lagi bikin skripsi pke algoritma ini. Sebelumnya makasih :D
Menurut Wikipedia, border itu adalah string yang merupakan prefix dan suffix dari suatu string yang sama. Misalnya "abc", yang merupakan border dari string "abcdefabc". Dalam KMP, border tidak boleh sama dengan string itu sendiri (tidak boleh "abcdefabc").
HapusNah failure function itu ada untuk setiap posisi karakter, dan artinya adalah panjang border terbesar pada prefix sampai pada sebelum karakter tersebut apa. Mencari border terbesar untuk setiap posisi pada string bisa dilakukan dalam O(N). Detil tentang algoritmanya bisa dilihat di http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching
Untuk string "render", failure functionnya:
r -> -1
e -> 0
n -> 0
d -> 0
e -> 0
r -> 1
Kalau ditanya sama atau tidak antara failure function dengan border function, saya tidak tahu secara pasti. Barangkali hanya perbedaan penamaan, atau mungkin memang berbeda.
terima kasih banyak mas atas penjelasannya.
BalasHapusoh iya mas, algoritma KMP bisa digunakan untuk membuat fungsi/fitur auto complete, auto suggest atau auto correct gtu ndak mas? mungkin mas punya link referensi terkait ini.
Hmm kalau untuk jadi auto correct/auto suggest, rasanya perlu pengembangan dari KMP. Jadi penggunaan automatanya (failure function) diperluas, bukan cuma buat string matching 1 string aja. Sebagai referensi bisa coba pelajari algo Aho-Corasick.
Hapusahh bgtu yah..
BalasHapusawalnya saya kira bisa mas. soalnya klo algoritma string matching lainnya seperti Bruto Force dan Boyer moore itu bisa untuk fitur auto complete/auto suggest gtu. knpa KMP ndak bisa ya mas?
Oh bukannya ngga bisa. Tapi saya rasa butuh pengembangan. Saya juga tidak terlalu ahli di bidang itu, coba tanya dosen yang bersangkutan aja haha
HapusIzin share soal SPOJ GUTTSS. Tolong dibantu penyelesaiannya
BalasHapus