DSA interview question

KMP Algorithm (Pattern Matching using LPS Array)

Hard · Algorithms · Topics: string, pattern matching, lps

The problem

You're building the "find in file" feature for a code editor (think Ctrl+F / Ctrl+Shift+F in VS Code), but the files being searched are massive log files (gigabytes) and the same search is run repeatedly. Naive substring search is too slow for the SLAs your team has committed to. Your task: given a text and a pattern, find all starting indices in text where pattern occurs, in O(n + m) time using the KMP algorithm.

Example: text = "ABABDABACDABABCABAB", pattern = "ABABCABAB" → pattern occurs at index 10.

Function signature

vector<int> kmpSearch(string text, string pattern);

Test cases

`text`	`pattern`	Output (indices)	Explanation
`"ABABDABACDABABCABAB"`	`"ABABCABAB"`	`[10]`	Single occurrence starting at index 10
`"AAAAA"`	`"AA"`	`[0,1,2,3]`	Overlapping occurrences allowed
`"ABCABCABC"`	`"ABC"`	`[0,3,6]`	Multiple non-overlapping occurrences
`"ABCDEF"`	`"XYZ"`	`[]`	No occurrence found
`"AAAA"`	`"AAAAA"`	`[]`	Pattern longer than text
`""`	`"A"`	`[]`	Empty text
`"A"`	`""`	edge case	Empty pattern — clarify expected behavior with interviewer

How interviewers phrase it

"Implement an efficient substring search algorithm — given a text and a pattern, return all indices where the pattern occurs."
"Can you find all occurrences of a pattern in a text in linear time?"
Sometimes phrased indirectly without naming KMP at all, to see if you independently arrive at it instead of just reciting memorized code — be ready to justify why naive search is insufficient before jumping to the algorithm name.

Clarifying questions to ask

Can occurrences overlap (e.g., pattern "AA" in text "AAAA" — does it count at indices 0,1,2)? (Yes, typically — confirm.)
Should I return indices (0-indexed) or count of occurrences, or both?
What are the size constraints on text and pattern? (If very large — like 10⁶+ — this strongly signals the interviewer wants O(n+m), ruling out brute force O(n*m).)
Is the pattern guaranteed non-empty? What should happen with empty text or empty pattern?
Case sensitivity / character set assumptions (ASCII only, Unicode, etc.)?

Follow-ups to expect

"Why not just use brute force / std::string::find in a loop?"
"Walk me through why KMP never backtracks in the text pointer."
"Can you do this with the Z-algorithm instead?"
"Can you do this with Rabin-Karp instead? What are the tradeoffs?"
"What if you need to search for multiple patterns simultaneously?"
"Can you find the LPS array's relationship to 'Longest Happy Prefix'?"
"Trace through the algorithm step by step for a specific tricky text/pattern pair"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview