String Matching algorithm String Matching algorithm String Matching algorithm

String Matching algorithm

1. WHAT IS STRING MATCHING ? In computer science, String searching algorithms, sometimes called string matching algorithms, that try to be find place where one or several string (also called pattern) are found within a larger string or text.

2. EXAMPLE A B C C A T D E F SHIFT = 3 C A T PATTERN MATCH TEXT

3. STRING MATCHING ALGORITHM There are many types of String Matching Algorithm like:- The Naive string-matching algorithm. The Rabin-Karp algorithm. String matching with finite automata The Knuth-Morris-Pratt algorithm

4. Naïve String Matching Algorithm

5. PSEUDO-CODE NaiveStringMatch (Text, Pattern): n = length(Text) m = length(Pattern) for i = 0 to n - m j = 0 while j < m and Pattern[j] = Text[ i + j] j = j + 1 if j = m print "Pattern found at position", i

6. Rabin-Karp Algorithm

7. PSEUDO-CODE In this pseudo-code: T is the text P is the pattern d is the number of characters in the input set. q is a prime number used as modulus n = length[T] m = length[P] h = pow(d, m-1) mod q P = 0 t0 = 0 # Preprocessing: Compute the hash value of the pattern and the first substring of T for i = 1 to m P = (d*P + P[ i ]) mod q t0 = (d*t0 + T[ i ]) mod q # Matching: Slide the window through T and compare hash values for s = 0 to n-m if P = ts if P[1.....m] = T[s+1..... s+m ] if s < n-m ts+1 = (d*( ts - T[s+1]*h) + T[s+m+1]) mod q