/
NikolayIvkin
/
TheAlgorithms_Python
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms_Python
Код
Запросы
2
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
strings/prefix_function.py
64 строки
2 KB
Maxim Smolskiy
Enable ruff RUF002 rule (#11377)
22 апр 2024, 22:51
Не верифицирован
22 апр 2024, 22:51
4700297
Код
Авторство
О чём код?
""" https://cp-algorithms.com/string/prefix-function.html Prefix function Knuth-Morris-Pratt algorithm Different algorithm than Knuth-Morris-Pratt pattern finding E.x. Finding longest prefix which is also suffix Time Complexity: O(n) - where n is the length of the string """ def prefix_function(input_string: str) -> list: """ For the given string this function computes value for each index(i), which represents the longest coincidence of prefix and suffix for given substring (input_str[0...i]) For the value of the first element the algorithm always returns 0 >>> prefix_function("aabcdaabc") [0, 1, 0, 0, 0, 1, 2, 3, 4] >>> prefix_function("asdasdad") [0, 0, 0, 1, 2, 3, 4, 0] """ # list for the result values prefix_result = [0] * len(input_string) for i in range(1, len(input_string)): # use last results for better performance - dynamic programming j = prefix_result[i - 1] while j > 0 and input_string[i] != input_string[j]: j = prefix_result[j - 1] if input_string[i] == input_string[j]: j += 1 prefix_result[i] = j return prefix_result def longest_prefix(input_str: str) -> int: """ Prefix-function use case Finding longest prefix which is suffix as well >>> longest_prefix("aabcdaabc") 4 >>> longest_prefix("asdasdad") 4 >>> longest_prefix("abcab") 2 """ # just returning maximum value of the array gives us answer return max(prefix_function(input_str)) if __name__ == "__main__": import doctest doctest.testmod()