15 | def search(string, word): |
16 | """ |
17 | Searches for occurrences of a "word" within a main "string" by employing |
18 | the observation that when a mismatch occurs, the word itself embodies |
19 | sufficient information to determine where the next match could begin, |
20 | thus bypassing re-examination of previously matched characters. |
21 | |
22 | :param string: The string to be searched. |
23 | :param word: The sub string to be searched for. |
24 | :rtype: The indices of all occurences of where the substring is found in |
25 | the string. |
26 | """ |
27 | word_length = len(word) |
28 | string_length = len(string) |
29 | offsets = [] |
30 | |
31 | if word_length > string_length: |
32 | return offsets |
33 | |
34 | prefix = compute_prefix(word) |
35 | q = 0 |
36 | for index, letter in enumerate(string): |
37 | while q > 0 and word[q] != letter: |
38 | q = prefix[q - 1] |
39 | if word[q] == letter: |
40 | q += 1 |
41 | if q == word_length: |
42 | offsets.append(index - word_length + 1) |
43 | q = prefix[q - 1] |
44 | return offsets |