String matching

String matching

String matching or searching algorithms try to find places where one or several strings (also called patterns) are found within a larger string (searched text).

Text-editing programs frequently need to find all occurrences of a pattern in the text. Efficient algorithms for this problem are called “string matching” algorithms that can greatly help the responsiveness of the text-editing program.

The string-matching problem is formalized as follows:

Assume that the text is an array T[1. . n] of length n and that the pattern is an array P[1. .m] of length m ≤ n. Assume that the elements of P and T are characters drawn from a finite alphabet Ʃ. The character arrays P and T are often called strings of characters.

The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T.

If the pattern P occurs with shift s in T, then s is called valid shift; otherwise, s is an invalid shift.

Pattern P occurs with shift s in text T if 0 ≤ s ≤ n-m and T [s+1. . s +m] = P [1. .m].