Gapped Search

When performing string search, sometimes we want gaps so that some errors or extra information can be ignored. For example; Text : “Uzun kuyrukları ve kısa kolları olan Sinosauropteryx” In this text we want to find that “kuyruk” and “kol” either exists or not and in the order is same. Here we have a solution : “Uzun kuyrukları ve kısa kolları olan Sinosauropteryx” We can formalize the pattern like Pattern : kuyruk*kol  Where *stands for arbitrary gap characters. In this example gap is “ları ve kısa “  When we say limited we say that * can place at most given characters, here the limit can be 14.