What Is Knuth-Morris-Pratt ?

Bagi yang menyukai bahasan tentang algoritma dan pemrograman harusnya sudah mengetahui salah satu algoritma yang cukup terkenal ini. Baiklah saya beri tahu saja secara singkat Knuth Morris Pratt adalah suatu algoritma pemrograman yang ditemukan bersama-sama oleh Donald Knuth dan Pratt serta Morris secara terpisah pada tahun 1977. Meskipun antara Knuth dan Pratt serta Morris menemukan algoritma secara sendiri-sendiri, namun mereka bertiga sepakat untuk mempublikasikannya secara bersama-sama, maka jadilah nama algoritma ini Knuth-Morris-Pratt.
Algoritma Knuth-Morris-Pratt atau yang sering disingkat KMP ini merupakan salah satu algoritma yang digunakan untuk mencari apakah suatu kata terdapat dalam suatu string atau kumpulan kata. Cara kerja algoritma ini sebenarnya cukup sederhana yakni dengan cara mencocokkan kata yang mau dicari dalam string atau kumpulan kata sampai seluruh huruf dalam kata yang dicari tadi menemui padanannya dalam kumpulan kata yang ada. Jika ada satu saja huruf dari kata yang dicari tidak cocok, maka proses pengecekan akan diulangi seperti semula tapi ke karakter selanjutnya yang masih mungkin bisa sesuai dengan karakter awal dari kata yang dicari. Untuk lebih jelas mengenai cara kerja algoritma ini, perhatikan contoh pergerakan dari proses pencarian kata berikut.

1)m  : 01 23 456 7 8901 23 4 567 89 01 2
   S   : ABC   ABCDAB  ABCDABCDABDE
   W : ABCDABD
    i   : 0 1 23 45 6

Ket : dari proses pertama ini bisa diketahui bahwa huruf D dari kata yang dicari tidak sama dengan karakter spasi, maka diproses selanjutnya pencocokkan akan dimulai dari kata kedua setelah spasi, sebab karakter spasi tidak mungkin menjadi awalan dari kata yang dicari yaitu ABCDABD.

2)m : 01 2345 67 8901 23 45 67 89 01 2
    S  : ABC  ABCDAB  ABCDABCDABDE
   W :           ABCDABD
    i   :           0 1 23 45 6

Ket : dari proses kedua ini kata yang dicari masih belum sepenuhnya cocok, maka proses dilanjutkan dengan ke karakter berikutnya yang masih mungkin cocok.

3)m : 01 2345 67 890  12 345 67 89 01 2
    S  : ABC  ABCDAB   ABCDABCDABDE
   W :                       ABCDABD
    i   :                       0 1 23 45 6

Ket : proses pencocokkan kata masih gagal atau tidak memenuhi kriteria kata yang dicari.

4)m : 01 2345 67 890  12 345 67 89 01 2
    S  : ABC  ABCDAB   ABCDABCDABDE
   W :                               ABCDABD
    i   :                               0 1 23 45 6

Ket : proses pencarian sekali lagi menunjukkan bahwa kata yang dicari belum semuanya cocok dengan string yang diberikan.

5)m : 01 2345 67 890  12 345 67 89 01 2
    S  : ABC  ABCDAB   ABCDABCDABDE
   W :                                           ABCDABD
    i   :                                           0 1 23 45 6

Ket : pada langkah kelima ini semua karakter atau huruf dalam kata yang dicari menemui padanannya pada kalimat atau string yang diberikan, maka proses berhenti dengan mengembalikan posisi dimana kata ditemukan.

Dalam contoh diatas m merupakan index dari kata dalam kalimat yang dicari, S adalah kalimat dimana kata akan dicari, W adalah kata yang akan dicari dalam S, dan i adalah index dari W.
Berikut ini saya berikan source program lengkap dalam bahasa C yang saya buat berdasarkan cara kerja algoritma diatas.



#include<string.h>
#include<constream.h>
#include<stdlib.h>

int errtime=0;

