The constructor for the Knuth Morris Pratt String Matcher is difficult to understand. A more direct approach would be to check, for each position i, whether each prefix of length i – 1 down to 1...

The constructor for the Knuth Morris Pratt String Matcher is difficult to understand. A more direct approach would be to check, for each position i, whether each prefix of length i – 1 down to 1 matches the part of the pattern ending at position i. Implement this algorithm and analyze its worst-case running time.