Knuth-Morris-Pratt is more efficient string matches algorithm because doing less number of comparisons than its contraparte the brute force algorithm. The codes are shown below.
Brute Force algorithm
def BruteForce(p,s):
i = 0
j = 0
while(i < len(p) and j < len(s)):
if(p[i] == s[j]):
i += 1
j += 1
else:
i = i - j + 1
j = 0
if(j >= len(s)):
return i-len(s)
else:
return 0
if __name__ == "__main__":
string="gcagtacgcagagagtatacagtacg"
pattern='agtacg'
print("String: ", string)
print("Pattern: ", pattern)
ans=BruteForce(string,pattern)
print("Pattern found at index: ", ans)
Knuth-Morris-Pratt algorithm
def KnuthMorrisPratt(s,p):
if not p:
return 0
if not s or len(p) > len(s):
return 0
chars = list(p)
next = [0] * (len(p) + 1)
for i in range(1, len(p)):
j = next[i + 1]
while j > 0 and chars[j] is not chars[i]:
j = next[j]
if j > 0 or chars[j] == chars[i]:
next[i + 1] = j + 1
j = 0
for i in range(len(s)):
if j < len(p) and s[i] == p[j]:
j = j + 1
if j == len(p):
return i - j + 1
elif j > 0:
j = next[j]
i = i - 1
if __name__ == "__main__":
string="gcagtacgcagagagtatacagtacg"
pattern='agtacg'
print("String: ", string)
print("Pattern: ", pattern)
ans=KnuthMorrisPratt(string,pattern)
print("Pattern found at index: ", ans)
To learn more about string matches see: https://brainly.com/question/23095498
#SPJ4
