Algorithms
Topics:
String Searching

String Searching

String Searching by KMP algorithm (Knuth Morris Pratt algorithm)

Motivation Problem: Given $2$ strings $P$(pattern) and $T$(text), find the number of occurrences of $P$ in $T$.

Basic / Brute Force solution:

One obvious and easy to code solution that comes to mind is this: For each index of $T$, take it as a starting point and find if $T_{i,i+1,...,i+|P|-1}$ is equal to $P$.

for i = 0 to length(T)-length(P):

Found = true

for j = i to i + length(P) - 1:

if P[j-i] not equal to T[j]:

Found = False

if Found = True



This brute force takes $O(|P| \cdot |T|)$ time in the worst case, which is obviously too slow for large strings.

Knuth Morris Pratt Algorithm:

Suppose for each index $i$ of some string $Z$, the longest suffix in $Z_{0,1,...,i}$ that is also a prefix of $Z_{0,1,...,i}$, be known. Formally, a length $F_i$ is known such that $Z_{0,1,...,F_i-1}$ = $Z_{i-F_i+1,...,i}$. Let these lengths be stored in array $F$. The suffix needs to be proper(whole string is not a proper suffix).

Then the solution to the motivation problem can be found as follows:

Define a string $V = P + '#' + T$, where $'#'$ is a delimiter that is not present in either of $P$ or $T$. Now, if the above information is known, all occurrences of $P$ in $T$ can be found as follows: If at some index $i$, $F_i = |P|$, then there is an occurrence of Pattern $P$ at position $i-|P|+1$. All such indices from $|P|+1$ [0 based indexing, the index just after '#'], need to be checked.

The main part of KMP algorithm calculates the array $F$, which is also called the prefix function. If calculation of $F$ or the prefix function can be done efficiently, then we have an efficient solution to the motivation problem. KMP algorithm finds the prefix function in $O(length of String)$ time.

To find the prefix function, best possible use of previous values of array $F$ is made, so that calculations aren't done again and again. Suppose all $F_i$ have been calculated, and now $F_{i+1}$ is to be calculated. It is to be noted that, value of $F_{i+1}$ can be at most 1 greater than $F_i$. Here is a proof by contradiction:

Suppose $F_{i+1} > F_i + 1$. Now, if the $(i+1)^{th}$ character is removed, we obtain a suffix ending at index $i$ that is of length $F_{i+1} - 1$, which is greater than $F_i$. This is a contradiction, hence proved.

Observe that if $Z_{i+1} = Z_{F_i}$, then the value of $F_{i+1} = F_i + 1$. If not, a smaller suffix ending at index $i$ is to be found, that is also a prefix of $Z_{0,1...,i}$. Let the length of such a suffix be $j$, then if $Z_{i+1} = Z_{j}$ then $F_{i+1} = j + 1$. If again the equality doesn't hold true, smaller and smaller suffixes that end at index $i$, which are also prefixes of $Z_{0,1...,i}$ need to be found.

The only thing remaining is, how to find the length of next smaller suffix ending at index $i$, that is also a prefix? This is also pretty simple. Observe that due to the property of $F$, the segment $Z_{0,1,...,F_i-1}$ is equal to the segment $Z_{i-F_i+1,...,i}$. So to find the next smaller suffix ending at index $i$, the longest suffix ending at $F_i - 1$ can be found which is $F_{F_i-1}$, and this suffix will be the next smaller suffix ending at index $i$. If this suffix also doesn't satisfy our criteria, then smaller suffixes can be found with the same process, here it will be $F_{F_{F_i-1} - 1}$. Note that, if at some point the length becomes $0$, the process is stopped.

This completes $KMP$ algorithm. Below is the code:

vector<int> prefix_function (string Z) {

int n = (int) Z.length();

vector<int> F (n);

F[0]=0;

for (int i=1; i<n; ++i) {

int j = F[i-1];

while (j > 0 && Z[i] != Z[j])

j = F[j-1];

if (Z[i] == Z[j])  ++j;

F[i] = j;

}

return F;

}


Finding the $F$ array for "ABCABC"

Initially, $F_0 = 0$.

Index $1 \rightarrow F_{0} = 0$, $j$ does not go into while loop and $Z_j \neq Z_i$, therefore value of $F_i = 0$.

Index $2 \rightarrow F_{1} = 0$, $j$ does not go into while loop and $Z_j \neq Z_i$, therefore value of $F_i = 0$.

Index $3 \rightarrow F_{2} = 0$, $j$ does not go into while loop and $Z_j = Z_i$, therefore value of $F_i = 1$.

Index $4 \rightarrow F_{3} = 1$, $j$ satisfies while loop condition but $Z_j = Z_i$, hence does not go into while loop, therefore value of $F_i = 2$.

Index $5 \rightarrow F_{4} = 2$, $j$ satisfies while loop condition but $Z_j = Z_i$, therefore value of $F_i = 3$.

Contributed by: Rishi Vikram