hmm…materi algo di kelas responsi sudah menginjakkan kakinya pada bab array dan string. bab yang menurut saya penuh dengan permainan yang mengasyikkan (walaupun kadang bikin pusing kepada 
).
sebelumnya bagi yang belum kenal string, coba kenalan dulu:
kamu -> hi string…
string -> iya…ada apa?
kamu -> string, kamu makanan macam apa sih?
string -> husstt….aku bukan makanan tahu! aku tuh kumpulan dari karakter-karakter, tahu g lo karakter tuh apa?
kamu -> tahu dunkz.. ‘a’, ‘b’ ‘c’, dan seterusnya.
string -> betul betul betul.
kamu -> terus lo bisa diapain aja?
string -> banyak dunkz, lo bisa cari substring di gw, bisa ngurutin gw, bisa ngecek palindrome, dan sebagainya.
kamu -> okey okey…terima kasih.
string -> sama-sama
okey langsung aja pada permasalahan, “substring” merupakan suatu kumpulan karakter yang ada dalam suatu string tertentu. Contohnya… string “FACEBOOK” klo kita perhatiin dalam string “FACEBOOK” ada substring “FACE”, “BOOK”, “CEB”, dan sebagainya. Pastilah sangat banyak, karena secara logika substring memiliki panjang minimal satu karakter dan maksimal panjang string induknya. Klo pake rumus kombinasi bakal dapat banyak tuh.
kemudian ada istilah BRUTEFORCE. brutoforce ini merupakan salah satu teknik algoritma yang paling gampang. tapi punya kekurangan jika datanya banyak proses bakalan lama. contohnya gini, klo kita lagi nyari-nyari bab di suatu buku, terus bukunya g ada daftar isinya (*yang nulis buku lagi dikejar deadline sampe lupa g nyantumin daftar isi ^^). terkadang klo ada kejadian kyk gini, qt bakal ngecek/buka halaman per halaman. nah..begitu juga dengan bruteforce, dia ngecek (istilah lain nge-trace) dari depan sampe belakang. dengan teknik ini kita bisa nyari substring dalam suatu string.
OK.let’s do it!
Misalkan ada string “AAAABBBAAA” terus kita pengen nyari substring “BA” ada d posisi keberapa (posisi awal adalah 0). gimana caranya y?
Menggunakan teknik bruteforce:
panjang dari substring “BA” adalah 2, jadi kita cari kombinasi 2 huruf dari string “AAAABBBAAA” secara berurutan:
1. 2 huruf pertama yaitu “AA” –> “AAAABBBAAA” , bukan
2. 2 huruf pertama yaitu “AA” –> “AAAABBBAAA” , bukan
3. 2 huruf pertama yaitu “AA” –> “AAAABBBAAA” , bukan
4. 2 huruf pertama yaitu “AB” –> “AAAABBBAAA” , bukan
5. 2 huruf pertama yaitu “BB” –> “AAAABBBAAA” , bukan
6. 2 huruf pertama yaitu “BB” –> “AAAABBBAAA” , bukan
7. 2 huruf pertama yaitu “BA” –> “AAAABBBAAA” , KETEMU berarti substring “BA” dimulai di index ke-6
Terus bisa g diimplementasikan ke bahasa pemrograman? pasti bisa lah,
pada kesempatan ini kita pake bahasa C, langsung cek:
#include
#include
#include
void main() {
char *s1 = “AAAABBBAAA”;
char *s2 = “BAA”;
int i, j, k;
int temp = 0;
int idx = i;
printf(“%s\n”,s1);
printf(“%s\n”,s2);
for(i=0;i
for(j=i,k=0;k
if(s1[j] == s2[k]) {
idx = i;
}else {
break;
}
}
}
printf(“index = %d”,idx);
getch();
}
hampir lupa, penggunaan algoritma untuk pencarian substring digunakan diantaranya di:
* parser (nanti belajar di kuliah teori bahasa dan automata dan kuliah teknik kompilasi)
* word processor (ms. word, open office, dll)
* web search engine
* natural language processing
* dsb….
Referensi: www.acmsolver.org
OKEY. thanks udah dibaca. semoga bermanfaat. dan d tunggu saran dan kritiknya
(Muhammad Zidny Naf”an)
#1 by fardian on 16 Mei 2011 - 2:27 pm
klau pakai bahasa pemprograman php bagaimana ya ? bisa kasih contoh nya. help me…
#2 by derlaz on 17 Mei 2011 - 3:35 am
klo pake php sebenarnya sama aja bro, kan algoritmanya ngecek satu2 dari awal string sampe akhir string. kira2 spt ini:
$s1 = “AAAABBBAAA”;
$s2 = “BAA”;
for($i=0;$i<(strlen($s1)-strlen($s2))+1;$i++) {
for($j=i,$k=0;$k<strlen(s$2);$j++,$k++) {
if($s1[$j] == $s2[$k]) {
$idx = $i;
}else {
break;
}
}
}
codingan diatas belum gw coba bro, lagi ngenet di warbet, jadi g bisa nyoba. semoga bisa membantu,
#3 by fardian on 23 Mei 2011 - 2:31 am
Saya sudah coba, tpi sepertinya masih belum sesuai mas.
saya juga sudah mencoba membuat tpi masih belum berhasil mklum masih newbie..mohon bantuan nya mas
kira2 saya bikin na seperti ini.
<?php
function bfs($car,$tex){
$cari = pecah($car);
$lebarCari = count($cari);
$text = pecah($tex);
$lebarText = count($text);
$w=$lebarText-$lebarCari;
for ($i=0;;$lebarText)
{
$j = 0;
$t=$i+$j;
while($j=$cari){
$ketemu[$i]=$j-$lebarCari;
}
return $ketemu;
}
}
function pecah($input){
for($h=0; $h
#4 by derlaz on 23 Mei 2011 - 4:08 pm
fungsi pecah yang dimaksud seperti apa?
#5 by fardian on 23 Mei 2011 - 2:50 am
oh ya mas, mf tanya lagi. yang saya cari adalah jumlah cocok tidak nya berapa, klo scrip nya mas sudah benar tpi itu menghitung posisi string yang cocok nya, bagaimana ya mas ? mohon bantuan nya.
#6 by fardian on 24 Mei 2011 - 4:23 am
mf function pecah nya belum lengkap, yg dimaksud seperti ini :
function pecah($input){
for($h=0; $h<strlen($input); $h++){
$output[$h]=substr($input,$h,1);
}
return $output; }