String Algoritma Terimleri ve SubSequence

Terimler Ve SubSequence 

Merhabalar, Bugün string algoritma terimlerinden ve subsequence bulma metodunun nasıl yazılabileceğinden bahsedeceğim.

Yüksek lisanta gördüğüm bu terimleri paylaşarak hem bilmeyenleri bilgilendirmeyi hem de gerektiğinde kendimi tekrar etmeyi hedeflemekteyim.

Prefix

               Teorik tanımı ile  y=u.x.v olarak kabul ettiğimizde ve u' nun bir boş string olduğunu kabul edersek, x y'nin prefix'i olmuş olmakta. 

                Daha anlaşılır bir dille elimizde y , u, x ve v diye stringler var. stringler arasındaki .(nokta) çarpma anlamına gelmekte yani stringlerin yan yana koyarak birleştirilmesidir. Yani bu mantıkla "ali"."ata"="aliata"gibi. u stringini boş bir string kabul ettiğimize göre aslında y: x ve v nin birleşiminden oluşmakta  x'i "umut" v'yi "coşkun" kabul edersek y="umutcoşkun" olacak ve bu drumda "umut" y stringinin prefixi olacaktır. yani açıkcası stringin baştan  tüm kombinasyonları onun prefixi kabul edilir.y nin prefixleri: "u", "um","umu"..."umutcoskun".

Suffix

         Suffix ise prefixin tersidir. yani Teorik olarak  y=u.x.v olarak kabul ettiğimizde ve v' nin bir boş string olduğunu kabul edersek, x y'nin suffix'i olmuş olmakta. Üstteki örnekten yola çıkarsak y'nin suffixleri "umutcoskun","utcoskun",..."coskun",.."n". olarak sıralanabilir.

Factor

          Factor ise teorik tanımdan yola çıkarak  y=u.x.v olarak kabul ettiğimizde x y'nin factorüdür. yani aslında suffix ve prefix de aslında bir factor dür.

SubSequence

             Teorik tanımdan yola çıkarsak y= |x| +1sting ifadesini karşılıyor ise yani string elemanları 'w' ile gösterirsek w0,w1, . . . , w|x| olarak kabul edelim eğer y = w0x[0]w1x[1] . . . x[|x| − 1]w|x| ise  x y'nin subsequence idir. 

aslında daha kaba bir dille söylemek gerekirse x, y-x harflerini y den silerek elde ettiğimiz bir stringtir. aşağıdaki örnekte daha iyi anlaşılacağını düşünüyorum.

static boolean isSubSequence(String x, String y, int m, int n) {

  if (m == 0)
   return true;
  if (n == 0)
   return false;

  if (x.charAt(m - 1) == y.charAt(n - 1))
   return isSubSequence(x, y, m - 1, n - 1);

  return isSubSequence(x, y, m, n - 1);
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub

 
  String subSeq="umut";
  String y="htucozmgeisuiklatr";
  
  int m = subSeq.length();
  int n = y.length();
  boolean res = isSubSequence(subSeq, y, m, n);
  if (res)
   System.out.println("Yes");
  else
   System.out.println("No");
 }

Girdi: subSeq = "ABC", y = "APTBKCL"
Çıktı: Yes

Girdi: subSeq = "ABC", y= "APTBKL"
Çıktı: No

Girdi: subSeq = "umut", y= "htucozmgeisuiklatr"
Çıktı: Yes

Görüldğü gibi her harfin varlığı ters sıralama ile kontrol ediliyor verildiği sıra ile bulununca "yes" sonucu dönülüyor.