Moderate Strings Question 78 of 224

How do you find the first occurrence of a needle string inside a haystack?

DSA interview set · Speak this in 60–90 seconds · Faridabad & Delhi NCR

StackLIFOlast in, first out

QueueFIFOfirst in, first out

Naive sliding comparison is O((n-m+1)*m).

Why interviewers care about Strings:

This is a process

question about Strings.

Panels listen for order,

trade-offs, and what you would actually do on a DSA project - not buzzwords.

Stay structured

Name the idea, why it exists, then one short example.

Close cleanly

End with when you use it and one common pitfall.

Before you speak the answer, walk the interviewer through these steps:

1
Define it
Naive sliding comparison is O((n-m+1)*m).
2
KMP builds an LPS
table in O(m) and searches in O(n), total O(n+m) time and O(m) space.
3
In an interview, explain
naive first, then KMP or Boyer-Moore if they ask to beat quadratic.
4
Give an example
One tiny concrete case you can say aloud.
5
Common mistake
What juniors usually get wrong.
6
Close
When you pick this over the alternative.

Here's a short line you can speak, broken into clear beats:

Say this line

“KMP builds an LPS table in O(m) and searches in O(n), total O(n+m) time and O(m)”

Break into beats

KMPbuildsanLPStablein

Speaking order

2987408337471632900

Note: Adapt this scaffold to your own project — keep it under 60–90 seconds.

Naive sliding comparison is O((n-m+1)*m). KMP builds an LPS table in O(m) and searches in O(n), total O(n+m) time and O(m) space.