{"id":8652,"date":"2025-01-05T02:15:10","date_gmt":"2025-01-04T23:15:10","guid":{"rendered":"https:\/\/fatihsoysal.com\/blog\/kmp-algoritmasi-bastan-sona-karsilastirmali-anlatim\/"},"modified":"2025-01-05T02:15:10","modified_gmt":"2025-01-04T23:15:10","slug":"kmp-algoritmasi-bastan-sona-karsilastirmali-anlatim","status":"publish","type":"post","link":"https:\/\/fatihsoysal.com\/blog\/kmp-algoritmasi-bastan-sona-karsilastirmali-anlatim\/","title":{"rendered":"KMP Algoritmas\u0131: Ba\u015ftan Sona Kar\u015f\u0131la\u015ft\u0131rmal\u0131 Anlat\u0131m"},"content":{"rendered":"

<\/p>\n

KMP Algoritmas\u0131: Ba\u015ftan Sona Kar\u015f\u0131la\u015ft\u0131rmal\u0131 Anlat\u0131m<\/p>\n

Metin i\u00e7inde belirli bir alt dizinin (pattern) bulunmas\u0131, bilgisayar bilimlerinde s\u0131k kar\u015f\u0131la\u015f\u0131lan bir problemdir. Bu problemi \u00e7\u00f6zmek i\u00e7in kullan\u0131lan en basit y\u00f6ntemlerden biri br\u00fct kuvvet (brute-force)<\/strong> y\u00f6ntemidir. Ancak, b\u00fcy\u00fck metinler i\u00e7in br\u00fct kuvvet y\u00f6ntemi olduk\u00e7a verimsiz olabilir. \u0130\u015fte bu noktada, Knuth-Morris-Pratt (KMP) algoritmas\u0131 devreye girer.<\/p>\n

Br\u00fct Kuvvet Y\u00f6ntemi<\/h2>\n

Br\u00fct kuvvet y\u00f6ntemi, pattern’\u0131 metnin her pozisyonunda teker teker kar\u015f\u0131la\u015ft\u0131r\u0131r. E\u015fle\u015fme yoksa, pattern bir karakter kayd\u0131r\u0131l\u0131r ve kar\u015f\u0131la\u015ft\u0131rma tekrarlan\u0131r. Bu y\u00f6ntem, en k\u00f6t\u00fc durumda O(mn) zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahiptir, burada ‘m’ pattern uzunlu\u011fu ve ‘n’ metin uzunlu\u011fudur. Yani, hem pattern hem de metin uzunlu\u011fu artt\u0131k\u00e7a, \u00e7al\u0131\u015fma s\u00fcresi \u00f6nemli \u00f6l\u00e7\u00fcde uzar. \u00d6rnek olarak, “ABABCABAB” metninde “ABAB” pattern’\u0131n\u0131 aramay\u0131 d\u00fc\u015f\u00fcnelim. Br\u00fct kuvvet, her olas\u0131 konumu teker teker deneyecek ve gereksiz tekrarlar yapacakt\u0131r.<\/p>\n

KMP Algoritmas\u0131: Daha Ak\u0131ll\u0131 Bir Yakla\u015f\u0131m<\/h2>\n

KMP algoritmas\u0131, br\u00fct kuvvet y\u00f6nteminin aksine, daha ak\u0131ll\u0131 bir yakla\u015f\u0131m kullan\u0131r. \u00d6ncelikle, pattern’\u0131n kendisinden yararlanarak bir uyumluluk tablosu (failure function)<\/strong> olu\u015fturur. Bu tablo, pattern’\u0131n herhangi bir pozisyonunda e\u015fle\u015fme olmazsa, pattern’\u0131n nereye kayd\u0131r\u0131lmas\u0131 gerekti\u011fini belirler. Bu sayede, gereksiz kar\u015f\u0131la\u015ft\u0131rmalar \u00f6nlenir ve zaman karma\u015f\u0131kl\u0131\u011f\u0131 O(n) seviyesine d\u00fc\u015f\u00fcr\u00fcl\u00fcr.<\/p>\n

\u00d6rne\u011fin, “ABAB” pattern’\u0131 i\u00e7in uyumluluk tablosu \u015fu \u015fekilde olacakt\u0131r:<\/p>\n

\nA: 0\nB: 0\nA: 1\nB: 2\n<\/code><\/pre>\n
Bu tablo,  “ABAB” pattern’\u0131n\u0131n herhangi bir pozisyonunda e\u015fle\u015fme olmamas\u0131 durumunda, ne kadar kayd\u0131r\u0131lmas\u0131 gerekti\u011fini g\u00f6sterir.  \u00d6rne\u011fin,  \u00fc\u00e7\u00fcnc\u00fc karakterde e\u015fle\u015fme olmazsa, tablo bize pattern’\u0131 bir karakter kayd\u0131rarak devam etmemiz gerekti\u011fini s\u00f6yler.<\/p>\n
KMP algoritmas\u0131n\u0131n en \u00f6nemli avantaj\u0131,  br\u00fct kuvvet y\u00f6ntemine g\u00f6re \u00e7ok daha h\u0131zl\u0131 olmas\u0131d\u0131r.  Bu, \u00f6zellikle b\u00fcy\u00fck metinler ve uzun pattern’lar i\u00e7in \u00e7ok b\u00fcy\u00fck bir fark yarat\u0131r.  Bunun sebebi,  KMP algoritmas\u0131n\u0131n daha \u00f6nceden hesaplanan uyumluluk tablosunu kullanarak,  gereksiz kar\u015f\u0131la\u015ft\u0131rmalar\u0131 en aza indirmesidir.<\/p>\n
Uyumluluk Tablosunun Olu\u015fturulmas\u0131<\/h2>\n
Uyumluluk tablosunun olu\u015fturulmas\u0131, KMP algoritmas\u0131n\u0131n \u00f6nemli bir par\u00e7as\u0131d\u0131r.  Bu tablo, pattern’\u0131n kendisini kullanarak olu\u015fturulur.  Algoritma,  pattern’\u0131n her bir \u00f6n ekini inceleyerek, en uzun uygun \u00f6n ekini bulur.  Bu en uzun uygun \u00f6n ek,  uyumluluk tablosunda ilgili karaktere kar\u015f\u0131l\u0131k gelir.<\/p>\n
Daha detayl\u0131 bir a\u00e7\u0131klama i\u00e7in,  web sitemi<\/a> ziyaret edebilirsiniz.  Ayr\u0131ca, konuyu daha iyi anlamak i\u00e7in a\u015fa\u011f\u0131daki kaynaklar\u0131 inceleyebilirsiniz:<\/p>\n