/
NikolayIvkin
/
TheAlgorithms_Python
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms_Python
Код
Запросы
2
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
strings/naive_string_search.py
40 строк
1 KB
Shubham Ganar
[mypy] Fix type annotations for strings/naive_string_search.py (#4611)
13 авг 2021, 10:10
Не верифицирован
13 авг 2021, 10:10
3c22524
Код
Авторство
О чём код?
""" https://en.wikipedia.org/wiki/String-searching_algorithm#Na%C3%AFve_string_search this algorithm tries to find the pattern from every position of the mainString if pattern is found from position i it add it to the answer and does the same for position i+1 Complexity : O(n*m) n=length of main string m=length of pattern string """ def naive_pattern_search(s: str, pattern: str) -> list: """ >>> naive_pattern_search("ABAAABCDBBABCDDEBCABC", "ABC") [4, 10, 18] >>> naive_pattern_search("ABC", "ABAAABCDBBABCDDEBCABC") [] >>> naive_pattern_search("", "ABC") [] >>> naive_pattern_search("TEST", "TEST") [0] >>> naive_pattern_search("ABCDEGFTEST", "TEST") [7] """ pat_len = len(pattern) position = [] for i in range(len(s) - pat_len + 1): match_found = True for j in range(pat_len): if s[i + j] != pattern[j]: match_found = False break if match_found: position.append(i) return position if __name__ == "__main__": assert naive_pattern_search("ABCDEFG", "DE") == [3] print(naive_pattern_search("ABAAABCDBBABCDDEBCABC", "ABC"))