Competitive Programming – Naive String Matching Algorithm

NAIVE ALGORITMASI

String match etme problemleri hakkındaki algoritmalar üzerine herhangi bir yazı okuduğunuzda hemen hemen hepsi klasik yöntem olan Naive Algorithm ile başlar. Ben de bu adeti bozmayayım ve konuya direkt giriş yapayım.

Problemimiz basit. Elimizde bir string var ki biz buna bundan sonra pattern diyeceğiz ve bir de herhangi bir textimiz var. Amacımız patternimiz textimizin içerisinde geçiyor mu bunu bulabilmek. Naive algoritması da aklınıza gelebilecek en klasik yöntemle bu soruya cevap buluyor. Karakter karakter sıralamak… Hemen somut bir örnek üzerinden naive algoritmasını inceleyelim.

Textimiz ACBAACAA patternimiz de AABA olsun. Naive algoritmasını kullanarak textimiz patternimiz içerisinde geçiyor mu bunu bulalım.

Süreç şu şekilde işler

ilk tur..

0    1    2    3    4    5    6    7
A    C    B    A    A    B    A    A

A    A    B    A
0    1    2    3                                          

A ile A eşit mi  –> Evet

C ile A eşit mi –> Hayır

Pattern bir yana kayar..

ikinci tur..

0    1    2    3    4    5   6    7
A    C    B    A    A    B   A    A

     A    A    B    A
     0    1    2    3                                          

C ile A eşit mi  –> Hayır 

Pattern bir yana kayar..

üçüncü tur..

0    1    2    3    4    5    6    7
A    C    B    A    A    B    A    A

          A    A    B    A
          0    1    2    3   

B ile A eşit mi  –> Hayır

Pattern bir yana kayar..

dördüncü tur..

0    1    2    3    4    5    6    7
A    C    B    A    A    B    A    A

               A    A    B    A
               0    1    2    3       

A ile A eşit mi  –> Evet

A ile A eşit mi  –> Evet

B ile B eşit mi  –> Evet

A ile A eşit mi  –> Evet

Eşleşme detected.

Naive string matching algoritması bu kadar basit. Ancak algoritma dünyasının geldiği noktayı düşünürsek kulağa biraz ilkel gelmiyor değil öyle değil mi? . Peki Naive Algorithm biraz daha iyileştirilemez mi? Bir matching algoritmasının iyileştirilmesinden kasıt comparison(kıyaslama) sayısının azaltılmasıdır. Naive algoritması üzerine kafa yoran insanlar naivei daha optimize bir hale getirmişler. Ancak bu Optimized naive algorithm olarak diğer yazımın konusu olacak. 🙂

NAIVE ALGORITMASININ ANALIZI

Bir string matching algoritmasında best case daha ilk eşleşme denemesinde patternin text içerisinde detect edilmesidir. Patternin boyutuna m textin boyutuna da n diyelim.

Eğer patternin ilk harfi text içerisinde yer almıyorsa bu best case’dir. Çünkü her bir shift için sadece bir kere kıyaslama yapacak ve daha ilk harfi bulamayınca kıyaslama yapmayı bırakacaktır. Bu durumda Best case O(n) diyebiliriz.

Worst case ise iki durumda oluşur. İlki pattern ve text aynı karakterlerden oluşuyor ise yani pattern “aaa” text “aaaaaaaaa” durumunda. Böyle bir durumda aşağıdaki C# kodundan da çıkarım yapabileceğiniz gibi complexity  O(m*(n-m+1)) olacaktır. Aynı complexityi veren 2. durum ise  pattern”VVVK” text “VVVVVVVVVVVVK” durumudur.

Best case ve Worst case’in ortalama değerini aldığımızda Naive algoritmasının complexitysi O(m*(n-m+1)) diyebiliriz.

Yukarıdaki logic için Naive algoritmasının C# ile kodlanması aşağıdaki gibi olacaktır.

public static void NaiveAlgorithm(string[] pattern, string[] text)
{
   int lengthOfPattern = pattern.Length;
   int lengthOfText = text.Length;
   int j;

   for (int i = 0; i <= lengthOfText - lengthOfPattern; i++)
   {
       for (j = 0; j < lengthOfPattern; j++)
         if (text[i + j] != pattern[j]) 
           break;
    
       if(j == lengthOfPattern)
       Console.WriteLine("Matched");

    } 
}