67

String Matching Introduction

String Matching Algorithm is also called “String Searching Algorithm.” This is a vital class of string algorithm is declared as “this is the method to find a place where one is several strings are found within the larger string.”

Given a text array, T [1…..n], of n character and a pattern array, P [1……m], of m characters. The problems are to find an integer s, called valid shift where 0 ≤ s < n-m and T [s+1……s+m] = P [1……m]. In other words, to find even if P in T, i.e., where P is a substring of T. The item of P and T are character drawn from some finite alphabet such as {0, 1} or {A, B …..Z, a, b….. z}.

Given a string T [1……n], the substrings are represented as T [i……j] for some 0≤i ≤ j≤n-1, the string formed by the characters in T from index i to index j, inclusive. This process that a string is a substring of itself (take i = 0 and j =m).

The proper substring of string T [1……n] is T [1……j] for some 0<i ≤ j≤n-1. That is, we must have either i>0 or j < m-1.

Using these descriptions, we can say given any string T [1……n], the substrings are

And proper substrings are

Note: If i>j, then T [i…..j] is equal to the empty string or null, which has length zero.

Algorithms used for String Matching:

There are different types of method is used to finding the string

1. The Naive String Matching Algorithm
2. The Rabin-Karp-Algorithm
3. Finite Automata
4. The Knuth-Morris-Pratt Algorithm
5. The Boyer-Moore Algorithm