String Algorithms

Q1. (3 marks)

• Worst case: $O(nm)$. (1)
• Example: text $=\texttt{"aaaa...a"}$ ($n$ a's), pattern $=\texttt{"aa...ab"}$ ($m-1$ a's then b). (1)
• Why: at each of $\sim n-m+1$ alignments the algorithm matches $m-1$ characters before failing on the last, giving $\Theta((n-m+1)\cdot m)=\Theta(nm)$. (1)

Q2. (5 marks) Pattern $P=\texttt{ababaca}$, indices 0–6.

Array: $\pi = [0,0,1,2,3,0,1]$. (1 mark per correct value cluster; award 5 for full array, deduct 1 per wrong entry) Why: $\pi[i]$ = length of longest proper prefix of $P[0..i]$ that is also a suffix. E.g. at $i=4$ (ababa), aba (len 3) matches; at $i=5$ (ababac), c breaks all borders → 0.

Q3. (4 marks)

• KMP never moves the text pointer backward. (1)
• On a mismatch, the failure function tells us the largest prefix already matched, so the pattern shifts without re-comparing those characters. (1)
• Each text character is examined a constant amortized number of times; the potential/counter argument bounds comparisons by $O(n)$. (1)
• Failure function precomputation is $O(m)$, so total $O(n+m)$. (1)

Q4. (5 marks) $h' = \big(b\cdot(h - s[i]\cdot b^{m-1}) + s[i+m]\big) \bmod q$

• $h$ = current hash of window $s[i..i+m-1]$. (1)
• $s[i]\cdot b^{m-1}$ = contribution of the leaving (leftmost) character; subtract it. (1)
• multiply by $b$ = shift remaining characters up one power. (1)
• $+\,s[i+m]$ = add the new incoming character. (1)
• all reduced mod prime $q$; $b^{m-1}\bmod q$ precomputed → $O(1)$ update. (1)

Q5. (5 marks) Convention: $Z[0]=0$ (undefined/length by convention); $Z[i]$ = length of longest substring starting at $i$ matching a prefix of $S$. $S=\texttt{aabaab}$.

$Z = [0,1,0,3,1,0]$. (deduct 1 per wrong entry) Why: at $i=3$, aab matches prefix aab fully (length 3). At $i=1$, only a matches prefix a.

Q6. (4 marks)

• Bad character heuristic: on a mismatch, align the pattern so that the last occurrence (in $P$) of the mismatched text character lines up with it; if the character does not occur in $P$, shift the pattern entirely past that position. (2)
• For $P=\texttt{BANANA}$ and mismatch on 'X' (not in $P$): shift so pattern moves past the mismatch — shift by $m=6$ (full pattern length, relative to comparison start). (2)

Q7. (4 marks)

• Aho–Corasick augments the trie with failure links (like KMP's failure function generalized to a trie): a failure link points to the node representing the longest proper suffix of the current string that is also a prefix of some pattern. (2)
• Output links collect all patterns ending at each node. (0.5)
• Search complexity: $O(n + m + z)$ where $z$ = number of matches. (1.5)

Q8. (5 marks) $S=\texttt{banana}$ (indices 0–5). Suffixes: 0:banana, 1:anana, 2:nana, 3:ana, 4:na, 5:a. Sorted lexicographically: a(5), ana(3), anana(1), banana(0), na(4), nana(2). Suffix array = $[5, 3, 1, 0, 4, 2]$. (2 for correct suffix list, 3 for correct SA)

Q9. (3 marks)

• Purpose: find longest palindromic substring / all palindromic radii in linear time. (1)
• Complexity: $O(n)$. (1)
• Trick: insert a separator (e.g. #) between every character and at the ends, converting the string into odd length so even- and odd-length palindromes are treated uniformly. (1)

Q10. (2 marks)

• (a) Aho–Corasick automaton. (1)
• (b) Manacher's algorithm. (1)

[
  {"claim":"KMP failure function of 'ababaca' is [0,0,1,2,3,0,1]","code":"def pi(P):\n    n=len(P); f=[0]*n; k=0\n    for i in range(1,n):\n        while k>0 and P[i]!=P[k]:\n            k=f[k-1]\n        if P[i]==P[k]:\n            k+=1\n        f[i]=k\n    return f\nresult = pi('ababaca')==[0,0,1,2,3,0,1]"},
  {"claim":"Z-array of 'aabaab' is [0,1,0,3,1,0] (Z[0]=0 convention)","code":"def zarr(s):\n    n=len(s); Z=[0]*n; l=r=0\n    for i in range(1,n):\n        if i<r: Z[i]=min(r-i,Z[i-l])\n        while i+Z[i]<n and s[Z[i]]==s[i+Z[i]]:\n            Z[i]+=1\n        if i+Z[i]>r: l,r=i,i+Z[i]\n    return Z\nresult = zarr('aabaab')==[0,1,0,3,1,0]"},
  {"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":"Rabin-Karp rolling hash update matches recomputation","code":"b=256; q=1000000007; s=[ord(c) for c in 'abcde']; m=3\nh=0\nfor k in range(m): h=(h*b+s[k])%q\nbm1=pow(b,m-1,q)\nhnext=(b*((h - s[0]*bm1)%q)+s[m])%q\nrecomp=0\nfor k in range(1,1+m): recomp=(recomp*b+s[k])%q\nresult = hnext%q==recomp%q"}
]