Expert · String algorithms · 251 of 264
Repeating pattern
Find the shortest piece that, repeated a whole number of times, makes the text (for abcabcabc it is abc). If none shorter exists, the whole text is the answer.
Input: one line (up to 9600 characters). Output: the length of that piece.
Examples
Input
abcabcabc
Output
3
Input
abcd
Output
4
Input
aaaa
Output
1
2 more tests check other inputs when you press Check.
Stuck? The idea behind string algorithms
Finding patterns in text: compare a window of the text with the pattern as it slides along, or use what has already matched to skip ahead.
str.find(pattern, start) gives the next position, or -1 when there is none.
text, pat = "abababa", "aba"
i = text.find(pat)
while i != -1:
print(i)
i = text.find(pat, i + 1)Watch for: Matches can overlap ("aba" twice in "ababa"): move on by one, not by the pattern's length.