Saturday, 1 February 2014

SPOJ PERIOD - Period

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:
  1. Hashing
  2. KMP
  3. 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. 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 ketidakcocokkan (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 redundan 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.
syntax highlighting tutorial

8 comments :

  1. Maaf mas boleh tanya ga?
    Failure 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

    ReplyDelete
    Replies
    1. 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").

      Nah 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.

      Delete
  2. terima kasih banyak mas atas penjelasannya.
    oh 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.

    ReplyDelete
    Replies
    1. 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.

      Delete
  3. ahh bgtu yah..
    awalnya 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?

    ReplyDelete
    Replies
    1. Oh bukannya ngga bisa. Tapi saya rasa butuh pengembangan. Saya juga tidak terlalu ahli di bidang itu, coba tanya dosen yang bersangkutan aja haha

      Delete