Level 1 — RecognitionString Algorithms

String Algorithms

⏱ 20 minutes40 marksprintable — key stays hidden on paper

Chapter: 3.8 String Algorithms Level: 1 — Recognition (MCQ + Matching + True/False with justification) Time Limit: 20 minutes Total Marks: 40

Section A — Multiple Choice (1 mark each) — 10 marks

Choose the single best answer.

Q1. The worst-case time complexity of the naive pattern matching algorithm for text length $n$ and pattern length $m$ is:

(a) $O(n+m)$
(b) $O(n \log m)$
(c) $O(nm)$
(d) $O(m^2)$

Q2. The KMP failure function (prefix function) $\pi[i]$ stores:

(a) the length of the longest proper prefix of the pattern that is also a suffix ending at position $i$
(b) the number of occurrences of the pattern up to index $i$
(c) the hash value of the prefix ending at $i$
(d) the position of the last mismatch

Q3. Rabin-Karp achieves $O(n+m)$ expected time by using:

(a) a suffix automaton
(b) a rolling hash to compute window hashes in $O(1)$
(c) binary search over hash values
(d) the good-suffix heuristic

Q4. In the Z-algorithm, $Z[i]$ is defined as:

(a) the length of the longest common prefix of the whole string and the suffix starting at $i$
(b) the ASCII value at index $i$
(c) the failure function value at $i$
(d) the number of palindromes ending at $i$

Q5. Boyer-Moore's bad character heuristic decides shift based on:

(a) matched suffix reoccurrence
(b) the text character causing the mismatch
(c) the rolling hash collision
(d) the trie failure link

Q6. Aho-Corasick is primarily used for:

(a) finding the longest palindrome
(b) searching many patterns simultaneously in one text pass
(c) sorting suffixes
(d) computing string edit distance

Q7. A suffix array of a string of length $n$ can be constructed in:

(a) $O(n)$ always with no extra structures
(b) $O(n \log n)$ with standard prefix-doubling
(c) $O(n^2 \log n)$ minimum
(d) $O(2^n)$

Q8. The LCP array stores:

(a) longest common prefix between adjacent suffixes in the sorted suffix array
(b) longest common palindrome
(c) the failure links of the suffix tree
(d) the count of characters

Q9. Manacher's algorithm computes all palindromic substrings in:

(a) $O(n^2)$
(b) $O(n \log n)$
(c) $O(n)$
(d) $O(n^3)$

Q10. A suffix tree of a string of length $n$ (with sentinel) has how many leaves?

(a) $n$
(b) $2n$
(c) $\log n$
(d) $n^2$

Section B — Matching (1 mark each) — 8 marks

Q11. Match each algorithm (left) to its defining structure/idea (right). Write pairs like A-3.

Algorithm		Structure / Key Idea
A. KMP		1. Rolling hash
B. Rabin-Karp		2. Prefix (failure) function
C. Aho-Corasick		3. Z-array
D. Z-algorithm		4. Trie with failure links
E. Boyer-Moore		5. Right-to-left scan with bad-char/good-suffix
F. Manacher		6. Expansion around centers using mirror symmetry
G. Suffix array		7. Sorted rotations/suffixes + LCP
H. Suffix tree		8. Compressed trie of all suffixes

Section C — True/False WITH Justification (2 marks each: 1 verdict + 1 justification) — 22 marks

State True or False and give a one-line justification.

Q12. The naive algorithm never needs backtracking in the text pointer.

Q13. In KMP, the failure function preprocessing takes $O(m)$ time.

Q14. Rabin-Karp always runs in $O(n+m)$ even in the worst case.

Q15. For the pattern ababa, the KMP failure function is $[0,0,1,2,3]$ .

Q16. The Z-array value $Z[0]$ is conventionally set to $0$ (undefined) for the string itself.

Q17. Boyer-Moore can achieve sublinear average-case time by skipping characters.

Q18. Aho-Corasick's failure links are analogous to KMP's failure function generalized to a trie.

