Exercises — KMP algorithm — failure function, O(n+m) — full derivation

We fill one index at a time. For each $i$ we look at $S[\mathrm{0..}i]$ and find the longest string that is both a prefix and a suffix but not the whole thing.

Why $\pi [4]=2$? aabaa starts with aa and ends with aa; those match. The next candidate aab is a prefix but the suffix of length 3 is baa ≠ aab. So the answer is $2$.

Answer: $\pi =[0,1,0,1,2]$.

Every prefix of aaaa is all a's, and so is every suffix. The longest proper border of a...a (length $k$) is a...a of length $k-1$.

Answer: $\pi =[0,1,2,3]$. It climbs by exactly $1$ each step because a run of identical characters extends its border every time.

The algorithm starts each step at $j=\pi [i-1]$. Here $i=4$, so $j=\pi [3]=2$. We compare $S[4]$ with $S[j]=S[2]$.

• $S[4]=$ a, $S[2]=$ a → they match. So we extend: $j\leftarrow j+1=3$.
• Set $\pi [4]=3$.

No fallback was needed because the very first comparison matched.

What the figure shows: the string ababa drawn as boxed cells. The cyan box marks the old border ab sitting as a prefix (cells 0–1); the amber box marks the same ab sitting as a suffix of the previous prefix abab (cells 2–3). The white arrow points at cell 4 (the new a): because it equals $S[2]=$a, both the cyan prefix and amber suffix grow by one cell into aba, so $\pi [4]$ jumps from the old $2$ to $3$. The picture is the geometric meaning of the single line "$j\leftarrow j+1$".

Answer: $\pi [4]=3$.

Step 1 — build $\pi$ for aba:

So $\pi =[0,0,1]$, and the pattern length is $m=3$.

Step 2 — scan the text with $j$ starting at $0$:

Answer: matches at positions $0$ and $2$ (overlapping occurrences of aba in ababa).

We index $\pi$ by $j-1$ each fallback. Start $j=6$.

• $j=6$ → $\pi [5]=2$. Meaning: the longest border of the matched prefix aabaaa has length $2$ (that border is aa). We slide the pattern so its first aa aligns where the text's last aa sat.
• Now $j=2$: compare $P[2]=$b with the same text char. Suppose it still mismatches. Fall back: $\pi [1]=1$.
• $j=1$: compare $P[1]=$a. Suppose still mismatch. Fall back: $\pi [0]=0$.
• $j=0$: we stop the while (guard is $j>0$). Now we compare $P[0]$ once; if it matches, $j$ becomes $1$, else stays $0$.

Chain: $6\to 2\to 1\to 0$. Each arrow drops $j$ to the length of the next nested border.

What the figure shows: the matched prefix aabaaa in boxed cells. The two cyan boxes highlight the border aa appearing at the front (cells 0–1) and at the back (cells 4–5) — this is the length-2 border that $\pi [5]=2$ refers to. The curved amber arrow sweeps the front aa over onto the back aa, which is exactly what "slide the pattern so its first aa lands on the last aa" looks like. The amber text below spells out the whole fallback chain $6\to 2\to 1\to 0$ so you can see each drop lands on the length of the next smaller nested border.

Answer: fallback chain from $j=6$ is $6,2,1,0$.

Border length $\pi [7]=5$ means the longest border of abcabcab is abcab (length 5). The smallest period is $p=m-\pi [m-1]=8-5=3.$ That period is abc: shifting the string right by 3 lines it up with itself where the overlap holds. To be a full repetition we need $p\mid m$, i.e. $3\mid 8$? No — $8=3\cdot 2+2$, remainder $2\ne 0$.

So abcabcab is almost three copies of abc but chopped off: it is abc abc ab. The period is $3$ but the string is not a whole number of periods. (Compare with Borders and Periods of Strings.)

Answer: smallest period $p=3$; $p$ does not divide $m=8$, so it is not a full repetition.

