Knuth–Morris–Pratt algorithm - Revision history

Brian: /* Computation of the prefix function */ --- whoops. battlefield test just now failed

2011-12-11T22:01:58Z

‎Computation of the prefix function: --- whoops. battlefield test just now failed

Brian: /* Example 1 */

2011-10-23T08:06:04Z

‎Example 1

Brian at 02:47, 7 April 2011

2011-04-07T02:47:13Z

Brian at 05:19, 6 April 2011

2011-04-06T05:19:32Z

Brian at 01:58, 6 April 2011

2011-04-06T01:58:39Z

Brian at 01:17, 6 April 2011

2011-04-06T01:17:59Z

Brian: /* Matching */ - sp.

2011-04-04T05:43:33Z

‎Matching: - sp.

Brian at 05:43, 4 April 2011

2011-04-04T05:43:05Z

Brian: notation

2011-04-04T03:35:26Z

notation

Brian: notation

2011-04-04T02:13:30Z

notation

@@ Line 37: / Line 37: @@
      while k &gt; 0 and S[k+1] &ne; S[i]
          k &larr; &pi;[k]
-     if k = 0
+     if S[k+1] = S[i]
          &pi;[i] &larr; 0
      else
@@ Line 50: / Line 50: @@
      while k &gt; 0 and S[k+1] &ne; S[i]
          k &larr; &pi;[k]
-     if k &ne; 0
+     if S[k+1] = S[i]
          k &larr; k+1
      &pi;[i] &larr; k

@@ Line 5: / Line 5: @@
 ===Example 1===
