Knuth-Morris-Pratt (KMP) Algorithm

1. Prefix Function $\pi$ (failure function)

computePi(P[0..m-1]):
  pi[0]=0; k=0
  for q=1..m-1:
    while k>0 and P[k]!=P[q]: k=pi[k-1]
    if P[k]==P[q]: k++
    pi[q]=k

$\pi[q]$ = length of longest proper prefix of $P[0..q]$ which is also suffix.

2. Search

KMP(T[0..n-1], P[0..m-1]):
  pi=computePi(P); q=0
  for i=0..n-1:
    while q>0 and P[q]!=T[i]: q=pi[q-1]
    if P[q]==T[i]: q++
    if q==m: report match at i-m+1; q=pi[q-1]

Time $O(n+m)$, space $O(m)$.

---

Apply to $p=$ "ababaca" (m=7), $s=$ "bacbabababacaab" (n=14-15)

Step A — Compute $\pi$ for $p=$ a b a b a c a

q	0:a	1:b	2:a	3:b	4:a	5:c	6:a
$\pi$	0	0	1	2	3	0	1

Derivation:

• q0 a →0
• q1 b≠a →0
• q2 a==a(0) →1
• q3 b==b(1) →2
• q4 a==a(2) →3
• q5 c vs p[3]=b mismatch → fallback pi[2]=1 → p[1]=b vs c mismatch →0
• q6 a==a →1

Step B — Scan $s=$ b a c b a b a b a b a c a a b
Index i (0-based), $q$ = matched prefix length:

i	T[i]	q before	action	q after	output
0	b	0	P0=a ≠b	0
1	a	0	a==a →1	1
2	c	1	P1=b ≠c →q=pi0=0, a≠c	0
3	b	0	a≠b	0
4	a	0	a==a→1	1
5	b	1	b==b→2	2
6	a	2	a==a→3	3
7	b	3	b==b→4	4
8	a	4	a==a→5	5
9	b	5	P5=c≠b →q=pi4=3, P3=b==b→4	4
10	a	4	a==a→5	5
11	c	5	c==c→6	6
12	a	6	a==a→7	7	Match at i-m+1=6 (1-based 7)
13	a	7→fallback pi6=1	1	P1=b≠a→q=pi0=0, P0=a==a→1	1
14	b	1	b==b→2	2

Result: One occurrence of "ababaca" at position 7 (1-indexed) in $s$ (0-indexed 6), i.e., $s[6..12]=$ "ababaca". No other full match; scan continues to end.

Verification by brute force: substrings of s length 7: bacbaba, ... ababaca at 6-12 matches.

Complexities: preprocessing $O(m)=O(7)$, searching $O(n)=O(14)$, total $O(n+m)$, never re-examines text characters (contrast naive $O(nm)$).