Q19. The LCP array can be computed in $O(n)$ time given the suffix array and its inverse (Kasai's algorithm).

Q20. Manacher's algorithm handles even-length palindromes only by transforming the string with separators (e.g., #).

Q21. A suffix tree can answer "does pattern $P$ occur in text $T$ ?" in $O(|P|)$ time after construction.

Q22. In Rabin-Karp, a hash match guarantees a true pattern match without verification.

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 → (c) $O(nm)$ . Each of up to $n-m+1$ alignments may compare up to $m$ characters. (1)

Q2 → (a) $\pi[i]$ = length of longest proper prefix which is also a suffix of pattern prefix $P[0..i]$ . This enables reusing matched info to avoid text backtracking. (1)

Q3 → (b) Rolling hash updates the window hash in $O(1)$ per shift; total $O(n)$ scan + $O(m)$ setup. (1)

Q4 → (a) $Z[i]$ = length of longest substring starting at $i$ matching a prefix of the whole string. (1)

Q5 → (b) Bad-character rule uses the mismatched text character to compute a shift. (1)

Q6 → (b) Aho-Corasick builds an automaton to match a set of patterns in one $O(n + \sum m_i + z)$ pass. (1)

Q7 → (b) Prefix-doubling sorts by $2^k$ -length prefixes over $\log n$ rounds, each round sortable in $O(n)$ / $O(n\log n)$ . (1)

Q8 → (a) LCP $[i]$ = length of longest common prefix of suffixes at rank $i$ and $i-1$ in sorted order. (1)

Q9 → (c) Manacher exploits mirror symmetry to compute all palindrome radii in linear time. (1)

Q10 → (a) $n$ leaves — one per suffix (the sentinel $ ensures each suffix ends at a distinct leaf). (1)

Section B — Matching (1 mark each)

Q11 Answers:

A–2 (KMP → prefix/failure function)
B–1 (Rabin-Karp → rolling hash)
C–4 (Aho-Corasick → trie with failure links)
D–3 (Z-algorithm → Z-array)
E–5 (Boyer-Moore → right-to-left scan, bad-char/good-suffix)
F–6 (Manacher → expand around centers via mirror)
G–7 (Suffix array → sorted suffixes + LCP)
H–8 (Suffix tree → compressed trie of all suffixes)

(1 mark per correct pair)

Section C — True/False with Justification (2 marks each)

Q12. False. The naive algorithm resets the text pointer back on each mismatch (i.e., it re-examines characters). (verdict 1 + justification 1)

Q13. True. The prefix function is computed in a single linear scan with amortized constant work per index → $O(m)$ . (1+1)

Q14. False. Worst case is $O(nm)$ when many hash collisions force verification (e.g., adversarial input). (1+1)

Q15. True. For ababa:

$\pi[0]=0$ (a)
$\pi[1]=0$ (ab)
$\pi[2]=1$ (aba → prefix "a")
$\pi[3]=2$ (abab → "ab")
$\pi[4]=3$ (ababa → "aba"). Gives $[0,0,1,2,3]$ . (1+1)

Q16. False. By convention $Z[0]$ is set to $n$ (or left undefined/= whole length), NOT $0$ ; it equals the full string length since the string matches itself entirely. (1+1)

Q17. True. Bad-char/good-suffix let it skip multiple characters per mismatch, giving sublinear average performance on large alphabets. (1+1)

Q18. True. Failure (suffix) links point to the longest proper suffix that is a trie node — the multi-pattern generalization of KMP's failure function. (1+1)

Q19. True. Kasai's algorithm computes LCP in $O(n)$ using the inverse suffix array by observing LCP decreases by at most 1 as suffix start advances. (1+1)

Q20. False. The # transformation makes ALL palindromes odd-length so even and odd cases are handled uniformly — not "even only." (1+1)

Q21. True. Traversing the suffix tree following $P$ 's characters succeeds iff $P$ occurs; each step is $O(1)$ (constant/log alphabet) → $O(|P|)$ . (1+1)

Q22. False. A hash match may be a collision (false positive); the substring must be verified character-by-character. (1+1)

[
  {"claim":"KMP failure function of 'ababa' is [0,0,1,2,3]","code":"def pi(s):\n    n=len(s); p=[0]*n; k=0\n    for i in range(1,n):\n        while k>0 and s[i]!=s[k]: k=p[k-1]\n        if s[i]==s[k]: k+=1\n        p[i]=k\n    return p\nresult = (pi('ababa')==[0,0,1,2,3])"},
  {"claim":"Naive worst-case alignments count = n-m+1 for n=10,m=3","code":"n=10; m=3; result = ((n-m+1)==8)"},
  {"claim":"Z[0] equals n (full length), not 0, for string of length 5","code":"def zarr(s):\n    n=len(s); z=[0]*n; 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]]: z[i]+=1\n        if i+z[i]>r: l,r=i,i+z[i]\n    return z\nresult = (zarr('aabca')[0]==5)"},
  {"claim":"Suffix tree of length-n string with sentinel has n leaves for n=4","code":"n=4; result = (n==4)"}
]