Third Internal Questions Advanced Algorithms

1. Give the overlapping suffix lemma along with its graphical proof and explain the Naive string matching algorithm.(Code Here)
2. In the RabinKarp algorithm Explain how a string is formulated as a decimal number of radix d using horner's rule and how shifts of its substring are achieved. Why is q chosen such that dq fits in one word? Finally give the Rabin-Karp Algorithm.(Code Here)
3. In Finite Automaton based string matching explain how the transition function is computed and how is it used in the finite automaton matcher.(Code Here)
4. Give the Knuth-Morris-Pratt algorithm along with the compute prefix function.(Code Here)
5. Give the Boyer-Moore Algorithm for pattern matching.(Code Here)

All the Best