Knuth Morris Pratt Algorithm & Other associated methods

I have always wanted to learn more about Data Structures and Algorithms.

However, owing to the non-CS background of my graduation, I never had the time to do so.

I thought, I would give it a try and started solving LeetCode problems on 20-September-2024.

As soon as I logged in, the first problem that was thrown at me was the Shortest Palindrome Problem.

Problem description is as follows:

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this
transformation.

Example 1:
Input: s = “aacecaaa”
Output: “aaacecaaa”

Example 2:
Input: s = “abcd”
Output: “dcbabcd”

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of lowercase English letters only.

---

I went ahead and tried solving the problem from a pseudocode POV:

1. Check the length of s to see that the constraint is satisfied
2. If len(s)=0, return result as s
3. Start searching s and eleminating each element from the back with each iteration, that means check if each s[0:n] or s[0:(n-1)] or s[0:(n-2)] and so on is a palindrome.
4. We assume, for now, that we are given a helper function isPalindrome, which compares the 0th element with the nth element and (0+1)th element with the (n-1)th element.
5. Find the shortest possible palindrome - sp.
6. Then reverse the remaining part of the string and add it to the start of sp.

Now, if we see the above in action, it will look pretty messy, however, we go ahead and check it anyway:

1. Assume we have string : s=abcd.
2. If len(s) = 0, return s
3. Else, run around s, check, if
   4. s[0] = s[len(s)-1] = FALSE : $a \neq d$
   5. s[0] = s[len(s)-2] = FALSE : $a \neq c$
   6. s[0] = s[len(s)-3] = FALSE : $a \neq b$
   7. s[0] = s[len(s)-4] = TRUE : $a = a$
4. isPalindrome[s[0]]=TRUE
5. s' = reverse[s[1:n]] : $dcb$
6. concatenate [s', s] : $dcbabcd$

---

I solved it using this, however, you will notice that there are 2 linear loops running,

1. loop for checking through each element : $O(n)$
2. isPalindrome loop : $O(n)$

The complexity of the above will be $O(n^2)$.

---

I was happy :) and submitted, after submission, I saw that there are multiple other algorithmic approaches that give a much better and faster solution to this solution.

This is when I came across the Knuth Morris Pratt Algorithm.

---

I tried to understand this from a Mathematician’s perspective before getting into the programming.

Often, the computer scientists over simplify a mathematical method and call it an algorithm, this is precisely why, a solution that would have taken an afternoon for a CS grad, is taking more than 2 days for a Mathematician.

---

Knuth Morris Pratt is an efficient algorithm for substring search 1.

• Prefix Function Definition:
  You are given a string s of length n. The prefix function for this string is defined as an array $\pi$ of length n, where $\pi(i)$ is the length of the longest proper prefix of the substring $s[0...i]$ which is also a suffix of this substring. A proper prefix of a string is a prefix that is not equal to the string itself. By definition,   $\pi[0]=0$.

Mathematically the definition of the prefix function can be written as follows:
 $\pi[i] = \max_ {k = 0 \dots i} \{k : s[0 \dots k-1] = s[i-(k-1) \dots i] \}$

Analytic Number Theory - 1

For those who have been following my blogs earlier, you would know that I am an amateur, self-made mathematician, and I like to write as I learn new concepts or explore old ones.

My old blog, which is now abandoned to start this new and more organized blog, can be accessed from here: Infinity & Beyond

Analytic number theory is taught as a part of higher mathematics in post-graduate Pure Science (Mathematics Hons.) courses and under-graduate engineering Courses in India.

While going through the internet, we find various sources for learning about this subject. Therefore, I will break this blog up into various pieces to cover this subject in significant details.

Coming to this, we will keep Tom M Apostol’s Introduction to Number Theory as the foundational text for this blog.

In this blog, we will cover the contents of Chapter 1 and Chapter 2 of Apostol.

Therefore, Elementary Number Theory, Fundamental Theorem of Arithmetic, Arithmetical Functions and Dirichlet Multiplication will be covered, amognst various other concepts.

It is again to be noted that, readers may take this is a disclaimer before we start, that I am writing this blog as a way to teach myself this subject and would therefore run this blog in a “note making/understanding” tone, rather than as a tutorial.

Fundamental Theorem of Arithmetic:

Many proofs of Analytic number theory makes use of the concepts that we learn in this section.

---

The principle of Induction:

If $Q$ is set of integers such that,
(a) $1 \in Q$
(b) $n \in Q \text{ implies } n+1 \in Q$
then,
(c ) $\text{all integers }\geq1\text{ belongs to } Q$

---