The chosen string: $S=\text{aaaaab}$ (five a's then a b), length $m=6$. We commit to this one string for the rest of the exercise.

Why this is the worst case for $m=6$. As we scan the five leading a's, the border variable $j$ climbs as high as it possibly can: $\pi =[0,1,2,3,4]$ up to index $4$, so just before the final character $j$ has reached $4$. The last character b matches none of the earlier a's, so it forces $j$ to walk all the way back down through every nested border in one step. No length-6 string can push $j$ higher than a full run of equal characters does, so no length-6 string can cause a longer single-step fallback.

Trace of the expensive step ($i=5$, computing $\pi [5]$, $S[5]=$b):

• $j=\pi [4]=4$. Compare $S[5]=$b with $S[4]=$a → mismatch. $j\leftarrow \pi [3]=3$.
• $j=3$. $S[5]=$b vs $S[3]=$a → mismatch. $j\leftarrow \pi [2]=2$.
• $j=2$. b vs $S[2]=$a → mismatch. $j\leftarrow \pi [1]=1$.
• $j=1$. b vs $S[1]=$a → mismatch. $j\leftarrow \pi [0]=0$.
• $j=0$. b vs $S[0]=$a → mismatch, but the while guard $j>0$ now stops us. So $\pi [5]=0$.

That single index performed four fallbacks: $4\to 3\to 2\to 1\to 0$.

Why the total is still $O(m)$. Track $j$ across the entire build, not one index. Two forces act on $j$:

• The line j += 1 runs at most once per index $i$, so across all $m$ indices $j$ increases by at most $m-1$ in total (here at most $5$).
• Every while fallback step strictly decreases $j$ (because $\pi [j-1]<j$), by at least $1$.
• $j\ge 0$ always.

A quantity that starts at $0$, rises by at most $m-1$ in total, and never drops below $0$ cannot fall more than $m-1$ times in total. So the number of fallback steps summed over the whole build is $\le m-1=O(m)$ — even though one index (here $i=5$) absorbed almost all of them. This is the potential / accounting method of Amortized Analysis.

What the figure shows: a line plot of the value of $j$ against each algorithm step while building $\pi$ for aaaaab. The cyan line climbs one step at a time (the five +1 extensions on the leading a's), then plunges straight down at the end (the four fallbacks on the final b). The amber dots mark each recorded state. Visually the "area of rise" bounds the "area of fall": because the line can only go up $\le m-1$ total, it can only come down $\le m-1$ total — that is the amortized $O(m)$ argument as a shape.

Answer: worst-case string aaaaab; it triggers a 4-step fallback $4\to 3\to 2\to 1\to 0$ at its last character, yet the total fallback count over the whole build is $\le m-1=5=O(m)$.

Idea. Run the ordinary matching loop, but keep a single integer counter. Every time $j$ reaches $m$ we do count += 1, report nothing, and immediately fall back with $j\leftarrow \pi [m-1]$ so the search continues into overlaps.

j = 0; count = 0
for i = 0 .. n-1:
    while j > 0 and T[i] != P[j]:
        j = pi[j-1]
    if T[i] == P[j]:
        j += 1
    if j == m:
        count += 1
        j = pi[m-1]

Why overlaps are counted correctly. After a full match we do not reset $j=0$. Setting $j=\pi [m-1]$ keeps exactly the longest prefix of $P$ that is still validly aligned with the text tail. If $P$ can overlap itself (like aba in ababa), this preserved overlap lets the next occurrence be found without moving $i$ backward.

Cost. The loop is the same amortized $O(n)$ matching loop; building $\pi$ is $O(m)$; total $O(n+m)$. Storage is a single counter, $O(1)$ extra.

Sanity check. For $P=$aa ($m=2$), $T=$aaaa ($n=4$): matches end at $i=1,2,3$ → count $=3$. Answer: count $=3$ overlapping occurrences.

Key fact. The set of all border lengths of $S$ is exactly the chain $\pi [m-1],\pi [\pi [m-1]-1],\pi [\pi [\pi [m-1]-1]-1],\dots ,0.$ Why: the longest border has length ${\ell }_1=\pi [m-1]$. The next-shorter border of $S$ must be a border of that longest border (borders nest), and the longest border of a length-${\ell }_1$ prefix is stored at $\pi [{\ell }_1-1]$. Repeat until we hit $0$. Each step follows one pointer, and the values strictly decrease, so the chain has length $\le m$: overall $O(m)$.

Apply to abacabaabacaba ($m=14$). First we actually build $\pi$ for it. The string is a b a c a b a a b a c a b a. Running the standard build gives $\pi =[0,0,1,0,1,2,3,1,2,3,4,5,6,3].$ So the last value is $\pi [13]=3$ (the longest border of the whole string is aba, length $3$ — the string both starts and ends with aba). Now walk the chain of border lengths:

• ${\ell }_1=\pi [13]=3$ (border aba).
• Next: $\pi [{\ell }_1-1]=\pi [2]=1$ (border a).
• Next: $\pi [1-1]=\pi [0]=0$ → stop.

Chain of border lengths: $3\to 1\to 0$.

So $S$ has borders of length $3$ and $1$ (plus the trivial empty border): the prefixes aba and a.

Answer: all non-empty border lengths $=\{3,1\}$, found by walking $3\to \pi [2]=1\to \pi [0]=0$.

Why $p=m-\pi [m-1]$ is the minimal period. A period $p$ means $S[k]=S[k+p]$ for all valid $k$; equivalently, $S$ has a border of length $m-p$ (the overlapping prefix/suffix). Larger border $\iff$ smaller period. The largest border has length $\pi [m-1]$, which therefore corresponds to the smallest period $p=m-\pi [m-1]$. Any smaller period would force a longer border than $\pi [m-1]$, contradicting maximality. Hence $p$ is minimal.

Apply to abcabca ($m=7$). Its longest border is abca (length $4$): the prefix abca equals the suffix abca. So $\pi [6]=4$ and $p=m-\pi [m-1]=7-4=3(\text{period }\text{abc}).$ Is $p\mid m$? $7=3\cdot 2+1$, remainder $1\ne 0$, so no — it is abc abc a, one and two-thirds copies of abc.

Minimum characters to append. Appending characters does not change the period we are aiming for ($p=3$, block abc); we just need the total length to be the next multiple of $3$ that is $\ge m=7$. Multiples of $3$: $3,6,9,\dots$; the smallest one $\ge 7$ is $9$. So we append $9-7=2\text{ characters},$ namely the next two characters of the block abc after position ...a, which are b then c, giving abcabca + bc = abcabcabc = abc $\times 3$.

Answer: minimal period $p=3$; append $2$ characters (bc) to reach the length-9 full repetition abcabcabc.