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$

---

Fractional Differential Equations

Haven’t written a single blog in 2021, this shows how 2021 went - many beautiful memories.

Let me resume with one of the most interesting topics in Calculus - Differential Equaltions.

It is a way of expressing real world dynamical systems in terms of derivatives in an equation.

So, a differential equation of the form given below is of order 2
$$\frac{\mathrm{d}^2}{\mathrm{d}x^2}y + \frac{\mathrm{d}}{\mathrm{d}x}y+c=D$$

Note the term real world, so we understand that in the real world having a whole number as the order will be impossible.

Motivation: Dr Peyman | Solving a Fractional Differential Equation | Youtube

Therefore, in this blog we will understand (with an example) on how to solve a differential equation of fractional order or fractional differential equation.

But before moving forward, we brush-up on some important concepts. I will deal with these in a very shallow yet exhaustive manner.

Gamma Function:

The Gamma Function is defined as an integral
$$\tag*{(1)} \boxed{\Gamma(\mathrm{z})=\int_{0}^{\infty}e^{-t}t^{z-1}\mathrm{d}t}$$
While, we can write another separate blog on the properties of Gamma Function, we shall limit ourselves to the definition of the the function only in this blog.
Some important definitions related to the Gamma Function are as follows:
$$\tag*{(2)} \boxed{\Gamma(\mathrm{z+1})=\mathrm{z}\Gamma(\mathrm{z})}$$
$$\tag*{(3)} \boxed{\Gamma(\mathrm{n+1})=n!}$$
$$\tag*{(4)} \boxed{\Gamma(\mathrm{\frac{n}{2}})=\sqrt{\pi}\frac{(n-2)!!}{2^\frac{(n-1)}{2}}}$$
Eqn (4), opens up another mystery that is double factorial, so we will also explore upon it a little,
$$5!! = 5 \times 3 \times 1 \\ 6!! = 6 \times 4 \times \times 2 \\$$
I hope you get the idea. Note: $n!! \neq (n!)!$

Now lets solve a problem to see how it works.

Problem:

$$\mathrm{D}^{\frac{1}{2}}y=-y+x^2+\frac{8}{3\sqrt\pi}x^\frac{3}{2}$$
We first denote this as equation 5
$$\tag*{(5)} \mathrm{D}^{\frac{1}{2}}y=-y+x^2+\frac{8}{3\sqrt\pi}x^\frac{3}{2}$$
Multiplying $\mathrm{D}^{\frac{1}{2}}$ on both sides of equation 5 we get,
$$\mathrm{D}^{\frac{1}{2}}(\mathrm{D}^{\frac{1}{2}}y)=\mathrm{D}^{\frac{1}{2}}(-y+x^2+\frac{8}{3\sqrt\pi}x^\frac{3}{2})$$
$$\tag*{(6)} y'=-\mathrm{D}^{\frac{1}{2}}y+\mathrm{D}^{\frac{1}{2}}x^2+\mathrm{D}^{\frac{1}{2}}\frac{8}{3\sqrt\pi}x^\frac{3}{2}$$
Now, to bring simplicity, we name each term separately and solve.
$$\mathrm{A}=-\mathrm{D}^{\frac{1}{2}}y \\ \mathrm{A}= -(-y+x^2+\frac{8}{3\sqrt\pi}x^\frac{3}{2}) \\ \boxed{\mathrm{A}=y-x^2-\frac{8}{3\sqrt\pi}x^\frac{3}{2}}$$
Again,
$$\mathrm{B}=\mathrm{D}^{\frac{1}{2}}x^2 \\$$
Now, how do we calculate the fractional derivative of $x^2$?
The answer will take us back to the person without whom Calculus wouldn’t have been what it is today - Riemann. The generalized defination of a derivative is derived from Riemann-Liouville definition for fractional derivative.

$$\frac{\mathrm{d}^q}{\mathrm{dx}^q}x^m = \frac{\Gamma(m+1)}{\Gamma(m-q+1)}x^{(m-q)}$$
When $q=\frac{1}{2}$ & $m=2$, we have,
$$\mathrm{B}=\mathrm{D}^{\frac{1}{2}}x^2=\frac{\mathrm{d}^{\frac{1}{2}}}{\mathrm{dx}^{\frac{1}{2}}}x^2 = \frac{\Gamma(3)}{\Gamma(\frac{5}{2})}x^{(2-\frac{1}{2})} =\frac{\Gamma(3)}{\Gamma(\frac{5}{2})}x^{(2-\frac{1}{2})}$$
From definitions $(3)$ & $(4)$ above, we get,
$$B = \frac{2}{\frac{3}{4}\sqrt{\pi}}x^{\frac{3}{2}}\\ \boxed{B = \frac{8}{3\sqrt{\pi}}x^{\frac{3}{2}}}$$
Again,
$$C=\mathrm{D}^{\frac{1}{2}}\frac{8}{3\pi}x^\frac{3}{2} \\ C=\frac{8}{3\pi}\mathrm{D}^{\frac{1}{2}}x^\frac{3}{2}\\ \boxed{C=\frac{8}{3\sqrt\pi}\frac{3 \sqrt{\pi}}{4}x}$$

Plugging A, B and C in equation $(6)$, we get,
$$y'= [y-x^2-\frac{8}{3\sqrt\pi}x^\frac{3}{2}] + [\frac{8}{3\sqrt{\pi}}x^{\frac{3}{2}}] + [\frac{8}{3\sqrt\pi}\frac{3 \sqrt{\pi}}{4}x]\\ y'= y-x^2+2x$$
Let’s simplify this further,
$$(y-x^2)'+2x = y-x^2+2x \\ (y-x^2)'=y-x^2$$
So, the derivative of the function is the function itself, therefore, the only function that satisfies this is exponential function.
$$y-x^2=Ce^x$$
$C$ is a constant.
$$y = Ce^x + x^2$$
Using $y(0)=0$ to find $C$, we get $C=0$, therefore,
$$\boxed{\boxed{y = x^2}}$$

Cheers!