Exact String Matching Algorithms
Preliminary Definitions A string is a sequence of characters. In our model we are going to represent a string as a 0-indexed array. So a string S = ”Galois” is indeed an array [‘G’, ’a’, ’l’, ’o’, ’i’, ’s’]. The number of characters of a string is called its length and is denoted by |S|. If we want to reference the character of the string at position i, we will use S[i]. A substring is a sequence of consecutive contiguous elements of a string, we will denote the substring starting at i and ending at j of string S by S[i...j]. A prefix of a string S is a substring that starts at position 0, and a suffix a substring that ends at |S|-1. A proper prefix of a S is a prefix that is different to S. Similarly, a proper suffix of S is a suffix that is different to S. The + operator will represent string concatenation. Example: S = "Galois" | S |= 6 S [ 0 ]= 'G' , S [ 1 ]= 'a' , S [ 2 ]= 'l' ,..., S [ 5 ]= 's' S [ 1. .. 4 ]= ...