 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
String Matching
Glossary
| string-matching problem | 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. Further 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. Pattern P occurs with shift s in text T (or, equivalently, pattern P occurs beginning at position s + 1 in text T) if 0 ≤ s ≤ n - m and
T[s + 1..s + m] = P[1..m] (that is, if T[s + j] = P[j], for 1 ≤ j ≤ m). if P occurs with shift s in T, then we call s a valid shift; otherwise, we call s an invalid shift. The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T.
(See page 906)
| | | | | empty string | zero-length, denoted ε
(See page 907)
| | | | | concatenation | of two strings x and y, denoted xy, has length |x| + |y| and consists of the characters from x followed by the characters from y.
(See page 907)
| | | | | rejected | an input that is not accepted
(See page 917)
| | | | | final-state function | A finite automaton M induces a function φ, called the final-state function, from Ε* to Q such that φ(w) is the state M ends up in after scanning the string w. Thus, M accepts a string w if and only if φ(w) ∈ A.
(See page 917)
|
|
2002 McGraw-Hill Higher Education