The string search algorithm is used to find occurrences of a specific pattern (substring) within a larger text (string). This algorithm plays a crucial role in text processing, searching, and manipulation tasks.
How It Works
- Start with a text (string) and a pattern (substring) to search for.
- Iterate through the text one character at a time.
- For each character in the text, compare it with the first character of the pattern.
- If there is a match, check if the subsequent characters also match the pattern.
- If the pattern is completely matched, record the starting position of the match.
- Continue searching for the pattern in the text.
Example
Consider a text: "ababcababcabcabc" And a pattern: "abc"
- Start at position 0. Compare "a" with the first character "a" in the pattern.
- Match found, move to the next characters: "b" with "b", and "a" with "c".
- Continue matching: "b" with "a", "a" with "b", and "b" with "c".
- Match failed at position 2.
- Start again at position 3. Compare "a" with the first character "a" in the pattern.
- Successful match: "a" with "a", "b" with "b", and "c" with "c".
- Record position 3.
The pattern "abc" is found at positions 0, 6, and 9.
Example Code in C++
In this example, the stringSearch
function is used to find occurrences of the pattern "abc" within the text "ababcababcabcabc". The result will be a vector containing the starting positions of the matches.