void KMP(int ctrs,int ctrw,char s[],char w[],int &posketemu,int tctrs)
{if(ctrw>strlen(w)-1) //cek sdh sampai char dicari terakhir
{posketemu=ctrs-ctrw;} //maka sudah ketemu
else //jika tidak ketemu
{if(w[ctrw]==s[ctrs]) //bandingkan kar yg dicari(w[ctrw]) dgn s[ctrs]
{ctrw++; ctrs++; tctrs++;} //jika ketemu increment indek keduanya
else
{ctrw=0; // kalau tdk ketemu, jika index ctrw>0
if(s[ctrs]==' '){ctrs++; tctrs++;} //jika salah dan char " " langsung inc(ctrs);
else
{if(errtime==0)
{if(ctrs<2) ctrs="=" errtime="0;" poskata="0;">>w;
if((strncmp(s," ",strlen(s))!=0)&(strncmp(w," ",strlen(w))!=0))
{KMP(0,0,s,w,poskata,0);
if(poskata>=0)
{itoa(poskata,tpos,10);
cetak<<setxy(1,3)<<"kata ketemu di posisi :"<<tpos; getch(); }else {cetak<<setxy(1,3)<<"kata tidak ketemu dalam kalimat"; getch(); } } }

Ancaman Pemecatan Bagi 2300 Karyawan Nokia

Rencana penutupan pabrik ponsel Nokia di Jerman tampaknya akan membawa banyak masalah, khususnya bagi para karyawan produsen ponsel terbesar dunia ini. Ribuan karyawan yang bekerja disana terancam pecat, tak mustahil lagi hal ini membuat warga negara tersebut berang dan terancam boikot.
Ancaman boikot ini rupanya bukan hanya gertakan semata yang coba dilontarkan oleh ribuan karyawan serta masyarakat di Jerman yang menentang penutupan pabrikan ponsel asal Finlandia tersebut.
"Boikot Nokia!", demikian seruan kepala regional Konfederasi Serikat Pekerja Jerman Dietmar Muscheid, seperti dikutip dari MSNBC.
"Siapapun yang ingin membeli ponsel hendaknya berpikir ulang dengan mempertimbangkan bahwa perusahaan Nokia telah menyengsarakan ribuan pekerja dengan menutup pabrik di Bochum." Aksi yang dilakukan Muscheid tidak sendirian. Serikat Pekerja itu pun mendapat dukungan penuh dari Pemerintah Jerman dengan bergabung dalam gerakan boikot setelah perusahaan ponsel tersebut mengumunkan penutupan pabriknya.
Menteri Pertanian Jerman, Horst Seehofer mengungkapkan, bahwa dia akan berpindah ke merek ponsel lain setelah kejadian penutupan pabrik ini. "Aku tidak menyukai apa yang telah mereka lakukan", seperti ditulis Deutsche Presse Agenture.
Sementara di lain pihak, Sekretaris Menteri Ekonomi Jerman, Hartmut Schauerte mengaku sedang mempersiapkan pertemuan dengan manajemen puncak Nokia untuk membahas masalah penutupan pabriknya.

IBM dan Apple Serbu Microsoft

International Business Machine(IBM) dan Apple Inc yang selama ini adalah pesaing dalam dunia bisnis komputer, sepakat untuk menyatukan kekuatan dalam menghadapi Microsoft si raksasa software.
Kerjasama diantara dua perusahaan raksasa itu nantinya berupa software e-mail dari IBM yang disediakan untuk kedua produk Apple iPhone dan iPod Touch. Software e-mail bernama Lotus Notes yang menggunakan server e-mail Domino milik IBM, akan tersedia secara cuma-cuma bagi pengguna yang telah mengantongi lisensi akses Lotus Web. Bagi pengguna baru akan dikenai biaya USD 39 per tahun.
Seperti yang saya ketahui dari Technewsworld, IBM juga akan merilis Lotus Notes dan Lotus Symphony yang mencakup software pengolah dokumen, spreadsheet, dan software lain yang mirip dengan produk Microsoft, Microsoft Office untuk komputer Apple Macintosh.
Melalui kerjasama kedua perusahaan akan saling diuntungkan. Sebanyak 135 juta pengguna Lotus di seluruh dunia dapat melihat e-mail Lotus dari produk Apple yang begitu populer iPhone. Kerja sama ini juga akan menjadikan gadget buatan Apple ini lebih kuat dalam bersaing dengan smartphone lain.

Cuma 1,1 Persen Dosen Mampu Meneliti

Dari 180.000 dosen di Indonesia, diperkirakan hanya sekitar 1,1 persen yang mampu meneliti secara layak. Tidak heran, kontribusi Indonesia pada perkembangan ilmu pengetahuan amat rendah.
Demikian disampaikan penilai hibah bersaing Direktorat Jenderal Pendidikan Tinggi (Dikti), Mien A Rifai APU, di Surabaya, Selasa (22/1). "Setidaknya saya lihat itu berdasarkan proposal penelitian yang masuk ke Dikti. Secara umum yang mampu meneliti dengan layak", ujarnya.
Banyak dosen lebih sibuk mengajar di banyak tempat daripada meneliti untuk kepentingan pengembangan ilmu. Pasalnya, penelitian untuk bidang ilmu dinilai lebih merepotkan.
Untuk mendapat hibah bersaing dari Ditjen Dikti, dosen harus mengajukan proposal. Meski sudah cukup susah membuat proposal, belum tentu dana diterima oleh dosen tersebut jika kalah bersaing.
Lain halnya jika mereka mengajar di banyak tempat. Mereka bisa segera mendapat bayaran tanpa perlu banyak kerepotan. Bayaran bisa langsung diterima setelah selesai mengajar. "Tetapi akibatnya penelitian amat kurang", ujarnya.
Penelitian yang kurang itu berujung pada rendahnya publikasi ilmiah dari dosen Indonesia di jurnal internasiona. Data dari banyak penerbit internasional menyebutkan kontribusi Indonesia pada jurnal internasional hanya 0,012 persen.
Kontribusi itu lebih rendah dari Nepal yang mampu menyumbang 0,014 persen. Padahal, Nepal negaranya lebih kecil dan kalah maju dibandingkan dengan Indonesia.
"Kalau dibandingkan dengan Singapura, malah lebih jauh lagi. Singapura menyumbang 0,179 persen bagi jurnal internasional", tuturnya.
Mien kurang sepakat bila dana dijadikan alasan. Sebab, dana relatif cukup tersedia. "Dari Dikti saja ada Rp 240 miliar untuk tahun 2007 lalu", ujarnya.
Penilai hibah lainnya, Suminar S Achmadi, mengatakan butuh waktu panjang untuk meningkatkan kemampuan dosen.

Sumber : www.kompas.com (RAZ)

HIDUP

Suatu kesempatan tersempurna yang pernah ada. Suatu jenjang waktu yang tidak akan terulang. Suatu masa dengan kenangan-kenangan yang akan selalu membekas dalam benak kita serta orang di sekitar kita. Kenangan itu dimana kita hanya ada sekali saja di dalamnya. Kenangan akan segala perjuangan, cita-cita, idealisme atau pikiran-pikiran yang seringkali orang lain tidak mengerti. Hidup suatu perjuangan, cinta yang tidak dan belum terkatakan, apapun yang terhubung dengannya. Dari hidup aku selalu belajar hal-hal baru, belajar akan keberanian dalam menghadapi semua masalah yang terburuk sekalipun.
Hidup, kebebasan dalam melangkah, bertindak, dan berusaha asalkan semuanya itu masih sesuai dengan norma dan tidak merugikan atau mengganggu kepentingan orang lain. Hidup adalah privasi tanpa ada orang lain yang boleh mencampurinya. Namun bukan berarti setiap orang tidak bisa dan tidak mau menerima nasihat orang lain. Hidup adalah suatu perjalanan sejarah, dimana segala keunikan ada di dalamnya. Hidup kepintaran, cinta kasih, usaha, semangat dan kerja keras, serta menghargai orang lain. Itu semua adalah bagian yang menyertai (itu juga yang akan dan harus diterapkan dalam hidup). Dan yang terpenting Hidup adalah sebuah proses belajar tiada henti, menghadapi hal-hal yang belum kita mengerti dan mungkin kita tidak bisa menawar sekali pun. Hadapi dan terimalah semuanya dengan penuh keberanian serta dengan keyakinan yang mantap dan kerja keras yang terbaik.

CITA-CITA dan KEINGINAN SEORANG MANUSIA

Aku sekarang bukan orang yang dulu selalu ragu. Aku sekarang adalah orang yang percaya diri. Selalu berusaha dengan baik untuk mewujudkan cita-citaku.

Akhir-akhir ini aku belajar tentang keadilan, belajar menyuarakan kritik-kritikku. Menyuarakan hal-hal yang tidak sesuai dengan pengetahuan dan pikiranku, yang aku yakin bahwa itu adalah baik. Aku belajar merasakan apa yang dirasakan orang-orang di sekitarku, terutama mereka yang berada di garis bawah, mereka yang selalu menderita. Aku mulai belajar memberikan saran-saran untuk suatu kebaikan. Untuk diriku sendiri dan orang lain. Aku juga berusaha membaca buku sebanyak mungkin untuk menambah pengetahuanku. Aku sedang berusaha menimbulkan kembali jiwa dan hobiku membaca buku. Suatu hobi yang sudah lama hilang sejak SMP kelas 2. Aku tahu itupun tidak mudah, tetapi dengan tekad dan usaha yang keras aku pasti menyempatkan untuk itu.

Aku belajar dan terus berusaha tanpa mengenal lelah, untuk diriku sendiri dan orang disekitarku. Aku belajar rendah hati. Aku belajar banyak hal yang menurutku masih harus diperbaiki. Aku mau menjadi orang yang paling banyak memiliki ilmu pengetahuan, menjadi yang nomor satu.

Sedang belajar tentang apa arti hidup, bagaimana hidup yang bermanfaat untuk diriku sendiri dan orang lain di sekitarku. Menjadi lebih akrab, murah senyum dan selalu mengeluarkan sapaan terbaikku. Ehm masih banyak lagi hal yang masih harusku pelajari dari orang lain dan buku-buku serta semua persoalan yang aku hadapi. Supaya dari sana aku bisa menjadi lebih baik di hari depan.