15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The naive string matching algorithm slides the pattern across the text one start at a time and compares characters until one differs or the whole pattern matches. It tests every start from 0 to n - m, so it returns the first occurrence. Worst-case time is O(nm) and extra space is O(1).
| Candidate starts | 0 through n - m, so n - m + 1 of them |
|---|---|
| Worst-case time | O(nm), at most (n - m + 1) * m comparisons |
| Extra space | O(1) |
| Empty pattern | Returns 0 |
| Not found | Returns -1; also returned when m > n |
| After a mismatch | Move to s + 1, never skip a start |
Assume you can:
text[2];text[1..3), which includes indexes 1 and 2 but not 3.Search a text for a pattern.
A substring occurrence is identified by its starting index. If a pattern starts at index s, then pattern index 0 is aligned with text index s.
Use the following contract:
-1 if it does not occur.0 when the pattern is empty.For a text of length n and a pattern of length m, a start s is feasible only when the entire pattern fits:
The reference material for terminology and string-search scope is the Algorithms, 4th edition companion site.
Use:
1text = "caba"
2pattern = "ab"Write the text with indexes:
1index: 0 1 2 3
2text: c a b aHere:
1n = 4
2m = 2The pattern has length 2. It can begin at starts 0, 1, and 2.
1start 0: pattern would use text indexes 0 and 1
2start 1: pattern would use text indexes 1 and 2
3start 2: pattern would use text indexes 2 and 3Start 3 is not feasible. A two-character pattern starting there would need text index 4, which does not exist.
Start with the leftmost candidate, s = 0.
Naive search tries each feasible start s = 0, 1, 2 in turn. Start 0 fails on its first pair (c vs a). Start 1 matches both pattern characters, so the search returns 1.
s = 0Align pattern index 0 with text index 0.
Compare corresponding positions:
1text[0] = c
2pattern[0] = aThey differ. Reject this alignment immediately.
Do not compare text[1] with pattern[1]. Exact matching requires every corresponding pair to be equal. One mismatch rejects start 0.
s = 1Move the pattern one text position to the right.
Compare the first pair:
1text[1] = a
2pattern[0] = aThey match.
s = 1Compare the next pair:
1text[2] = b
2pattern[1] = bThey match.
Both pattern characters matched. The occurrence starts at index 1.
1return 1The matched substring is:
1text[1..3) = "ab"While searching from left to right, two facts remain true.
At a candidate start s, suppose j comparisons have succeeded. Then:
1pattern[0..j) equals text[s..s+j)For example, at s = 1 after the first successful comparison:
1pattern[0..1) = "a"
2text[1..2) = "a"Every candidate start before s has already been tested and rejected.
Together, these facts form the loop invariant:
At a candidate start
s, afterjsuccessful comparisons,pattern[0..j)equalstext[s..s+j); no earlier candidate start remains untested when searching left to right.
A mismatch at position j rejects only the current start. The algorithm then tries s + 1. In the example, skipping directly from s = 0 to s = 2 would miss the occurrence beginning at 1.
Handle the length boundaries first.
m = 0, return 0. The empty pattern is defined here to occur first at index 0.m > n, return -1. A nonempty pattern cannot fit in a shorter text.Otherwise, test every feasible start in increasing order:
10, 1, 2, ..., n - mAt each start s:
j to 0.text[s + j] with pattern[j].j.s.j reaches m, every pattern character matched, so return s.Testing starts in increasing order returns the first occurrence.
Inputs: read-only strings text and pattern
Return value: first start index of pattern in text; -1 if absent; 0 if pattern is empty
Mutation behavior: does not modify either input string
Index boundary: candidate starts range from 0 through n - m, inclusive
101 function firstIndexOf(text, pattern) -> integer
202 n <- length(text)
303 m <- length(pattern)
404
505 if m = 0
606 return 0
707
808 if m > n
909 return -1
1010
1111 for s <- 0 to n - m inclusive
1212 j <- 0
1313
1414 while j < m and text[s + j] = pattern[j]
1515 j <- j + 1
1616
1717 if j = m
1818 return s
1919
2020 return -1The condition on line 14 does two jobs:
j < m prevents reading beyond the pattern.text[s + j] = pattern[j] continues only while the current pair matches.When a character mismatch occurs, line 14 becomes false. The loop stops, and the for loop moves to the next candidate start.
Dry-run the same input:
1text = "caba"
2pattern = "ab"1n <- 4
2m <- 21m = 0 ?
22 = 0 ? No.Do not return.
1m > n ?
22 > 4 ? No.Do not return.
1s <- 01j <- 0s = 01j < m -> 0 < 2, true
2text[s + j] -> text[0 + 0] = text[0] = c
3pattern[j] -> pattern[0] = a
4text[s + j] = pattern[j] -> c = a, falseThe full while condition is false. Do not enter line 15.
1j = m ?
20 = 2 ? No.Do not return. The for loop advances.
1s <- 11j <- 0s = 11j < m -> 0 < 2, true
2text[s + j] -> text[1 + 0] = text[1] = a
3pattern[j] -> pattern[0] = a
4text[s + j] = pattern[j] -> a = a, trueEnter the loop.
1j <- 1s = 11j < m -> 1 < 2, true
2text[s + j] -> text[1 + 1] = text[2] = b
3pattern[j] -> pattern[1] = b
4text[s + j] = pattern[j] -> b = b, trueEnter the loop.
1j <- 21j < m ?
22 < 2 ? No.Stop the while loop.
1j = m ?
22 = 2 ? Yes.
3
4return s
5return 1The algorithm returns 1.
We show that firstIndexOf returns the required result.
Before the first candidate is tested, s = 0.
There are no earlier candidate starts, so the statement that no earlier candidate remains untested is true.
At the beginning of an alignment, j = 0. The ranges:
1pattern[0..0)
2text[s..s+0)are both empty. Therefore they are equal. The invariant holds before any comparison.
Assume the invariant holds at candidate start s after j successful comparisons.
If line 14 succeeds, then:
1text[s + j] = pattern[j]The invariant already says the earlier ranges match:
1pattern[0..j) = text[s..s+j)Adding one equal character to each range gives:
1pattern[0..j+1) = text[s..s+j+1)Then line 15 increases j to j + 1, so the invariant still holds.
If line 14 stops because of a mismatch, the current alignment cannot be an exact occurrence. Exact equality requires every corresponding pair to match. The algorithm does not return this s; it moves to the next candidate start. Since starts are tried in increasing order, the rejected s is now also among the tested earlier starts.
There are two ways the algorithm can terminate.
If line 18 returns s, then j = m. By the invariant:
1pattern[0..m) = text[s..s+m)Every pattern character matches the corresponding text character. Thus s is an occurrence.
All smaller feasible starts were tested first and rejected. Therefore s is the first occurrence.
If the loop finishes and line 20 returns -1, every feasible start from 0 through n - m has been tested and rejected. Any occurrence of a pattern of length m must begin at one of those starts. Therefore no occurrence exists.
The early length checks also satisfy the stated boundary contract:
m = 0, return 0.m > n, return -1.Assume first that:
10 <= m <= nThere are:
feasible starts.
At each start, the inner loop performs at most m character comparisons. It may stop sooner at a mismatch, but it cannot compare more than all m pattern characters.
Therefore the total number of character comparisons is at most:
So the worst-case running time is:
For the board example:
1n = 4
2m = 2
3feasible starts = 4 - 2 + 1 = 3
4maximum comparisons = 3 * 2 = 6The actual example returns early after three comparisons:
1at s = 0: one comparison, c versus a
2at s = 1: two comparisons, a versus a and b versus b
3total: three comparisonsAn early match can reduce the actual work. It does not change the worst-case bound.
The algorithm stores lengths and indexes such as n, m, s, and j. It does not build another string or array. Its auxiliary space is:
Incorrect assumption: every text index can be a candidate start.
1for s <- 0 to n - 1 inclusiveInput that exposes it:
1text = "ab"
2pattern = "ab"After testing s = 0, this incorrect loop also tries s = 1.
At that start, comparing the second pattern character requires:
1text[1 + 1] = text[2]But index 2 is outside the text.
Wrong result or state: invalid access when s = 1.
Correction:
1for s <- 0 to n - m inclusiveThe corrected bound tests only starts with enough remaining text characters.
Incorrect assumption: a match of the first character means the pattern matches.
1if text[s] = pattern[0]
2 return sInput that exposes it:
1text = "ac"
2pattern = "ab"At s = 0:
1text[0] = a
2pattern[0] = aThe incorrect code returns 0, even though:
1text[1] = c
2pattern[1] = bdo not match.
Wrong output: 0.
Correction: return only after all m corresponding character comparisons match.
1if j = m
2 return sIncorrect assumption: after a mismatch, skip one possible start.
1after failure at s = 0, continue with s = 2Input that exposes it:
1text = "caba"
2pattern = "ab"Start 0 fails because:
1text[0] = c
2pattern[0] = aIf the algorithm jumps to s = 2, it never tests s = 1, where "ab" occurs.
Wrong output: not found.
Correction: naive first-occurrence search advances to the next candidate:
1s <- s + 1Incorrect assumption: an empty pattern is not found.
1if m = 0
2 return -1Input that exposes it:
1text = "abc"
2pattern = ""Wrong output: -1.
Correction: the explicit contract defines the first empty-pattern occurrence as index 0.
1if m = 0
2 return 0| Text | Pattern | Result | Reason |
|---|---|---|---|
"" | "" | 0 | Empty pattern returns 0. |
"" | "a" | -1 | A nonempty pattern cannot occur in empty text. |
"abc" | "" | 0 | Empty pattern returns 0. |
"ab" | "abc" | -1 | m > n. |
"aaaa" | "aa" | 0 | Starts 0, 1, and 2 are occurrences; return the first. |
"abc" | "d" | -1 | Every feasible alignment mismatches. |
Implement:
1firstIndexOf(text, pattern)Required contract:
-1 when the pattern is absent.0 when the pattern is empty.text or pattern.The tests will include:
1def first_index_of(text, pattern):
2 n = len(text)
3 m = len(pattern)
4 if m == 0:
5 return 0
6 if m > n:
7 return -1
8 for s in range(n - m + 1): # starts 0 .. n - m inclusive
9 j = 0
10 while j < m and text[s + j] == pattern[j]:
11 j += 1
12 if j == m: # every pattern character matched
13 return s
14 return -1
15
16for text, pattern in [("caba", "ab"), ("aaaa", "aa"), ("abc", "d"), ("abc", ""), ("ab", "abc")]:
17 print(text + " | " + pattern + " -> " + str(first_index_of(text, pattern)))1public class Main {
2 static int firstIndexOf(String text, String pattern) {
3 int n = text.length();
4 int m = pattern.length();
5 if (m == 0) return 0;
6 if (m > n) return -1;
7 for (int s = 0; s <= n - m; s++) { // starts 0 .. n - m inclusive
8 int j = 0;
9 while (j < m && text.charAt(s + j) == pattern.charAt(j)) {
10 j++;
11 }
12 if (j == m) return s; // every pattern character matched
13 }
14 return -1;
15 }
16
17 public static void main(String[] args) {
18 String[][] cases = {{"caba", "ab"}, {"aaaa", "aa"}, {"abc", "d"}, {"abc", ""}, {"ab", "abc"}};
19 for (String[] c : cases) {
20 System.out.println(c[0] + " | " + c[1] + " -> " + firstIndexOf(c[0], c[1]));
21 }
22 }
23}1#include <iostream>
2#include <string>
3#include <utility>
4#include <vector>
5using namespace std;
6
7int firstIndexOf(const string& text, const string& pattern) {
8 int n = (int)text.size();
9 int m = (int)pattern.size();
10 if (m == 0) return 0;
11 if (m > n) return -1;
12 for (int s = 0; s <= n - m; s++) { // starts 0 .. n - m inclusive
13 int j = 0;
14 while (j < m && text[s + j] == pattern[j]) {
15 j++;
16 }
17 if (j == m) return s; // every pattern character matched
18 }
19 return -1;
20}
21
22int main() {
23 vector<pair<string, string>> cases = {
24 {"caba", "ab"}, {"aaaa", "aa"}, {"abc", "d"}, {"abc", ""}, {"ab", "abc"}};
25 for (auto& c : cases) {
26 cout << c.first << " | " << c.second << " -> " << firstIndexOf(c.first, c.second) << endl;
27 }
28}1function firstIndexOf(text, pattern) {
2 const n = text.length;
3 const m = pattern.length;
4 if (m === 0) return 0;
5 if (m > n) return -1;
6 for (let s = 0; s <= n - m; s++) { // starts 0 .. n - m inclusive
7 let j = 0;
8 while (j < m && text[s + j] === pattern[j]) {
9 j++;
10 }
11 if (j === m) return s; // every pattern character matched
12 }
13 return -1;
14}
15
16const cases = [['caba', 'ab'], ['aaaa', 'aa'], ['abc', 'd'], ['abc', ''], ['ab', 'abc']];
17for (const [text, pattern] of cases) {
18 console.log(`${text} | ${pattern} -> ${firstIndexOf(text, pattern)}`);
19}Line the pattern up with text index 0 and compare pair by pair. On the first mismatch, shift the pattern one place right and try again. For "caba" and "ab", start 0 fails on c versus a, and start 1 matches both characters, so the answer is 1.
It depends on the input. Naive search is the baseline at O(nm) worst case. KMP guarantees O(n + m), Rabin-Karp compares rolling hashes in expected O(n + m), and Aho-Corasick searches many patterns together.
They find where a pattern occurs in a text. Naive search, KMP, Rabin-Karp, Boyer-Moore and Aho-Corasick are the usual ones. They differ in how much work they reuse after a mismatch.
A pattern of length m starting at s needs text index s + m - 1. Past s = n - m the pattern runs off the end, and the loop would read an index that does not exist. Starting at n - 1 is the common mistake.
Any start you skip might hold a match. In "caba", jumping from start 0 to start 2 misses the match at start 1. The naive version always advances by one.
Zero. The contract defines the first occurrence of an empty pattern as index 0, even for an empty text.