Implement strStr (Pattern Index)

Implement strStr asks you to do something every search box does: find where one string appears inside another. It is the gentlest possible introduction to string matching, and the naive solution teaches the "slide a window and compare" move you will reuse for KMP, Rabin-Karp, and more.

The slow way first

There is no clever trick hiding here at first — the most direct idea already works. Try every possible start position in the text. For a start index i, compare the pattern character by character against text[i], text[i+1], and so on. If all of them match, you found it; if any mismatches, give up on this start and try i + 1.

The only cost is that comparing can fail late. A start can match many characters and then mismatch on the very last one, so you redo work the next window. That makes the naive method O(n · m) in the worst case — but it is simple, correct, and exactly what an interviewer wants you to write before optimizing.

The idea: slide the pattern and compare

Picture the pattern printed on a strip of paper that you slide left to right under the text. At each position, walk a second pointer j across the pattern:

• While text[i + j] == pattern[j], advance j.
• If j reaches the length of the pattern, every character lined up — return i.
• The moment a character disagrees, stop, slide the strip one step right, and reset j to 0.

The two indices have clear jobs: i chooses where the window begins, and j measures how far into the pattern we have matched so far.

Walk through it

Step through the animation. The pattern row slides under the text row. Green cells are characters that matched; the highlighted pair is the comparison happening right now. Watch start i = 2 match two characters and then fail on the last one — that near-miss is exactly the wasted work KMP later avoids. When i reaches 5, all three characters of aab line up, j runs off the end, and we return 5.

Pseudocode

n = length of text, m = length of pattern
for each start i from 0 to n - m:
    j = 0
    while j < m and text[i + j] == pattern[j]:
        j = j + 1                 # this character matched, look at the next
    if j == m:
        return i                  # the whole pattern fit here
return -1                          # never matched anywhere

The Python solution

def str_str(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i
    return -1

• n - m + 1 is the number of valid start positions — past that, the pattern would hang off the end of the text.
• j resets to 0 for every new start; it counts how many characters have matched in the current window.
• The while keeps comparing only while characters agree; j < m stops us from reading past the pattern.
• If the loop ends with j == m, every character matched, so the pattern begins at i — return it.
• If no start ever produces j == m, we fall out of the for and return -1.

Complexity

The naive scan uses O(1) extra space — just two indices. Its weakness is the repeated work after a long partial match. KMP fixes that by precomputing a failure table so that after a mismatch it never re-checks characters it already knows agree, giving a linear O(n + m) total. For interviews, write the naive version first and mention KMP as the optimization.

When this pattern shows up

Practice