-1. W[5] itself extends the prefix match begun with W[4], and we can assume that the corresponding character in S, S[m+5] ≠ 'B'. So backtracking before W[5] is pointless, but S[m+5] may be 'A', hence T[5] = 0. Finally, we see that the next character in the ongoing segment starting at W[4] = 'A' would be 'B', and indeed this is also W[5]. Furthermore, the same argument as above shows that we need not look before W[4] to find a segment for W[6], so that this is it, and we take T[6] = 2. Therefore, we compile the following table: Another example: Another example (slightly changed from the previous example): Another more complicated example: Description of pseudocode for the table-building algorithm The example above illustrates the general technique for assembling the table with a minimum of fuss. The principle is that of the overall search: most of the work was already done in getting to the current position, so very little needs to be done in leaving it. The only minor complication is that the logic which is correct late in the string erroneously gives non-proper substrings at the beginning. This necessitates some initialization code. algorithm kmp_table: input: an array of characters, W (the word to be analyzed) output: an array of integers, T (the table to be filled) define variables: an integer, pos ← 1 (the current position we are computing in T) an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring) let T[0] ← -1 while pos < length(W) do if W[pos] = W[cnd] then let T[pos] ← T[cnd] else let T[pos] ← cnd while cnd ≥ 0 and W[pos] ≠ W[cnd] do let cnd ← T[cnd] let pos ← pos + 1, cnd ← cnd + 1 let T[pos] ← cnd (only needed when all word occurrences are searched) Efficiency of the table-building algorithm The time (and space) complexity of the table algorithm is , where is the length of W. The outer loop: pos is initialized to 1, the loop condition is pos < k, and pos is increased by 1 in every iteration of the loop. Thus the loop will take iterations. The inner loop: cnd is initialized to 0 and gets increased by at most 1 in each outer loop iteration. T[cnd] is always less than cnd, so cnd gets decreased by at least