Beyond A level · 5 exercises

Python 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.

Exercises

Find every matchPrint every position (from 0) where the pattern occurs in the text, overlappingExpert
Common beginningPrint the longest beginning that all words share, or none if they share nothing.Expert
Repeating patternFind the shortest piece that, repeated a whole number of times, makes the text (forExpert
Longest stretch without repeatsFind the length of the longest run of consecutive characters with no characterExpert
Different piecesHow many different non-empty substrings (runs of consecutive characters) does a textExpert