Rosihan Ari's Blog

Algoritma Mengambil Substring

January 7th, 2009 | by rosihanari |  Cetak Artikel

Pernahkah Anda mendengar istilah substring? Ya… substring adalah suatu string yang merupakan bagian dari suatu string. Sebagai contoh, misalkan ada suatu string ‘KOMPUTER’, maka ‘PUTER’ adalah merupakan substringnya. Selain itu ‘KOM’, ‘TER’, ‘OMPUT’, ‘PUT’ dan bahkan ‘K’ atau ‘R’ itu juga merupakan substring dari ‘KOMPUTER’. Masih banyak lagi substring dari ‘KOMPUTER’ ini.

Saat ini di beberapa bahasa pemrograman seperti PHP dan juga tool seperti MySQL, MS. Excel dll telah dilengkapi dengan suatu function untuk mengambil substring ini dengan mudah. Kita ambil contoh dalam PHP terdapat function substr(), dalam MySQL terdapat substring() dan dalam MS. Excel juga terdapat mid().

Nah… di sini saya tidak akan membahas kembali cara penggunaan function-function instan untuk mencari subtring. Banyak artikel di blog.rosihanari.net ini yang telah membahas penggunaan function tersebut. Silakan Anda cari sendiri ya Akan tetapi sekarang akan saya bahas bagaimana sebenarnya algoritma mengambil subtring ini dan bagaimana implementasinya dalam program.

Diantara beberapa macam function instan yang telah saya sebutkan di atas, kesemuanya memiliki karakteristik yang sama yaitu memiliki 3 buah parameter, yaitu string aslinya, angka yang menunjukkan posisi karakter awal dari substring yang akan diambil, serta jumlah karakter substring yang akan diambil. Sebagai contoh misalkan dalam PHP, misalkan kita akan mengambil substring ‘OMPUTE’ dalam string ‘KOMPUTER’, maka perintahnya substr("KOMPUTER", 1, 6); Angka 1 menunjukkan posisi karakter O dalam string yaitu ke-1 (ingat dalam PHP penghitungan posisi karakter dalam string dimulai dari 0). Sedangkan 6 menunjukkan jumlah karakter subtring yang akan diambil. Contoh lain misalkan dalam MS. Excel, kita gunakan perintah MID("KOMPUTER", 2, 6), dalam hal ini 2 menunjukkan posisi karakter awal substringnya (perhitungan posisi karakter dalam string pada Excel dimulai dari 1).

OK… untuk studi kasus, misalkan kita punya string ‘KOMPUTER‘. Selanjutnya kita ingin mengambil substring ‘MPUTE‘. Apa yang harus kita lakukan? Untuk bisa mengambil subtring ini, tentu kita butuh beberapa parameter untuk melakukannya. Apa saja parameternya? Ya… kita harus tahu terlebih dahulu string aslinya dalam hal ini ‘KOMPUTER’. Kita juga harus mengetahui posisi karakter awal substring pada string aslinya (dalam hal ini posisi karakter ‘M’), dan juga panjang karakter subtringnya. Parameter ini kita adopsi dari function-function instan yang telah saya sebutkan di atas. Akan tetapi sebenarnya parameter-parameter ini tidak harus demikian. Bisa saja Anda menggunakan parameter posisi karakter yang merupakan akhir dari subtring misalnya, sebagai pengganti parameter jumlah karakter subtring yang akan diambil.

Nah selanjutnya, dari kasus yang kita ambil di atas, kita dapatkan string aslinya ‘KOMPUTER’, posisi awal karakter substring yaitu ‘M’ adalah ke-3 dari string asli dan panjang karakter substringnya adalah 5. Trus… langkah berikutnya bagaimana? Secara konsep, sebenarnya kita hanya mengambil karakter demi karakter dari string aslinya, mulai dari posisi karakter yang telah ditentukan. Setelah karakter dibaca, lalu digabungkan dengan gabungan karakter yang telah dibaca sebelumnya. Gambarannya adalah sbb: langkah pertama kita ambil karakter ke-3 dari string asli, yaitu ‘M’, lalu ambil karakter ke-4 yaitu ‘P’, nah ‘P’ ini digabung dengan ‘M’ yang sebelumnya dibaca, menjadi ‘MP’. Lalu baca lagi karakter ke-5 yaitu ‘U’ dan digabungkan dengan ‘MP’, menjadi ‘MPU’. Begitu seterusnya. Proses ini diulang-ulang terus sampai dengan 5 kali. Mengapa 5 kali? Ya… karena panjang karakter substring yang kita inginkan adalah 5. Sehingga diperolehlah substring ‘MPUTE’.

Nah… yang menjadi pertanyaan, Bagaimana cara kita menggabungkan karakter-karakter tersebut? Ho..ho jangan khawatir, dalam Pascal, C atau C++ terdapat operator untuk menggabung karakter atau string, yaitu menggunakan operator + (bukan penjumlahan lho ya). Jadi misalkan ‘A’ + ‘B’ hasilnya adalah ‘AB’, sedangkan ‘B’ + ‘A’ hasilnya ‘BA’.

Sehingga dari penjelasan konsep di atas, kita dapat implementasikan ke dalam program. Dalam contoh ini, saya gunakan bahasa Pascal.

function substring(x : string; a : integer; n : integer) : string;
var i : integer; hasil : string;
begin
   hasil := '';
   for i:=a to a+n-1 do
   begin
        hasil := hasil + x[i];
   end;
   substring := hasil;
end;

Dalam hal ini parameter x adalah string asli, a adalah posisi awal karakter substring dalam string, dan n adalah jumlah karakter substring. Lho… mengapa perulangan FOR nya dimulai dari i=a sampai dengan i=a+n-1? Ya… karena i ini nanti akan digunakan untuk menentukan posisi karakter dalam string asli yang akan diambil. Misalkan a=3 dan n=5, maka i akan bergerak mulai dari i=3 s/d i=3+5-1=7 atau i=3, 4, 5, 6, 7. Sehingga karakter dari string asli yang akan diambil adalah karakter ke-3, 4, 5, 6, dan 7.

Oya…. sebelum karakter-karakter dalam string asli itu dibaca dan digabungkan, terlebih dahulu ada inisialisasi untuk variabel hasil yaitu NULL karakter atau karakter kosong. Variabel hasil ini digunakan untuk menyimpan gabungan antar karakter-karakter yang dibaca.

Pembahasan code di atas hanyalah dalam bentuk function saja. Adapun program Pascal secara lengkap untuk mencari substring ‘MPUTE’ dalam string ‘KOMPUTER’ adalah sbb:

Program CariSubstring;

function substring(x : string; a : integer; n : integer) : string;
var i : integer; hasil : string;
begin
   hasil := '';
   for i:=a to a+n-1 do
   begin
        hasil := hasil + x[i];
   end;
   substring := hasil;
end;

begin
   write(substring('KOMPUTER', 3, 5));
end.

Program di atas akan menghasilkan output ‘MPUTE’.

OK… semoga artikel ini ada manfaatnya buat Anda.