Write the simplest search there is, before making it faster.
What to build
A naive string search that reports where a pattern first appears.
Requirements
- Compare the characters yourself, without library search functions.
- Stop at the first position where the whole pattern matches.
- Print -1 if the pattern does not appear.
Input
Two lines: the text, then the pattern. Each is a word with no spaces.
Output
The first position of the pattern, counting from 0, or -1.
Constraints
The text and the pattern each have 1 to 200 letters.
Example
Input:
abracadabra
cad
Output:
4
Why it works
Every place the pattern could start is tried, so a match cannot be missed. In the worst case, each of about n positions needs up to m comparisons, which is O(n · m).
Examples
Example 1 · Input
abracadabra cad
Expected output
4
Example 2 · Input
aaaa b
Expected output
-1
Hints
Hint 1
Try each starting position in the text, from left to right.
Hint 2
At each one, compare letter by letter, and stop at the first difference.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
int main(void) {
char text[201], pat[201];
scanf("%200s %200s", text, pat);
int n = strlen(text), m = strlen(pat), answer = -1;
for (int s = 0; s + m <= n && answer == -1; s++) {
int j = 0;
while (j < m && text[s + j] == pat[j]) j++;
if (j == m) answer = s;
}
printf("%d\n", answer);
return 0;
}