W[i] and increments i if they are equal. This is depicted, at the start of the run, like 1 2 m: 01234567890123456789012 S: W: i: The algorithm compares successive characters of W to "parallel" characters of S, moving from one to the next by incrementing i if they match. However, in the fourth step S[3] = ' ' does not match W[3] = 'D'. Rather than beginning to search again at S[1], we note that no 'A' occurs between positions 1 and 2 in S; hence, having checked all those characters previously (and knowing they matched the corresponding characters in W), there is no chance of finding the beginning of a match. Therefore, the algorithm sets m = 3 and i = 0. 1 2 m: 01234567890123456789012 S: ABC W: i: This match fails at the initial character, so the algorithm sets m = 4 and i = 0 1 2 m: 01234567890123456789012 S: ABC W: i: Here, i increments through a nearly complete match "ABCDAB" until i = 6 giving a mismatch at W[6] and S[10]. However, just prior to the end of the current partial match, there was that substring "AB" that could be the beginning of a new match, so the algorithm must take this into consideration. As these characters match the two characters prior to the current position, those characters need not be checked again; the algorithm sets m = 8 (the start of the initial prefix) and i = 2 (signaling the first two characters match) and continues matching. Thus the algorithm not only omits previously matched characters of S (the "AB"), but also previously matched characters of W (the prefix "AB"). 1 2 m: 01234567890123456789012 S: ABC ABCD W: i: This search at the new position fails immediately because W[2] (a 'C') does not match S[10] (a ' '). As in the first trial, the mismatch causes the algorithm to return to the beginning of W and begins searching at the mismatched character position of S: m = 10, reset i = 0. 1 2 m: 01234567890123456789012 S: ABC ABCDAB W: i: The match at m=10 fails immediately, so the algorithm next tries m = 11 and i = 0. 1 2 m: 01234567890123456789012 S: ABC ABCDAB W: i: Once again, the algorithm matches "ABCDAB", but the next character, 'C', does not match the final character 'D' of the word W. Reasoning as before,