Naive substring search is O(n·m) in the worst case ("aaaa...ab" in "aaaa...a"). KMP is O(n + m): it precomputes, for each prefix of the pattern, the length of the longest proper prefix that is also a suffix (the failure function, or LPS array), so it never re-examines text characters.
Implement:
lps(pattern): the failure function as a listkmp_search(text, pattern): the start indices of all occurrences, including overlapping onesshortest_period(s): the length of the smallest string p such that s is a prefix of p repeated many times ("abcabcab" → 3). Hint: it's len(s) - lps(s)[-1].Don't use str.find, re or in for the search.