Algoritma panggolèkan string

Saka Wikipédia, Bauwarna Mardika abasa Jawa / Saking Wikipédia, Bauwarna Mardika abasa Jawi
Langsung menyang: pandhu arah, pados

Algoritma panggolèkan string utawa asring disebut uga panyocokan string yaiku algoritma kanggo nggolèki kabèh kamunculan string cendhak pattern[0..n-1] sing disebut pattern ing string sing luwih dawa teks[0..m-1] sing disebut tèks. [1]

Panyocokkan string arupa pamasalahan paling prasaja saka kabèh pamasalahan string liyané, lan dianggep minangka bagéyan saka pamrosèsan data, pangomprèsian data, analisis leksikal, lan temu walik informasi. Tèknik kanggo ngrampungaké pamasalahan panyocokkan string biasané bakal ngasilaké implikasi langsung marang aplikasi string liyané[2].

Conto algoritma panyocokkan string[sunting | sunting sumber]

Algoritma-algoritma panyocokkan string bisa diklasifikasikaké dadi telung bagéyan miturut arah panggolèkané.

Telung kategori iku yaiku :

Algoritma brute force jroing panggolèkan string[sunting | sunting sumber]

Algoritma brute force arupa algoritma panyocokan string sing ditulis tanpa mikiraké paningkatan performa. Algoritma iki arang banget dienggo jroning praktèk, nanging migunani jroning studi pambandhing lan studi-studi liyané.

Carané kerja[sunting | sunting sumber]

Sacara sistematis, langkah-langkah sing dilakoni algoritma brute force nalika nyocokaké string yaiku:

  1. Algoritma brute force wiwit nyocokaké pattern ing awal tèks.
  2. Saka kiwa nengen, algoritma iki bakal nyocokaké karakter per karakter pattern karo karakter ing tèks sing padha selaras, nganti salah siji kondhisi iki kapenuhi:
    1. Karakter ing pattern lan ing tèks sing dibandhingaké ora cocok (mismatch).
    2. Kabèh karakter ing pattern cocok. Sawisé iku algoritma bakal nggenahi panemon ing posisi iki.
  3. Algoritma banjur terus nggèsèr pattern siji nengen, lan mbalèni langkah angka 2 nganti pattern ada ing ujung tèks.

Ing ngisor iki Algoritma brute force sing lagi temandang nggolèki string:

Algoritma brute force sing lagi temandang nggolèki string.

Pseudocode[sunting | sunting sumber]

Pseudocode algoritma brute force iki:

procedure BruteForceSearch(
        input m, n : integer,
        input P : array[0..n-1] of char,
        input T : array[0..m-1] of char,
        output ketemu : array[0..m-1] of boolean
       )

Deklarasi:
       i, j: integer 

Algoritma:
        for (i:=0 to  m-n) do
               j:=0
               while (j < n and T[i+j] = P[j]) do    
                        j:=j+1
               endwhile
               if(j >= n) then
                         ketemu[i]:=true;
               endif 
        endfor

Réferènsi[sunting | sunting sumber]

  1. ^ (en)Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5
  2. ^ (en)Breslauer, Dany. 1992. Efficient String Algorithms. dokumen

Pirsanana uga[sunting | sunting sumber]

Pranala njaba[sunting | sunting sumber]