KMP Stream Matcher State

Problem

Match a pattern in a text with the KMP algorithm.

Build the prefix function for pattern, then scan text left to right without ever moving backwards in the text. Overlapping matches are reported. patterns passed to this problem are non-empty.

Return [prefix_function, match_start_indices].

Hint

On a mismatch fall back to the longest proper prefix that is also a suffix.

Test cases

case 1

in: ["ababab","ab"]

expected: [[0,0],[0,2,4]]

case 2

in: ["aaaa","aa"]

expected: [[0,1],[0,1,2]]

case 3

in: ["abc","d"]

expected: [[0],[]]

case 4

in: ["","a"]

expected: [[0],[]]

Starter codePython

def kmp_matches(text, pattern):
    # Your code here
    pass

4 test cases · run your code against them in the editor