String Algorithms

Question 1

(a) For $P=\texttt{ababcababa}$:

Reasoning at $i=9$: longest border of ababcababa. Prefix aba = suffix aba (length 3). Length 4 abab ≠ suffix baba, so $\pi[9]=3$. (4 marks: −1 per error, max 4.)

(b) Pseudocode $O(m)$:

build_pi(P, 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

(4 marks: correct while-fallback 2, increment/assign 2.)

(c) Claim: the borders of a string $w = P[0..i-1]$ are exactly the prefixes of lengths in the sequence $k_0 = \pi[i-1],\ k_1 = \pi[k_0-1],\ k_2 = \pi[k_1-1],\dots$ terminating at $0$.

Proof. A border of $w$ of length $b$ is a proper prefix equal to a suffix. The longest border has length $\pi[i-1]=k_0$. Suppose $b$ is any border with $0<b<k_0$. Since the length-$k_0$ border $u = P[0..k_0-1]$ is both a prefix and suffix of $w$, and $b<k_0$, the length-$b$ border of $w$ (being a suffix of $w$ of length $<k_0$) is a suffix of $u$; and being a prefix of $w$ it is a prefix of $u$. Hence any border of $w$ shorter than $k_0$ is precisely a border of $u = P[0..k_0-1]$. The longest border of $u$ has length $\pi[k_0-1]=k_1$. By induction the full set of border lengths is $\{k_0,k_1,\dots\}$ enumerated by repeatedly applying $\pi[\cdot-1]$ until reaching $0$. This is a strictly decreasing chain (each $\pi[k-1]<k$), so it terminates and lists every border exactly once. ∎ (6 marks: prefix∩suffix argument 3, inductive nesting of borders 2, termination/decreasing 1.)

(d) Potential argument. Let $\Phi = k$ (the current matched length variable). Initially $\Phi=0$; always $\Phi\ge0$.

• Each iteration of the outer for (m−1 iterations) increases $k$ by at most $1$ (the single if increment). So total increase of $\Phi$ over the whole algorithm is $\le m-1$.
• Each execution of the inner while body sets $k=\pi[k-1]<k$, strictly decreasing $\Phi$ by at least $1$.

Since $\Phi$ starts at $0$, ends $\ge0$, and total increase is $\le m-1$, the total decrease is also $\le m-1$. Therefore the inner while body executes at most $m-1$ times in total across all outer iterations. Outer loop is $O(m)$; total work $O(m)+O(m)=O(m)$. ∎ (6 marks: potential defined 2, increase bounded 2, decrease = while-count bounded → O(m) 2.)

(e) All border lengths of the whole string $P$ (length $m$): start with $\ell_0=\pi[m-1]$, then $\ell_{j+1}=\pi[\ell_j-1]$, continuing while $\ell_j>0$. Each such $\ell$ is a length where a prefix equals a suffix of $P$. Justification: identical to (c) applied to $w=P$ (the whole string), i.e. $i-1=m-1$. (4 marks.)

Question 2

(a) Removing leading digit and appending trailing digit:

Precompute the constant $D_{high} = d^{\,m-1} \bmod q$. All operations mod $q$; $O(1)$ per shift. (4 marks: subtract top 2, multiply+add new 1, precomputed constant named 1.)

(b) If two distinct length-$m$ strings $A,B$ have equal hash, then $q \mid (val(A)-val(B))=D$ with $D\ne0$ and $|D|<d^{\,m}$ (each is in $[0, d^m-1]$). An integer $D$ with $|D|<d^m$ has at most $\log_2|D| < \log_2 d^{\,m} = m\log_2 d$ prime divisors (each prime factor is $\ge 2$, and the product of $t$ primes $\ge 2^t$; so $2^t \le |D| < d^m \Rightarrow t < m\log_2 d$). If $q$ is uniform among the $\pi(N)$ primes $\le N$, the probability $q$ is one of these $\le m\log_2 d$ bad primes is

(6 marks: define D nonzero bounded 2, prime-divisor count via $2^t\le|D|$ 2, probability ratio 2.)

(c) There are $\le n$ candidate windows; each non-matching window collides with probability $\le \frac{m\log_2 d}{\pi(N)}$. By union bound (linearity of expectation),

By the prime number theorem $\pi(N)\sim N/\ln N$. Choosing $N = \Theta(nm)$ gives $\pi(N)=\Theta(nm/\log(nm))$, so

and choosing $N=\Theta(n m^2\log d)$ (or any $N$ with $\pi(N)\gg nm\log d$) forces the expected count to $O(1)$. Each true match verification costs $O(m)$, but expected number of verifications (true + spurious) is $O(\text{occ}+1)$, so total expected time is $O(n+m)$ (hashing) plus $O(m)$ per genuine occurrence. ∎ (6 marks: union bound 2, PNT & choice of N 2, conclusion O(n+m) 2.)

(d) Naive worst case: $T=\texttt{aaaa...a}$ ($n$ a's), $P=\texttt{aaa...ab}$ (length $m$, all a's then a b). At every one of the $n-m+1$ shifts the naive matcher compares $m-1$ matching a's before failing on the b → $\Theta(nm)$. Rabin–Karp worst case is still $\Theta(nm)$ because an adversary knowing $q$ can craft inputs where every window's hash collides with the pattern hash, forcing $O(m)$ verification at each of $n$ positions. (4 marks: example 2, RK worst-case reason 2.)

Question 3

(a) Invariant: maintain the rightmost-reaching palindrome with center $c$ and right boundary $r$ (radius $p[c]$ so $r=c+p[c]$). For $i<r$, let its mirror be $i' = 2c-i$. Because $S[c-t]=S[c+t]$ for all $t\le p[c]$ (palindrome symmetry about $c$), the substring around $i$ mirrors that around $i'$ as long as it stays inside $[c-p[c],\,c+p[c]]$. Hence $p[i]\ge \min(r-i,\ p[i'])$: we can copy the mirror's radius $p[i']$, but not beyond the current right boundary (only $r-i$ characters to the right are guaranteed symmetric). Beyond $r$ we must expand explicitly.

Physical interpretation: the map $x\mapsto 2c-x$ is exactly a reflection (parity) about the point $c$ on the real line — the same reflection symmetry as a mirror at position $c$. $i$ and $i'=2c-i$ are equidistant from $c$ on opposite sides; the palindrome property is invariance of $S$ under this reflection within radius $p[c]$. (6 marks: invariant + copy bound 3, reflection map $2c-i$ as parity/mirror 3.)

(b) $S=\texttt{abaaba}$. Transformed $T = \texttt{\#a\#b\#a\#a\#b\#a\#}$ (length 13, indices 0–12).

$p$-array (radii on transformed string):

Max $p=6$ at index 6 (the center # between the two middle a's) → longest palindrome length $=6$: substring abaaba (the whole string). (6 marks: transformed string 1, p-array correct 3, longest palindrome + length 2.)

(c) Build W = P\T$with$$\notin P,T$,$|P|=k$. For position$j$in$T$, its index in$W$is$k+1+j$.$Z[k+1+j]$= length of longest prefix of$W$(which is$P$...$) matching the substring starting at$k+1+j$. Since$$$appears only once (at index$k$), the match can never cross the$$$boundary, so$Z$value$\le k$. If$Z[k+1+j]=k$, then$W[k+1+j \ldots k+1+j+k-1] = W[0\ldots k-1] = P$, i.e.$T[j\ldots j+k-1]=P$: an exact occurrence. Conversely an occurrence gives a length-$k$prefix match, and it cannot exceed$k$because the$(k{+}1)$-th prefix character is$$$which is absent in$T$. Hence occurrences$\iff Z[k+1+j]=k$. ∎ (4 marks: separator blocks overflow 2, iff 2.)

[
  {"claim":"pi array for ababcababa is [0,0,1,2,0,1,2,3,4,3]",
   "code":"P='ababcababa'\nm=len(P)\npi=[0]*m\nk=0\nfor i in range(1,m):\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,2,0,1,2,3,4,3])"},
  {"claim":"Rabin-Karp rolling update matches direct hash on random data (mod q, base d)",
   "code":"import random\nrandom.seed(