Question

(Very Easy)You have been provided with the following string matching algorithm: KMP_matcher.py(see below). Using the algorithm, I want you to find the word(s) that have:

1. Longest Continual Substring of:

- Vowels

- Consonants

2. Longest Continual Prefix of:

- Vowels

- Consonants

3. Longest Continual Suffix of:

- Vowels

- Consonants

Example: ["Hello", "World", "Face", "Asthma", "Spring", "Because", "Thorough", "Sequoia" ]. In this list of strings, "Sequoia" has the longest substring of consecutive vowels. "Asthma" has the longest substring of consecutive consonants. "Asthma" Also has the longest prefix of consecutive vowels. "Spring" has the longest prefix of consecutive consonants. "World" has the longest suffix of consecutive consonants and "Sequoia" has the longest suffix of consecutive vowels. Your word file is going to be a long excerpt from "Lorem Ipsum" text found in lorem_ipsum.txt(see below). If there are multiple words that tie in any criteria, return ALL words that tie. You can assume that the only characters in the file will be standard English letters, no numbers, special characters, or characters with diacritic marks.

This is the KMP_matcher.py algorithm

def pfun(pattern): # function to generate prefix function for the given pattern
n = len(pattern) # length of the pattern
prefix_fun = [0]*(n) # initialize all elements of the list to 0
k = 0
for q in range(2,n):
while k>0 and pattern[k+1] != pattern[q]:
k = prefix_fun[k]
if pattern[k+1] == pattern[q]: # If the kth element of the pattern is equal to the qth element
k += 1 # update k accordingly
prefix_fun[q] = k
return prefix_fun # return the prefix function

def KMP_Matcher(text,pattern): # KMP matcher function
m = len(text)
n = len(pattern)
flag = False
text = '-' + text # append dummy character to make it 1-based indexing
pattern = '-' + pattern # append dummy character to the pattern also
prefix_fun = pfun(pattern) # generate prefix function for the pattern
q = 0
for i in range(1,m+1):
while q>0 and pattern[q+1] != text[i]: # while pattern and text are not equal, decrement the value of q if it is > 0
q = prefix_fun[q]
if pattern[q+1] == text[i]: # if pattern and text are equal, update value of q
q += 1
if q == n: # if q is equal to the length of the pattern, it means that the pattern has been found.
print("Pattern occours with shift",i-n) # print the index, where first match occours.
flag = True
q = prefix_fun[q]
if not flag:
print('\nNo match found')

KMP_Matcher('aabaacaadaabaaba','aabac') # function call, with two parameters,text and pattern

This is the lorum_ipsum.txt

Lorem ipsum dolor sit amet, consectetur adipiscing elit. In dignissim sollicitudin interdum. Praesent est eros, lobortis ac fermentum in, facilisis non tellus. Morbi euismod quis elit in rhoncus. Etiam lorem arcu, imperdiet a libero non, lobortis pretium elit. Suspendisse egestas diam in nunc suscipit, ac convallis lectus commodo. Nullam tincidunt est sed arcu semper gravida id et sapien. Praesent commodo dignissim sagittis.

Fusce id tristique sem, vel aliquam justo. Cras at malesuada tellus. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Integer id viverra tortor, vel rhoncus diam. Pellentesque eget accumsan tellus. Integer ac est non turpis tincidunt efficitur. Nam ex augue, feugiat vitae ultrices sed, pharetra quis leo. Ut vitae erat elit. Suspendisse faucibus molestie neque.

Proin luctus, lorem eget tempor ornare, nisl est posuere dolor, sit amet varius mauris odio in dolor. Interdum et malesuada fames ac ante ipsum primis in faucibus. Fusce vel suscipit nisi. Cras suscipit ultrices arcu sit amet euismod. Nunc bibendum finibus quam. Fusce non ipsum ut mi tincidunt iaculis. Nunc eget porttitor tortor, et porttitor mi. Morbi varius, dui sit amet dignissim efficitur, eros ipsum volutpat eros, at efficitur metus dolor vitae justo. Mauris rutrum eros dolor, a iaculis diam ullamcorper at. Aenean sit amet felis tempus, dignissim orci ut, fermentum mi. Nulla facilisi. Sed eget turpis nunc. Vestibulum et lacus semper, auctor augue quis, auctor ante. Maecenas euismod, diam non egestas semper, purus orci blandit enim, ultricies vulputate neque tellus ac urna. Curabitur euismod magna finibus, laoreet massa sed, semper lacus. Vestibulum maximus rhoncus sem, at vehicula ante elementum ut.

Aenean venenatis in velit at ullamcorper. In sit amet laoreet turpis. Donec leo sem, tempor et pellentesque eu, aliquet nec mi. Sed ut dolor sit amet ex dictum pharetra et et mauris. Nam tincidunt, magna id pulvinar dapibus, dui tellus vulputate felis, et fringilla nisl mi et nibh. Aliquam finibus tempor augue, ut rutrum velit efficitur ac. Orci varius natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Sed et elementum augue, nec malesuada nulla. Morbi quis libero quis tellus convallis elementum. Nunc pulvinar ex ut velit convallis, et semper nisl egestas. Praesent lorem libero, scelerisque vitae cursus sit amet, maximus nec nisi. Donec rutrum risus eget massa commodo dapibus. Vestibulum pharetra turpis non posuere viverra. Mauris eu dui semper, pulvinar turpis eget, aliquet lorem. In feugiat cursus pretium.

