Expert · String algorithms · 253 of 264
Different pieces
How many different non-empty substrings (runs of consecutive characters) does a text have? Texts have up to 300 characters.
Input: one line. Output: the number of different substrings.
Examples
Input
abc
Output
6
Input
aaa
Output
3
Input
abab
Output
7
One more test checks 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.