← Quiz: String Matching — KMP and Rabin-Karp: all 10 questions
Quiz: String Matching — KMP and Rabin-Karp · Question 3 of 10
What does this print? (code)
What does this print?
def build_lps(p):
lps, k = [0] * len(p), 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = lps[k - 1]
if p[i] == p[k]:
k += 1
lps[i] = k
return lps
print(build_lps("AABAAA"))
- A.[0, 1, 0, 1, 2, 3]
- B.[0, 1, 0, 1, 2, 2]
- C.[0, 1, 1, 1, 2, 2]
- D.[0, 0, 0, 1, 2, 2]
Answer & explanation
Correct answer: [0, 1, 0, 1, 2, 2]
For "AABAAA" the longest border is "AA" (length 2). "AAB" is not a suffix, so the last value cannot be 3.
Can you get the rest right without peeking?
Take the timed Quiz: String Matching — KMP and Rabin-Karp quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →