String Algorithms

Question 1 (12)

(a) P = "abacabab", indices 0–7.

Build $\pi[i]$ = length of longest proper prefix that is also suffix of P[0..i].

Reasoning at i=6: prefix "abaca", matching "a","ab","aba" → π=3 (since P[3]... actually compare: previous π[5]=2, P[6]='a', P[2]='a' match → π=3). At i=7: from π=3, P[7]='b', P[3]='c' mismatch, fall back to π[2]=1, P[7]='b', P[1]='b' match → π=2. (6, ~1 per correct entry from i=2 onward)

(b) Borders of full P come from iterating $\pi$ on the last index (7): $\pi[7]=2 \to \pi[1]=0$. So border lengths are 2 and 0 → the only non-empty proper border is "ab" (length 2). (3)

(c) Longest border length = 2, so smallest period $p = n - 2 = 8 - 2 = 6$. Since $6 \nmid 8$, P is not a whole-number repetition of a smaller block; it is not periodic in the "power of a block" sense. (3)

Question 2 (12)

(a) T = "aabxaayaab", indices 0–9.

Checks: $Z[1]$: T[1]='a'=T[0], T[2]='b'≠T[1]? compare prefix: T[0..]="aab", suffix at 1 "abx…" → match length 1. $Z[4]$: "aay…" vs prefix "aab" → "aa" match, then 'y'≠'b' → 2. $Z[7]$: suffix "aab" vs prefix "aab" → full 3. (6)

(b) Concatenate $W = P + \# + X$. Compute $Z$ over $W$. For every position $i$ in the $X$-portion (i.e. $i > |P|$), if $Z[i] \ge |P|$ then $P$ occurs in $X$ starting at index $i - |P| - 1$. The separator # (not in alphabet) guarantees $Z[i]$ can never exceed $|P|$, so $Z[i] = |P|$ signals a full match. (4)

(c) $W =$ aab#xaayaab, $|P|=3$. Positions in X region needing $Z=3$: the suffix "aab" at end matches → occurrence. Index in X: the "aab" starts at X-index 4 (x a a y a a b → positions 4,5,6). So one occurrence at index 4 of X. (2)

Question 3 (12)

(a) P="cab", $v$: c=3,a=1,b=2. $b=31$. $H_P = (3\cdot31^2 + 1\cdot31 + 2) \bmod 101$. $31^2 = 961$. $3\cdot961 = 2883$. $2883+31+2 = 2916$. $2916 \bmod 101$: $101\cdot28=2828$, $2916-2828=88$. $H_P = 88$. (3)

(b) Window "abc": $v$=a1,b2,c3. $H = (1\cdot961 + 2\cdot31 + 3)\bmod101 = (961+62+3)\bmod101 = 1026 \bmod 101$. $101\cdot10=1010$, $1026-1010=16$. So $H_{abc}=16$.

Rolling to "bca": remove leading a1, add trailing a1: $H_{new} = \big((H_{old} - v(c_0)\cdot b^{m-1})\cdot b + v(c_{new})\big)\bmod q.$ $b^{m-1}=b^2=961\equiv 961\bmod101$. $101\cdot9=909$, $961-909=52$. So $961\equiv52$. $H_{new} = ((16 - 1\cdot52)\cdot31 + 1)\bmod101 = ((-36)\cdot31 + 1)\bmod101 = (-1116+1)\bmod101 = -1115 \bmod 101$. $101\cdot11=1111$, $-1115+1212=97$ (add $101\cdot12=1212$): $97$. Verify directly: "bca" = b2,c3,a1 → $2\cdot961+3\cdot31+1 = 1922+93+1=2016$; $2016\bmod101$: $101\cdot19=1919$, $2016-1919=97$. ✓ $H_{bca}=97$. (5)

(c) Pattern hash 88. Compute all length-3 window hashes of T="abcaba":

• "abc"→16
• "bca"→97
• "cab": c3,a1,b2 → $3\cdot961+31+2=2916\to88$ ✓ hash = 88
• "aba": a1,b2,a1 → $961+62+1=1024\bmod101$: $101\cdot10=1010$, →14.

