String Algorithms

Question 1 — KMP Failure Function (12)

(a) $\pi[i]$ = length of the longest proper prefix of $P[0\ldots i]$ that is also a suffix of $P[0\ldots i]$. "Proper" means it is not the whole substring itself. (2)

(b) $P = a\,b\,a\,b\,a\,b\,c\,a$

• $\pi[0]=0$ (always). $\pi[1]$: ab no match → 0.
• $\pi[2]$ aba → prefix a=suffix a → 1.
• $\pi[3]$ abab → ab=2. $\pi[4]$ ababa=3. $\pi[5]$ ababab=4.
• $\pi[6]$ abababc: c breaks all borders → 0.
• $\pi[7]$ abababca: a matches prefix a → 1.

Award 4 (½ each correct entry, rounded up; deduct 1 per error).

(c) Pseudocode (4):

build_pi(P):
    m = len(P)
    pi = array(m); pi[0] = 0
    k = 0
    for i = 1 to m-1:
        while k > 0 and P[i] != P[k]:
            k = pi[k-1]
        if P[i] == P[k]:
            k = k + 1
        pi[i] = k
    return pi

2 marks structure/loop, 1 for correct fallback k = pi[k-1], 1 for correct increment/assignment.

(d) Amortised: k increases by at most 1 per iteration of the outer for (total increase $\le m$). Each while iteration strictly decreases k by at least 1. Since k never goes below 0, total decreases $\le$ total increases $\le m$. Hence total inner-loop work across all $i$ is $O(m)$. (2)

Question 2 — Z-Algorithm (10)

(a) $Z[i]$ = length of the longest substring starting at position $i$ that matches a prefix of $S$ (i.e. longest $k$ such that $S[0\ldots k-1] = S[i\ldots i+k-1]$). $Z[0]$ is conventionally $0$ (or $n$). (2)

(b) $S = a\,a\,b\,a\,a\,b\,a\,a$

Checks: $Z[3]$: aabaa matches prefix aabaa (5 chars, runs to end) → 5. $Z[6]$: aa = prefix aa → 2. $Z[7]$: a → 1. (4) (½ each)

(c) The Z-box $[L,R]$ is the interval of the rightmost match of a prefix found so far (position with largest $i+Z[i]-1$). When computing $Z[i]$ with $i \le R$, let $k = i - L$ (mirror index). (4)

• Case 1: $Z[k] < R - i + 1$ → the mirror value fits entirely inside the box, so $Z[i] = Z[k]$ (no comparisons needed).
• Case 2: $Z[k] \ge R - i + 1$ → the box might extend further; set $Z[i] = R-i+1$ and continue explicit comparisons past $R$, updating $[L,R]$.

Question 3 — Rabin-Karp (12)

(a) Update formula (4): $h_{i+1} = \big( (h_i - S[i]\cdot b^{m-1})\cdot b + S[i+m] \big) \bmod q$

• $h_i$ = hash of window starting at $i$,
• $b$ = base, $q$ = prime modulus,
• $b^{m-1}$ = precomputed high-order weight (remove leaving char),
• multiply by $b$ shifts left, add incoming char $S[i+m]$. Take mod $q$; add $q$ if negative.

(b) $b=10, q=13, m=3$. (5)

First window 314: value $= 314$. $314 \bmod 13$: $13\times24 = 312$, remainder $2$. So $h_0 = 2$.

Roll to 141: remove leading 3. $b^{m-1}=10^2=100$, $100 \bmod 13 = 9$ (since $13\times7=91$). $h_1 = \big((h_0 - 3\cdot 9)\cdot 10 + 1\big) \bmod 13 = ((2 - 27)\cdot 10 + 1)\bmod 13.$ $2-27 = -25 \equiv -25 + 26 = 1 \pmod{13}$. Then $(1\cdot 10 + 1)=11$; $11 \bmod 13 = 11$.

Direct: 141 $\bmod 13$: $13\times10=130$, remainder $11$. ✓ Match. $h_1 = 11$.

(3 for correct roll arithmetic, 2 for direct check matching.)

