Created
May 2, 2016 21:20
-
-
Save biomadeira/b4069225550336bc8c4d90556c7d748f to your computer and use it in GitHub Desktop.
[Algorithms] Pattern matching in string (from /laurentluce/python-algorithms)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def string_matching_naive(text='', pattern=''): | |
| """Returns positions where pattern is found in text. | |
| We slide the string to match 'pattern' over the text | |
| O((n-m)m) | |
| Example: text = 'ababbababa', pattern = 'aba' | |
| string_matching_naive(t, s) returns [0, 5, 7] | |
| @param text text to search inside | |
| @param pattern string to search for | |
| @return list containing offsets (shifts) where pattern is found inside text | |
| """ | |
| n = len(text) | |
| m = len(pattern) | |
| offsets = [] | |
| for i in range(n-m+1): | |
| if pattern == text[i:i+m]: | |
| offsets.append(i) | |
| return offsets | |
| string_matching_naive(text="ababbababa", pattern="aba") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment