Bir String’deki Tüm Anagramları Bulma: Sabit Pencere Desenleriyle

Bir String’deki Tüm Anagramları Bulma: Sabit Pencere Desenleriyle

Bir dizideki tüm anagramları bulma problemi, yazılım mühendisliğinde sıkça karşılaşılan bir sorundur. Bu problem için birçok çözüm yöntemi mevcuttur ancak en verimli yöntemlerden biri de “sabit pencere” (veya kayan pencere) desenini kullanmaktır. Bu yöntem, özellikle büyük veri setleri için performans açısından oldukça avantajlıdır.

Öncelikle, anagram kavramını hatırlayalım. İki kelime, harflerinin sayısı ve türü aynıysa birbirinin anagramıdır. Örneğin, “listen” ve “silent” kelimeleri birbirlerinin anagramıdır. Peki, bu bilgiyi kullanarak bir string içindeki tüm anagramları nasıl bulabiliriz?

Sabit Pencere Deseniyle Anagram Bulma

Sabit pencere deseni, verinin üzerinden kayan bir pencere kullanarak işleme yapmamızı sağlar. Bu yöntemde, belirli bir boyuttaki bir pencere, string’in başlangıcından sonuna kadar bir adım bir adım kaydırılır. Her adımda, pencere içindeki karakterlerin frekanslarını kontrol ederek, aranan anagramın olup olmadığını kontrol ederiz.

Örneğin, “cbaebabacd” string’inde “abc” anagramını bulmak istediğimizi varsayalım. Üç karakterlik bir pencere oluşturup, string üzerinde kaydırarak ilerliyoruz. Her adımda pencerenin içindeki karakterlerin frekanslarını kontrol ediyoruz ve hedef anagramla eşleşip eşleşmediğini belirliyoruz.

Algoritma Adımları:

1. Aralık boyutu (anağram uzunluğu) belirlenir.
2. Bir pencere oluşturulur ve ilk konumlandırılır.
3. Pencere içindeki karakterlerin frekanslarını saklamak için bir veri yapısı (örneğin bir sözlük) kullanılır.
4. Hedef anagramın karakter frekansları bir başka sözlükte saklanır.
5. Pencere kaydırılırken, pencere içindeki karakterlerin frekansları güncellenir ve hedef anagramla karşılaştırılır.
6. Eşleşme varsa, pencere başlangıcı kaydedilir.
7. Pencere, string’in sonuna kadar kaydırılır.

Örnek Kod (Python):

def find_anagrams(text, pattern):
  """Bir string içindeki tüm anagramları bulur."""
  pattern_len = len(pattern)
  pattern_freq = {}
  for char in pattern:
    pattern_freq[char] = pattern_freq.get(char, 0) + 1

  window_start, matched = 0, 0
  window_freq = {}
  result = []

  for window_end in range(len(text)):
    right_char = text[window_end]
    if right_char in pattern_freq:
      window_freq[right_char] = window_freq.get(right_char, 0) + 1
      if window_freq[right_char] == pattern_freq[right_char]:
        matched += 1

    if window_end - window_start + 1 > pattern_len:
      left_char = text[window_start]
      window_start += 1
      if left_char in pattern_freq:
        if window_freq[left_char] == pattern_freq[left_char]:
          matched -= 1
        window_freq[left_char] -= 1

    if matched == len(pattern_freq):
      result.append(window_start)

  return result

Bu kod, verilen bir string içindeki tüm anagramları bulur ve başlangıç indekslerini döndürür. Daha detaylı bilgi için bu kaynağa bakabilirsiniz. Fonksiyonun karmaşıklığı O(N*M) şeklindedir, burada N string uzunluğu ve M pattern uzunluğudur. Bu da, büyük stringler için oldukça verimli bir çözüm olduğunu göstermektedir. Başka programlama dillerinde de benzer algoritmalar kullanılabilir.

Bu yöntem, basitliği ve performansı sayesinde birçok uygulamada tercih edilmektedir. Örneğin, metin arama motorlarında, biyoinformatikte ve veri madenciliğinde sıklıkla kullanılır.

Daha fazla bilgi ve diğer algoritma örnekleri için kendi web sitemi Fatih Soysal sitesini ziyaret edebilirsiniz.

#Etiketler

anagram, sabit pencere, algoritma, python, programlama, string manipülasyonu, verimli kodlama, Fatih Soysal, anagram bulma, kayan pencere, veri yapıları