-In this example, we are searching for the string <math>S</math> = '''aaa''' in the string <math>T</math> = '''aaaaaaaaa''' (in which it occurs seven times). The naive algorithm would begin by comparing <math>S_1</math> with <math>T_1</math>, <math>S_2</math> with <math>T_2</math>, and <math>S_3</math> with <math>T_3</math>, and thus find a match for <math>S</math> at position 1 of <math>T</math>. Then it would proceed to compare <math>S_1</math> with <math>T_2</math>, <math>S_2</math> with <math>T_3</math>, and <math>S_3</math> with <math>T_4</math>, and thus find a match at position 2 of <math>T</math>, and so on, until it finds all the matches. But we can do better than this, if we preprocess <math>S</math> and note that <math>S_1</math> and <math>S_2</math> are the same, and <math>S_2</math> and <math>S_3</math> are the same. That is, the '''prefix''' of length 2 in <math>S</math> matches the '''substring''' of length 2 starting at position 2 in <math>S</math>; ''<math>S</math> partially matches itself''. Now, after finding that <math>S_1, S_2, S_3</math> match <math>T_1, T_2, T_3</math>, respectively, we no longer care about <math>T_1</math>, since we are trying to find a match at position 2 now, but we still know that <math>S_2, S_3</math> match <math>T_2, T_3</math> respectively. Since we already know <math>S_1 = S_2, S_2 = S_3</math>, we now know that <math>S_1, S_2</math> match <math>T_2, T_3</math> respectively; there is no need to examine <math>T_2</math> and <math>T_3</math> again, as the naive algorithm would do. If we now check that <math>S_3</math> matches <math>T_4</math>, then, after finding <math>S</math> at position 1 in <math>T</math>, we only need to do ''one'' more comparison (not three) to conclude that <math>S</math> also occurs at position 2 in <math>T</math>. So now we know that <math>S_1, S_2, S_3</math> match <math>T_2, T_3, T_4</math>, respectively, which allows us to conclude that <math>S_1, S_2</math> match <math>T_3, T_4</math>. Then we compare <math>S_3</math> with <math>T_5</math>, and find another match, and so on. Whereas the naive algorithm needs three comparisons to find each occurrence of <math>S</math> in <math>T</math>, our technique only needs three comparisons to find the ''first'' occurrence, and only one for each after that, and doesn't go back to examine previous characters of <math>T</math> again. (This is how a human would probably do this search, too.
+In this example, we are searching for the string <math>S</math> = '''aaa''' in the string <math>T</math> = '''aaaaaaaaa''' (in which it occurs seven times). The naive algorithm would begin by comparing <math>S_1</math> with <math>T_1</math>, <math>S_2</math> with <math>T_2</math>, and <math>S_3</math> with <math>T_3</math>, and thus find a match for <math>S</math> at position 1 of <math>T</math>. Then it would proceed to compare <math>S_1</math> with <math>T_2</math>, <math>S_2</math> with <math>T_3</math>, and <math>S_3</math> with <math>T_4</math>, and thus find a match at position 2 of <math>T</math>, and so on, until it finds all the matches. But we can do better than this, if we preprocess <math>S</math> and note that <math>S_1</math> and <math>S_2</math> are the same, and <math>S_2</math> and <math>S_3</math> are the same. That is, the '''prefix''' of length 2 in <math>S</math> matches the '''substring''' of length 2 starting at position 2 in <math>S</math>; ''<math>S</math> partially matches itself''. Now, after finding that <math>S_1, S_2, S_3</math> match <math>T_1, T_2, T_3</math>, respectively, we no longer care about <math>T_1</math>, since we are trying to find a match at position 2 now, but we still know that <math>S_2, S_3</math> match <math>T_2, T_3</math> respectively. Since we already know <math>S_1 = S_2, S_2 = S_3</math>, we now know that <math>S_1, S_2</math> match <math>T_2, T_3</math> respectively; there is no need to examine <math>T_2</math> and <math>T_3</math> again, as the naive algorithm would do. If we now check that <math>S_3</math> matches <math>T_4</math>, then, after finding <math>S</math> at position 1 in <math>T</math>, we only need to do ''one'' more comparison (not three) to conclude that <math>S</math> also occurs at position 2 in <math>T</math>. So now we know that <math>S_1, S_2, S_3</math> match <math>T_2, T_3, T_4</math>, respectively, which allows us to conclude that <math>S_1, S_2</math> match <math>T_3, T_4</math>. Then we compare <math>S_3</math> with <math>T_5</math>, and find another match, and so on. Whereas the naive algorithm needs three comparisons to find each occurrence of <math>S</math> in <math>T</math>, our technique only needs three comparisons to find the ''first'' occurrence, and only one for each after that, and doesn't go back to examine previous characters of <math>T</math> again. (This is how a human would probably do this search, too.)
 ===Example 2===
 Now let's search for the string <math>S</math> = '''aaa''' in the string <math>T</math> = '''aabaabaaa'''. Again, we start out the same way as in the naive algorithm, hence, we compare <math>S_1</math> with <math>T_1</math>, <math>S_2</math> with <math>T_2</math>, and <math>S_3</math> with <math>T_3</math>. Here we find a mismatch between <math>S</math> and <math>T</math>, so <math>S</math> does ''not'' occur at position 1 in <math>T</math>. Now, the naive algorithm would continue by comparing <math>S_1</math> with <math>T_2</math> and <math>S_2</math> with <math>T_3</math>, and would find a mismatch; then it would compare <math>S_1</math> with <math>T_3</math>, and find a mismatch, and so on. But a human would notice that after the first mismatch, the possibilities of finding <math>S</math> at positions 2 and 3 in <math>T</math> are extinguished. This is because, as noted in Example 1, <math>S_2</math> is the same as <math>S_3</math>, and since <math>S_3 \neq T_3</math>, <math>S_2 \neq T_3</math> also (so we will not find <math>S</math> at position 2 of <math>T</math>). And, likewise, since <math>S_1 \neq S_2</math>, and <math>S_2 \neq T_3</math>, it is also true that <math>S_1 \neq T_3</math>, so it is pointless looking for a match at the third position of <math>T</math>. Thus, it would make sense to start comparing again at the fourth position of <math>T</math> (''i.e.'', <math>S_1, S_2, S_3</math> with <math>T_4, T_5, T_6</math>, respectively). Again finding a mismatch, we use similar reasoning to rule out the fifth and sixth positions in <math>T</math>, and begin matching again at <math>T_7</math> (where we finally find a match.) Again, notice that the characters of <math>T</math> were examined strictly in order.

← Older revision		Revision as of 02:47, 7 April 2011
Line 95:		Line 95:
	==References==		==References==
	<references/>		<references/>
		+
		+	==External links==
		+	* {{SPOJ\|NHAY\|A Needle in the Haystack}}

@@ Line 30: / Line 30: @@
 Here is the pseudocode:
 <pre>
 &pi;[1] &larr; 0
@@ Line 49: / Line 62: @@
 Think carefully about what this means. If <math>p > 0</math> does not satisfy the statement that <math>S_1, \ldots, S_{k-p}</math> match <math>T_{j+p}, \ldots, T_{j+k-1}</math>, then the needle <math>S</math> ''does not match'' <math>T</math> at position <math>j+p</math>, ''i.e.'', we can ''rule out'' the position <math>j+p</math>. On the other hand, if <math>p > 0</math> ''does'' satisfy this statement, then <math>S</math> ''might'' match <math>T</math> at position <math>j+p</math>, and, in fact, all the characters up to but not including <math>T_{j+k}</math> have already been verified to match the corresponding characters in <math>S</math>, so we can proceed by comparing <math>S_{k-p+1}</math> with <math>T_{j+k}</math>, and, as promised, ''never need to look back''.
 :''Proof'': Let <math>0 \leq q < k</math>. If <math>S^q \sqsupset S^k</math>, then by definition we have <math>S_1, \ldots, S_q = S_{k-q+1}, \ldots, S_k</math>. But since <math>S_1, \ldots, S_k = T_j, \ldots, S_{j+k-1}</math>, it is also true that <math>S_{k-q+1}, \ldots, S_k = T_{j+k-q}, \ldots, T_{j+k-1}</math>. Therefore <math>S_1, \ldots, S_q = T_{j+k-q}, \ldots, T_{j+k-1}</math>. If, on the other hand, it is not true that <math>S^q \sqsupset S^k</math>, then it is not true that <math>S_1, \ldots, S_q = S_{k-q+1}, \ldots, S_k</math>, so it is not true that <math>S_{k-q+1}, \ldots, S_k = T_{j+k-q}, \ldots, T_{j+k-1}</math>, so it is not true that <math>S_1, \ldots, S_q = T_{j+k-q}, \ldots, T_{j+k-1}</math>. Therefore <math>k-q</math> is a possible value of <math>p</math> if and only if <math>S^q \sqsupset S^k</math>. Since the maximum possible value of <math>q</math> is <math>\pi_k</math>, the minimum possible value of <math>p</math> is given by <math>k-\pi_k</math>. <math>_\blacksquare</math>
 ==References==
 <references/>

@@ Line 27: / Line 27: @@
 :''Proof'': We first show by induction that if <math>j</math> appears in the sequence <math>\pi^*_i</math> then <math>S^j \sqsupset S^i</math>, ''i.e'', <math>j</math> indeed belongs in the sequence <math>\pi^*_i</math>. Suppose <math>j</math> is the first entry in <math>\pi^*_i</math>. Then <math>j = i</math> and it is trivially true that <math>S^j \sqsupset S^i</math>. Now suppose <math>j</math> is not the first entry, but is preceded by the entry <math>k</math> which is valid. That is, <math>\pi_k = j</math>. By definition, <math>S^j \sqsupset S^k</math>. But <math>S^k \sqsupset S^i</math> by assumption. Since <math>\sqsupset</math> is [[Partial order|transitive]], <math>S^j \sqsupset S^i</math>.
 :We now show by contradiction that if <math>S^j \sqsupset S^i</math>, then <math>j \in \pi^*_i</math>. Assume <math>j</math> does not appear in the sequence. Clearly <math>0 < j < i</math> since 0 and <math>i</math> both appear. Since <math>\pi^*_i</math> is strictly decreasing, we can find exactly one <math>k \in \pi^*_i</math> such that <math>k > j</math> and <math>\pi_k < j</math>; that is, we can find exactly one <math>k</math> after which <math>j</math> "should" appear (to keep the sequence decreasing). We know from the first part of the proof that <math>S^k \sqsupset S^i</math>. Since the suffix of <math>S^i</math> of length <math>j</math> is a suffix of the suffix of <math>S^i</math> of length <math>k</math>, it follows that the suffix of <math>S^i</math> of length <math>j</math> matches the suffix of length <math>j</math> of <math>S^k</math>. But the suffix of <math>S^i</math> of length <math>j</math> also matches <math>S^j</math>, so <math>S^j</math> matches the suffix of <math>S^k</math> of length <math>j</math>. We therefore conclude that <math>\pi_k \geq j</math>. But <math>j > \pi_k</math>, a contradiction. <math>_\blacksquare</math>
-With this in mind, we can design an algorithm to compute the table <math>\pi</math>. For each <math>i</math>, we will first try to find some <math>j > 0</math> such that <math>S_j \sqsupset S_i</math>. If we fail to do so, we will conclude that <math>\pi_i = 0</math> (clearly this is the case when <math>i = 1</math>.) Observe that if we do find such <math>j > 0</math>, then by removing the last character from this suffix, we obtain a suffix of <math>S^{i-1}</math> that is also a prefix of <math>S</math>, ''i.e.'', <math>S^{j-1} \sqsupset S^{i-1}</math>. Therefore, we first enumerate ''all'' nonempty proper suffixes of <math>S^{i-1}</math> that are also prefixes of <math>S</math>. If we find such a suffix of length <math>k</math> which also satisfies <math>S_k = S_i</math>, then <math>S^{k+1} \sqsupset S^i</math>, and <math>k+1</math> is a possible value of <math>j</math>. So we will let <math>k = \pi_{i-1}</math> and keep iterating through the sequence <math>\pi_k, \pi_{\pi_k}, \ldots</math>. We stop if we reach element <math>j</math> in this sequence such that <math>S_{j+1} = S_i</math>, and declare <math>\pi_i = j+1</math>; this always gives an optimal solution since the sequence <math>\pi^*_i</math> is decreasing and since it contains all possible valid <math>k</math>'s. If we exhaust the sequence, then <math>\pi_i = 0</math>.
+With this in mind, we can design an algorithm to compute the table <math>\pi</math>. For each <math>i</math>, we will first try to find some <math>j > 0</math> such that <math>S_j \sqsupset S_i</math>. If we fail to do so, we will conclude that <math>\pi_i = 0</math> (clearly this is the case when <math>i = 1</math>.) Observe that if we do find such <math>j > 0</math>, then by removing the last character from this suffix, we obtain a suffix of <math>S^{i-1}</math> that is also a prefix of <math>S</math>, ''i.e.'', <math>S^{j-1} \sqsupset S^{i-1}</math>. Therefore, we first enumerate ''all'' nonempty proper suffixes of <math>S^{i-1}</math> that are also prefixes of <math>S</math>. If we find such a suffix of length <math>k</math> which also satisfies <math>S_k = S_i</math>, then <math>S^{k+1} \sqsupset S^i</math>, and <math>k+1</math> is a possible value of <math>j</math>. So we will let <math>k = \pi_{i-1}</math> and keep iterating through the sequence <math>\pi_k, \pi_{\pi_k}, \ldots</math>. We stop if we reach element <math>j</math> in this sequence such that <math>S_{j+1} = S_i</math>, and declare <math>\pi_i = j+1</math>; this always gives an optimal solution since the sequence <math>\pi^*_{i-1}</math> is decreasing and since it contains all possible valid <math>k</math>'s. If we exhaust the sequence, then <math>\pi_i = 0</math>.
 Here is the pseudocode:
@@ Line 47: / Line 47: @@
 Given that <math>S_1, \ldots, S_k = T_j, \ldots, T_{j+k-1}</math>, what positions in <math>T</math> can we rule out? Here is the result at the core of the KMP algorithm:
 :''Theorem'': If <math>k > 0</math> then <math>p = k - \pi_k</math> is the least <math>p > 0</math> such that <math>S_1, \ldots, S_{k-p}</math> match <math>T_{j+p}, \ldots, T_{j+k-1}</math>, respectively. (If <math>k = 0</math>, then <math>p = 1</math> vacuously.)
 ==References==
 <references/>

@@ Line 45: / Line 45: @@
 Suppose that we have already computed the table <math>\pi</math>. Here's where we apply this hard-won information. Suppose that so far we are testing position <math>j</math> for a match, and that the first <math>k</math> characters of <math>S</math> have been successfully matched, that is, <math>S_1 = T_j, S_2 = T_{j+1}, S_3 = T_{j+2}, \ldots S_k = T_{j+k-1}</math>. There are two possibilities: either we just continue going along <math>S</math> and <math>T</math> and comparing pairs of characters, or we decide we want to try out a new position in <math>T</math>. This occurs because either <math>k = m</math> (''i.e'', we've successfully located <math>S</math> at position <math>i</math> in <math>T</math>, and now we want to check out other positions) or because <math>S_{k+1} \neq T_{j+k}</math> (so we can rule out the current position).
-Given that <math>S_1, \ldots, S_k = T_j, \ldots, T_{j+k-1}</math>, what positions in <math>T</math> can we rule out? The key is to realize:
+Given that <math>S_1, \ldots, S_k = T_j, \ldots, T_{j+k-1}</math>, what positions in <math>T</math> can we rule out? Here is the result at the core of the KMP algorithm:
-:If <math>k > 0</math> then the next possible position in <math>T</math> is <math>j + k - \pi_k</math>, whereas if <math>k = 0</math> then it is trivially <math>j + 1</math>.
+:''Theorem'': If <math>k > 0</math> then <math>p = k - \pi_k</math> is the least <math>p > 0</math> such that <math>S_1, \ldots, S_{k-p}</math> match <math>T_{j+p}, \ldots, T_{j+k-1}</math>, respectively. (If <math>k = 0</math>, then <math>p = 1</math> vacuously.)
-That is, if currently the character <math>T_{j+k-1}</math> is known to match <math>S_k</math> (and all the preceding characters match), then we also know that <math>T_{j+k-1}</math> matches <math>S_{\pi_k}</math> and all the preceding characters match, and should continue our search by comparing <math>S_{\pi_k+1}</math> and <math>T_{j+k}</math>. On the other hand, if even <math>S_1</math> does not match the corresponding <math>T_j</math>, then we have absolutely no information about whether <math>S</math> may occur starting at <math>T_{j+1}</math>, and we must simply proceed as in the naive algorithm.
 ==References==
 <references/>

@@ Line 13: / Line 13: @@
 ==Concept==
 The examples above show that the KMP algorithm relies on noticing that certain substrings of the needle match or do not match other substrings of the needle, but it is probably not clear what the unifying organizational principle for all this match information is. Here it is:
-:''At each position <math>i</math> of <math>S</math>, find the longest proper suffix of the prefix of <math>S</math> of length <math>i</math> that is also a prefix of <math>S</math>.''
+:''At each position <math>i</math> of <math>S</math>, find the longest proper suffix of <math>S^i</math> that is also a prefix of <math>S</math>.''
-We shall denote the length of this substring by <math>\pi_i</math>, following <ref name="CLRS">Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 32.4: The Knuth-Morris-Pratt algorithm". ''Introduction to Algorithms'' (Second ed.). MIT Press and McGraw-Hill. pp. 923–931. ISBN 978-0-262-03293-3.</ref>. We can also state the definition of <math>\pi_i</math> equivalently as ''the length of the longest substring with length less than <math>i</math> ending at <math>S_i</math> which is also a prefix of <math>S</math>''.
+We shall denote the length of this substring by <math>\pi_i</math>, following <ref name="CLRS">Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 32.4: The Knuth-Morris-Pratt algorithm". ''Introduction to Algorithms'' (Second ed.). MIT Press and McGraw-Hill. pp. 923–931. ISBN 978-0-262-03293-3.</ref>. We can also state the definition of <math>\pi_i</math> equivalently as ''the maximum <math>j</math> such that <math>S_j \sqsupset S_i</math>''.
 The table <math>\pi</math>, called the ''prefix function'', occupies linear space, and, as we shall see, can be computed in linear time. It contains ''all'' the information we need in order to execute the "smart" searching techniques described in the examples. In particular, in examples 1 and 2, we used the fact that <math>\pi_3 = 2</math>, that is, the prefix '''aa''' matches the suffix '''aa'''. In example 3, we used the facts that <math>\pi_5 = 2</math>. This tells us that the prefix '''ta''' matches the substring '''ta''' ending at the fifth position. In general, the table <math>\pi</math> tells us, after either a successful match or a mismatch, what the next position is that we should check in the haystack. Comparison proceeds from where it was left off, never revisiting a character of the haystack after we have examined the next one.
@@ Line 21: / Line 23: @@
 ==Computation of the prefix function==
 To compute the prefix function, we shall first make the following observation:
-:''Prefix function iteration lemma''<ref name="CLRS"></ref>: The sequence <math>\pi^*_i = i, \pi_i, \pi_{\pi_i}, \pi_{\pi_{\pi_i}}, \ldots, 0</math> contains exactly those values <math>j</math> such that the prefix of <math>S</math> of length <math>j</math> matches the substring of length <math>j</math> ending at <math>S_i</math>.
+:''Prefix function iteration lemma''<ref name="CLRS"></ref>: The sequence <math>\pi^*_i = i, \pi_i, \pi_{\pi_i}, \pi_{\pi_{\pi_i}}, \ldots, 0</math> contains exactly those values <math>j</math> such that <math>S^j \sqsupset S^i</math>.
-That is, we can enumerate all substrings ending at <math>S_i</math> that are prefixes of <math>S</math> by starting with <math>i</math>, looking it up in the table <math>\pi</math>, looking up the result, looking up the result, and so on, giving a strictly decreasing sequence, terminating with zero.
+That is, we can enumerate all suffixes of <math>S^i</math> that are also prefixes of <math>S</math> by starting with <math>i</math>, looking it up in the table <math>\pi</math>, looking up the result, looking up the result, and so on, giving a strictly decreasing sequence, terminating with zero.
-:''Proof'': We first show by induction that if <math>j</math> appears in the sequence <math>\pi^*_i</math> then the prefix <math>S_1, S_2, \ldots, S_j</math> matches the substring <math>S_{i-j+1}, S_{i-j+2}, \ldots, S_i</math>, ''i.e'', <math>j</math> indeed belongs in the sequence <math>\pi^*_i</math>. Suppose <math>j</math> is the first entry in <math>\pi^*_i</math>. Then <math>j = i</math> and it trivially belongs (''i.e'', the prefix of length <math>i</math> matches itself). Now suppose <math>j</math> is not the first entry, but is preceded by the entry <math>k</math> which is valid. This means that the prefix of length <math>j</math> is a suffix of the prefix of length <math>k</math>. But the prefix of length <math>k</math> matches the substring of length <math>k</math> ending at <math>S_i</math> by assumption. So the prefix of length <math>j</math> is a suffix of the substring of length <math>k</math> ending at <math>S_i</math>. Therefore the prefix of length <math>j</math> matches the substring of length <math>j</math> ending at <math>S_i</math> (since <math>j < k</math>).
+:''Proof'': We first show by induction that if <math>j</math> appears in the sequence <math>\pi^*_i</math> then <math>S^j \sqsupset S^i</math>, ''i.e'', <math>j</math> indeed belongs in the sequence <math>\pi^*_i</math>. Suppose <math>j</math> is the first entry in <math>\pi^*_i</math>. Then <math>j = i</math> and it is trivially true that <math>S^j \sqsupset S^i</math>. Now suppose <math>j</math> is not the first entry, but is preceded by the entry <math>k</math> which is valid. That is, <math>\pi_k = j</math>. By definition, <math>S^j \sqsupset S^k</math>. But <math>S^k \sqsupset S^i</math> by assumption. Since <math>\sqsupset</math> is [[Partial order|transitive]], <math>S^j \sqsupset S^i</math>.
-:We now show by contradiction that if the prefix of length <math>j</math> matches the suffix of length <math>j</math> of the prefix of length <math>i</math>, ''i.e.'', if <math>j</math> "belongs" in the sequence <math>\pi^*_i</math>, then it appears in this sequence. Assume <math>j</math> does not appear in the sequence. Clearly <math>0 < j < i</math> since 0 and <math>i</math> both appear. Since <math>\pi^*_i</math> is strictly decreasing, we can find exactly one <math>k \in \pi^*_i</math> such that <math>k > j</math> and <math>\pi_k < j</math>; that is, we can find exactly one <math>k</math> after which <math>j</math> "should" appear (to keep the sequence decreasing). We know from the first part of the proof that the substring ending at <math>S_i</math> with length <math>k</math> is also a prefix of <math>S</math>. Since the substring of length <math>j</math> ending at <math>S_i</math> is a suffix of the substring of length <math>k</math> ending at <math>S_i</math>, it follows that the substring of length <math>j</math> ending at <math>S_i</math> matches the suffix of length <math>j</math> of the prefix of length <math>k</math>. But the substring of length <math>j</math> ending at <math>S_i</math> also matches the prefix of length <math>j</math>, so the prefix of length <math>j</math> matches the suffix of length <math>j</math> of the prefix of length <math>k</math>. We therefore conclude that <math>\pi_k \geq j</math>. But <math>j > \pi_k</math>, a contradiction. <math>_\blacksquare</math>
+:We now show by contradiction that if <math>S^j \sqsupset S^i</math>, then <math>j \in \pi^*_i</math>. Assume <math>j</math> does not appear in the sequence. Clearly <math>0 < j < i</math> since 0 and <math>i</math> both appear. Since <math>\pi^*_i</math> is strictly decreasing, we can find exactly one <math>k \in \pi^*_i</math> such that <math>k > j</math> and <math>\pi_k < j</math>; that is, we can find exactly one <math>k</math> after which <math>j</math> "should" appear (to keep the sequence decreasing). We know from the first part of the proof that <math>S^k \sqsupset S^i</math>. Since the suffix of <math>S^i</math> of length <math>j</math> is a suffix of the suffix of <math>S^i</math> of length <math>k</math>, it follows that the suffix of <math>S^i</math> of length <math>j</math> matches the suffix of length <math>j</math> of <math>S^k</math>. But the suffix of <math>S^i</math> of length <math>j</math> also matches <math>S^j</math>, so <math>S^j</math> matches the suffix of <math>S^k</math> of length <math>j</math>. We therefore conclude that <math>\pi_k \geq j</math>. But <math>j > \pi_k</math>, a contradiction. <math>_\blacksquare</math>
 With this in mind, we can design an algorithm to compute the table <math>\pi</math>. For each <math>i</math>, we will first try to find a nonempty proper suffix of the prefix of length <math>i</math> that is also a prefix of <math>S</math>. If we fail to do so, we will conclude that <math>\pi_i = 0</math> (clearly this is the case when <math>i = 1</math>.) Observe that if we do find a nonempty proper suffix of <math>S_i</math> that is also a prefix of <math>S</math>, and that this suffix has length <math>k</math>, then, by removing the last character from this suffix, we obtain a nonempty proper suffix of the prefix of length <math>i-1</math> that is also a prefix of <math>S</math>. Therefore, if we enumerate ''all'' nonempty proper suffixes of the prefix of length <math>i-1</math> that are also prefixes of <math>S</math>, the ''longest'' of these ''that can be extended'' (because the character after this prefix equals the character <math>S_i</math>, so that it can be added to the end of both the prefix and the suffix to give a suffix of the prefix of length <math>i</math> that is also a prefix of <math>S</math>) gives the value of <math>\pi_i</math>. So we will let <math>k = \pi_{i-1}</math> and keep iterating through the sequence <math>\pi_k, \pi_{\pi_k}, \ldots</math>. We stop if we reach element <math>j</math> in this sequence such that <math>S_{j+1} = S_i</math>, and declare <math>\pi_i = j+1</math>; this always gives an optimal solution since the sequence <math>\pi^*_i</math> is decreasing. If we exhaust the sequence, then <math>\pi_i = 0</math>.