Window "cab" at index 2 has hash 88 = $H_P$. Here the string "cab" actually equals P, so it is a true match, not spurious. Checking all windows, no window has hash 88 with a differing string → no spurious hit occurs for this text. Rabin-Karp always confirms a hash match with a direct character comparison, so any collision would be rejected; here the only hash match is genuine. (4) (Award full marks for correctly finding no spurious hit and stating the verification step.)

Question 4 (12)

(a) S="abacaba" (indices 0–6). Odd-centre palindrome radius (number of characters each side, so palindrome length = 2·radius+1):

(6)

(b) Longest palindromic substring = "abacaba", length 7 (centre index 3). (2)

(c) Before expanding centre $i$ inside $[l,r]$ with mirror $i' = l+r-i$, initialise $P[i] = \min\big(P[i'],\; r - i\big).$ This is valid because the substring $S[l..r]$ is a palindrome, so the neighbourhood of $i$ mirrors that of $i'$ at least up to the boundary $r$; we can safely copy $P[i']$ but must cap it at $r-i$ since beyond $r$ the mirror symmetry is not guaranteed and must be verified by explicit expansion. (4)

Question 5 (12)

(a) (i) KMP per pattern: preprocess each pattern $O(|p_j|)$ and scan text once per pattern $O(n)$ → total $O(kn + M)$. (ii) Aho-Corasick: build automaton $O(M)$ (over fixed alphabet) and single text scan $O(n + \text{occ})$ → total $O(M + n + \text{occ})$. Aho-Corasick is strictly better when $k$ is large (many patterns), since it replaces the $kn$ term by a single $n$ scan. (4)

(b) In the trie for {he, she, his, hers}, the node reached by "she" has a failure link to the node reached by "he" (the longest proper suffix of "she" that is a prefix of some pattern). Because "he" is itself a complete pattern, reaching the "she" node while scanning "ushers" reports both "she" (the node's own pattern) and "he" (via the output link following the failure link). At the position ending "...she" in "ushers", outputs = {she, he}. (4)

(c) Suffixes of S="banana":

0: banana
1: anana
2: nana
3: ana
4: na
5: a
6: (empty, $)

Sorted (with $ smallest): order of starting indices: $(6), a(5), ana(3), anana(1), banana(0), na(4), nana(2).

Suffix array = [6, 5, 3, 1, 0, 4, 2] (or [5,3,1,0,4,2] if $ omitted).

First two adjacent real suffixes in sorted order: a(5) and ana(3). LCP = 1 (common prefix "a"). (4)

[
  {"claim":"KMP pi array for abacabab ends with border length 2","code":"P='abacabab'\npi=[0]*len(P)\nk=0\nfor i in range(1,len(P)):\n    while k>0 and P[i]!=P[k]:\n        k=pi[k-1]\n    if P[i]==P[k]:\n        k+=1\n    pi[i]=k\nresult = (pi==[0,0,1,0,1,2,3,2])"},
  {"claim":"Hash of cab base31 mod101 is 88","code":"v={'a':1,'b':2,'c':3}\nb=31; q=101\nP='cab'\nH=0\nfor c in P:\n    H=(H*b+v[c])%q\nresult = (H==88)"},
  {"claim":"Rolling hash of bca equals 97","code":"v={'a':1,'b':2,'c':3}\nb=31;q=101\ndef h(s):\n    H=0\n    for c in s: H=(H*b+v[c])%q\n    return H\nresult = (h('bca')==97 and h('abc')==16)"},
  {"claim":"Suffix array of banana (no sentinel) is [5,3,1,0,4,2]","code":"S='banana'\nsuf=sorted(range(len(S)), key=lambda i:S[i:])\nresult = (suf==[5,3,1,0,4,2])"},
  {"claim":"Manacher longest palindrome of abacaba has length 7","code":"S='abacaba'\nn=len(S)\nbest=0\nfor c in range(n):\n    r=0\n    while c-r>=0 and c+r<n and S[c-r]==S[c+r]:\n        r+=1\n    best=max(best,2*(r-1)+1)\nresult = (best==7)"}
]