Implementasi Struktur Data Rope pada Permasalahan SPOJ Alphabetic Rope

Abstract

Permasalahan alphabetic rope merupakan sebuah permasalahan yang melibatkan sebuah rentang pencarian/query. Tipe query secara umum dibagi menjadi dua yaitu, operasi pencarian dan perubahan. Operasi perubahan pada suatu rentang akan menyebabkan perubahan hasil pencarian selanjutnya. Untuk menangani berbagai permasalahan pada operasi alphabetic rope yang harus dilakukan, dibutuhkan struktur data yang mampu mendukung operasi-operasi tersebut dengan efisien. Pada penelitian ini dirancang penyelesaian permasalahan alphabetic rope antara lain operasi pencarian karakter pada indeks ke-y pada konfigurasi rope saat ini, operasi memotong segmen rope pada indeks ke-x sampai y dan menggabungkan pada bagian depan rope, dan operasi memotong segmen rope pada indeks ke-x sampai y dan menggabungkan pada bagian belakang rope. Struktur data klasik yang biasa digunakan dalam penyelesaian permasalahan ini adalah stuktur data String. Namun penggunaan algoritma String masih kurang efisien dalam hal kecepatan dan kebutuhan memori. Pada penelitian ini digunakan struktur data Rope untuk menyelesaikan tipe-tipe operasi yang diberikan. Algoritma yang dirancang dapat menyelesaikan permasalahan yang diberikan dengan benar dan memiliki pertumbuhan waktu secara logaritmik dengan kompleksitas waktu sebesar O(log N ) per query.