(c) Expected $O(n+m)$: hashes match rarely, so full character verification (needed to confirm/reject collisions) happens $O(1)$ expected times with a good random prime. Worst case $O(nm)$ when hashes collide constantly (adversarial input or unlucky $q$), forcing verification every window. Mitigation: use a large random prime modulus (and/or double hashing) to make collisions vanishingly unlikely. (3)

Question 4 — Boyer-Moore (10)

(a) On a mismatch at pattern index $j$ (text char $c$), the bad-character rule aligns the mismatched text char $c$ with its last occurrence in the pattern to the left of $j$: shift $= j - \text{last}[c]$. If $c$ does not occur (or last occurrence is at/after $j$), the shift can be $\le 0$; this is unsafe, so BM takes $\max(1, \text{shift})$ (or combines with good-suffix) to guarantee progress. (4)

(b) $P = n\,e\,e\,d\,l\,e$, last-occurrence table (3):

(All other characters → $-1$, meaning shift past.) e last at index 5, d at 3, l at 4, n at 0.

(c) Good-suffix: after matching a suffix $t$ of the pattern before a mismatch, shift so the next occurrence of $t$ (or the longest prefix of $P$ that is a suffix of $t$) aligns. Taking $\max$ of both heuristics is safe because each individually gives a shift that never skips a possible match, so the larger is still valid and skips more. (3)

Question 5 — Manacher (8)

(a) Finds the longest palindromic substring (and all palindrome radii) in $O(n)$ time. (2)

(b) Insert a separator like # between every character and at the ends: abaaba → #a#b#a#a#b#a#. Every palindrome in the transformed string is centred on a single position, so even-length and odd-length palindromes in the original are both represented as odd-length palindromes here — the algorithm only needs to handle one case (centre + radius). (3)

(c) $S=$abaaba. Longest palindromic substring is the whole string abaaba (length 6) — it reads the same forwards/backwards: a-b-a | a-b-a reversed = abaaba. ✓ (3)

Question 6 — Suffix Array & LCP (8)

(a) Suffixes of banana (4):

Sorted lexicographically:

a       (5)
ana     (3)
anana   (1)
banana  (0)
na      (4)
nana    (2)

Suffix array = [5, 3, 1, 0, 4, 2].

(b) LCP array (LCP between consecutive sorted suffixes; first entry 0) (2):

• a vs ana → 1
• ana vs anana → 3
• anana vs banana → 0
• banana vs na → 0
• na vs nana → 2

LCP = [0, 1, 3, 0, 0, 2] (leading 0 convention).

(c) Prefix-doubling (sort by rank pairs over $\log n$ rounds, each sort $O(n\log n)$ or $O(n)$ radix) gives $O(n\log n)$ (or $O(n\log^2 n)$ naïve). LCP array uses: number of distinct substrings, longest repeated substring, or $O(1)$ longest-common-extension queries. (2)

[
  {"claim":"KMP pi for ababab ca is [0,0,1,2,3,4,0,1]","code":"P='abababca'\ndef pi_f(P):\n    m=len(P); pi=[0]*m; k=0\n    for i in range(1,m):\n        while k>0 and P[i]!=P[k]: k=pi[k-1]\n        if P[i]==P[k]: k+=1\n        pi[i]=k\n    return pi\nresult = pi_f(P)==[0,0,1,2,3,4,0,1]"},
  {"claim":"Rabin-Karp roll: hash(314)%13=2, hash(141)%13=11 and roll matches","code":"b,q=10,13\nh0=314%q\nhigh=(b**2)%q\nh1=(((h0-3*high)*b+1)%q)%q\ndirect=141%q\nresult = (h0==2) and (h1==direct) and (direct==11)"},
  {"claim":"Suffix array of banana is [5,3,1,0,4,2]","code":"S='banana'\nsa=sorted(range(len(S)), key=lambda i:S[i:])\nresult = sa==[5,3,1,0,4,2]"},
  {"claim":"Longest palindromic substring of abaaba has length 6","code":"S='abaaba'\nbest=0\nfor i in range(len(S)):\n    for j in range(i,len(S)):\n        sub=S[i:j+1]\n        if sub==sub[::-1]: best=max(best,len(sub))\nresult = best==6"}
]