Etiam ornare aliquam luctus. Vestibulum nibh magna, maximus sed augue suscipit, egestas cursus orci. Maecenas rutrum congue odio vitae venenatis. Donec mattis pretium odio, sodales semper est ultricies vel. Suspendisse potenti. Vivamus ante neque, egestas et elit a, luctus auctor risus. Vestibulum et arcu eget odio auctor bibendum nec commodo tortor. Nulla aliquet magna tortor, ac ornare nulla eleifend in. In mollis semper nulla a efficitur.

Suspendisse potenti. Proin facilisis blandit sapien. Sed fringilla, ipsum ac fermentum scelerisque, felis ligula cursus libero, ac efficitur risus libero et diam. Vivamus lacinia pretium sapien, sed aliquam massa semper a. Curabitur semper neque mi, sit amet sollicitudin tellus pharetra at. Aliquam venenatis sagittis eros, ac ultrices ligula vehicula id. Integer feugiat ultricies sodales. Duis consectetur orci eu risus lobortis, et tempor purus volutpat.

Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Etiam est diam, ornare vel nisi ut, bibendum dapibus eros. Nullam eget placerat turpis. Interdum et malesuada fames ac ante ipsum primis in faucibus. Morbi sit amet accumsan enim, ac facilisis tortor. Maecenas faucibus, metus sed placerat tempor, lacus massa interdum arcu, ut aliquam massa leo a ante. Nulla facilisis magna ut justo lobortis placerat. Cras feugiat venenatis nisi congue pharetra. Maecenas ut lorem id nisi viverra porta sit amet at ipsum. Duis fringilla, justo scelerisque luctus vulputate, nunc erat posuere eros, in semper velit libero quis velit. Ut semper, massa non elementum egestas, tortor massa pharetra mi, a malesuada nisl arcu laoreet eros.

Etiam tincidunt, nisi ut suscipit gravida, est ante ullamcorper purus, eget finibus nisl nisl quis justo. Integer semper massa eget nunc pellentesque, in mattis tellus vestibulum. In ut diam placerat, venenatis enim quis, faucibus odio. Sed et dignissim ipsum. Sed lacinia lacinia velit, ac tristique velit pharetra ut. Cras cursus enim mauris, at auctor dolor pretium vel. Curabitur ac nisl et diam fringilla placerat. Pellentesque neque lacus, rhoncus vitae nibh vitae, sagittis sodales eros. In eu vehicula magna. Donec rhoncus a lacus vitae tincidunt. Donec venenatis, risus at aliquet semper, tortor purus auctor nibh, nec porta ex enim id nulla. Ut ac scelerisque lectus.

Mauris vitae turpis massa. Vestibulum ultricies, nibh quis placerat porttitor, arcu est convallis enim, in euismod massa nisi quis dui. Fusce congue elit ut lacus consequat pharetra pellentesque eu purus. Etiam semper, odio a viverra pellentesque, magna felis consectetur velit, porttitor finibus libero eros eget ex. Proin aliquet fringilla risus id dictum. Fusce vel nibh in metus cursus lobortis eu blandit nunc. Mauris et lacus gravida, posuere nibh sed, finibus diam. Proin vel turpis fermentum, dapibus diam nec, porta ipsum. Aenean tempor leo non aliquam semper. Cras sit amet ex eu ipsum suscipit rutrum et vel lacus. Vivamus vitae justo id justo pellentesque venenatis. Aliquam erat volutpat. Phasellus mi augue, accumsan nec accumsan eget, hendrerit aliquam elit.

Pellentesque dictum suscipit sem, a vehicula sapien rhoncus ut. Nunc dignissim, est quis ullamcorper hendrerit, tortor orci egestas magna, sed ultricies lacus sapien non orci. Sed maximus convallis nunc, ac finibus lorem luctus nec. Curabitur eu massa mattis, viverra nibh at, tristique sapien. Phasellus molestie eros eget nibh tincidunt, ultricies pulvinar augue sollicitudin. Nullam dui enim, lobortis quis ligula in, iaculis ullamcorper felis. Fusce ac interdum elit, in dignissim mauris.

Answer 1

# Python program for KMP Algorithm

def KMPSearch(pat, txt):

    M = len(pat)

    N = len(txt)

    # create lps[] that will hold the longest prefix suffix

    # values for pattern

    lps = [0]*M

    j = 0 # index for pat[]

    # Preprocess the pattern (calculate lps[] array)

    computeLPSArray(pat, M, lps)

    i = 0 # index for txt[]

    while i < N:

        if pat[j] == txt[i]:

            i += 1

            j += 1

        if j == M:

            print ("Found pattern at index " + str(i-j))

            j = lps[j-1]

        # mismatch after j matches

        elif i < N and pat[j] != txt[i]:

            # Do not match lps[0..lps[j-1]] characters,

            # they will match anyway

            if j != 0:

                j = lps[j-1]

            else:

                i += 1

def computeLPSArray(pat, M, lps):

    len = 0 # length of the previous longest prefix suffix

    lps[0] # lps[0] is always 0

    i = 1

    # the loop calculates lps[i] for i = 1 to M-1

    while i < M:

        if pat[i]== pat[len]:

            len += 1

            lps[i] = len

            i += 1

        else:

            # This is tricky. Consider the example.

            # AAACAAAA and i = 7. The idea is similar

            # to search step.

            if len != 0:

                len = lps[len-1]

                # Also, note that we do not increment i here

            else:

                lps[i] = 0

                i += 1

txt = "ABABDABACDABABCABAB"

pat = "ABABCABAB"

KMPSearch(pat, txt)