Please do it in python

Pattern Matching Algorithms

Lab Exercises: In this lab, you will be implementing two pattern matching algorithms.

Exercise-1: Nave pattern matching algorithm

Naive pattern matching:Slide the pattern over text one index by one and check for a match. If a match is found, then slides by 1 again to check for subsequent matches. Given a text and a pattern, write a function search which takes a text and a pattern as inputs and prints all occurrences of the pattern in the text i.e., each of their start index. If there is no pattern, return -1. Assume that the length of the text is greater than the pattern. Write a pseudocode or an algorithm, explain your algorithm and perform the time complexity. You can implement the algorithm in python or in Java. You cannot use a library to implement this algorithm.

Make the following function calls the following inputs:

Input-1: txt1[] = "This is a CMPSC 412 lab course. Students take this course along with CMPSC 462" Pat1[] = "CMPSC" Output: Patterns found at index 10 and index _ Input-2: txt1[] = "This is a CMPSC 412 lab course. Students take this course along with CMPSC 462"

Pat2[] = "course" Output: Patterns found at index __ and index __ Input-2: txt2[] = "AABAACAADAABAABAABBBBBAAABDCBA" Pat3[] = "BBBBBA" Output: Patters found at index __

Attach the code and screenshots of your results here.

Exercise-2: KnuthMorrisPratt (KMP) algorithm pattern matching algorithm

KMP pattern matching: The Naive pattern matching algorithm doesnt work well in cases where there are many matching characters followed by a mismatching character. KMP uses an optimized approach and has a better time complexity. KMP uses Longest Proper Prefix which is Suffix (LPS).