Knutt Morris Pratt Algorithm

Question 1

State the KMP-Algo prompt

Answer 1

Write a function that takes in two strings and checks if
the first string contains the second one using the Knuth
-Morris-Pratt algorithm. The function should return a
boolean.

Question 2

Hint 1 / Step 1

Answer 2

The Knuth-Morris-Pratt algorithm works by
identifying patterns in the potential substring and
exploiting them to avoid doing needless character
comparisons when searching for the substring in
the main string.

For instance, take the string
“ababac” and the substring “abac”, comparing
these strings will fail at the fourth character,
where “b” is not equal to “c”, Instead of
restarting the comparison at the second character
of the main string, however, we notice that the
substring “ab”, which is at the beginning of our
potential substring, just appeared near our point
of failure in the main string. How can we use this
to our advantage?

Question 3

Hint 2 / Step 2

Answer 3

Start by traversing the potential substring and
building out a pattern table. This 1-dimensional
array should store, for every position in the
substring, the last index at which a matching
pattern has been seen; more specifically, this
index should be the ending index of a prefix in the
substring that is also a suffix at the given position.
For example, the string “abcababcd” should yield
the following pattern table: [-1, -1, -1, 0, 1, 0, 1, 2,
-11.

Question 4

Hint 3 / Step 3

Answer 4

After the pattern table mentioned in Hint #2 has
been built, traverse the main string and the
potential substring with two separate pointers.
When characters match, move the pointers
forward. When characters don’t match, check if
the pointer in the substring is at the very
beginning of the substring; if it is, then there is no
match and you can move the pointer of the main
string forward until there is a match; if it isn’t,
then move it to the position that comes right after
the last seen pattern stored at the previous index
in the pattern table.

Question 5

Sample Input 2

“string”:
“testwafwafawfawfawfawfawfawfawfa”,
“substring”:

“fawfawfawfawfa”

Answer 5

TRUE

Question 6

Sample input 3

“string”: “tesseatesgawatewtesaffawgfawtteafawtesftawfawfawfwfawftest”,
“substring”: “test”

Answer 6

TRUE

Question 7

Define the Main Function

Answer 7

def knuthMorrisPrattAlgorithm(string, substring) :
pattern = buildPattern(substring)
return doesMatch(string, substring, pattern)

Question 8

Define the BuildPattern function

Answer 8

def buildPattern(substring):
pattern = [-1 for i in substring]
j=0
¡=1

  while i < len(substring):
    if substring[i] == substring[j] :
      pattern[i] = i
      ¡ += 1
      j += 1
    elif i > 0:
      j= pattern [i - 1] + 1
    else:
      ¡ += 1
return pattern

Question 9

Define the DoesMatch()

Answer 9

def doesMatch(string, substring, pattern) :
  ¡=0
  j =0
  while i + len (substring) - j <= len(string):
    if string[i] == substring[j]:
      if j == len (substring) - 1:
        return True
      i += 1
      j += 1
    elif j > 0:
      j = pattern[j - 1] + 1
    else:
      ¡ += 1
return False

Question 10

Define the Time and Space Complexity of KMP Algo

Answer 10

O(n + m) time | 0(m) space