Tuduhaké menu pokok

Algoritma panggolèkan string

Algoritma panggolèkan string utawa asring karan uga panyocokan string ya iku algoritma kanggo nggolèki kabèh kamunculan string cendhak sing karan pattern ing string sing luwih dawa sing karan tèks.[1]

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

Conto algoritma panyocokkan stringBesut

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

Telung kategori iku ya iku:

Algoritma brute force jroing panggolèkan stringBesut

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

Carané kerjaBesut

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

  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 cocog (mismatch).
    2. Kabèh karakter ing pattern cocog. 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.

PseudocodeBesut

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ènsiBesut

  1. Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5
  2. Breslauer, Dany. 1992. Efficient String Algorithms. dhokumèn

Pirsanana ugaBesut

Pranala njabaBesut