Formalization:

• Text: $T[1..n]$
• Pattern: $P[1..m]$ ($m\le n$)
• elements of $P$ and $T$ are characters drawn from a finite alphabet $\Sigma$.
• $\Sigma^*$ denotes the set of all finite-length string using $\Sigma$
• $\varepsilon\in \Sigma ^*$ emptry string
• $x y$ denotes concatenation of $x$ and $y$
• $w\sqsubset x$: $w$ is a prefix of $x$, i.e. $x=wy$ for some $y\in \Sigma^*$
• $w\sqsupset x$: $w$ is a suffix of $x$, i.e. $x=yw$ for some $y\in \Sigma^*$
• $P_k$ is the $k$-character prefix $P[q..k]$

Comparison of Algorithms:

Algorithm	Preprocessing time	Matching Time
Naive	0	$O((n-m+1)m)$
Rabin-Karp	$\Theta(m)$	$O((n-m+1)m)$
Finite Automaton	$O(m\vert \Sigma\vert)$	$\Theta(n)$
Knuth-Morris-Pratt	$\Theta(m)$	$\Theta(n)$
Z-Algorithm	0	$\Theta(m+n)$

Rabin-Karp algorithm

Based on certain assumptions its average-case running time is better.

Let us assume $\Sigma={0,1,2,\ldots,d}$. Let $p$ denote the interpretation of $P[1..m]$ as a radix-d number. Similarly let $t_s$ denote the interpretatin of $T[s+1\ldots s+m]$ for $s\in {0,1,\dots n-m}$. Now $t_s=p\iff T[s+1\ldots s+m]=P[1..m]$.

We can compute $p$ in $\Theta(m)$ using Horner’s rule

$p=P[m]+10(P[m-1]+10(P[m-2]+\ldots))$

Similarly

$t_{s+1}=10(t_s-10^{m-1}T[s+1])+T[s+m+1]$

where we can calculate $10^{m-1}$ in $O(\lg m)$.

For string matching we work with $\mathbb Z_q$ where $q$ is a prime such that $dq$ fits inside a computer word. However $t_{s} \equiv p\pmod q$ doesn’t imply that $t_s=p$, but $t_s\not\equiv p\mod q\implies t_s\neq p$. So we additionaly check explicity string equality.

In worst case it could be $\Theta((n-m+1)m)$ when all shifts are valid.

In average case we expect only $c$ shifts to be valid, then matching time is $O((n-m+1)+cm)=O(n+m)$ plus time required to process spurious hits. We can expect the number of spurious hits to be $O(n/q)$ since $t_s\equiv p\pmod q$ with probability $1/q$. This makes the expected matching time to be $O(n)+O(m(\nu+n/q))$ where $\nu$ is number of valid shifts. This is $O(n)$ if $\nu=O(1)$ (expected number of valid shifts is small) and $q\ge m$ ($q$ larger than the length of pattern)

Finite Automata

Definition

A finite automaton $M(Q, q_0, A, \Sigma, \delta)$ where

• $Q$: states,
• $q_0\in Q$: start state,
• $A\subseteq Q$: accepting states,
• $\Sigma$: input alphabet
• $\delta:Q\times \Sigma\mapsto Q$: transition function

$M$ induces a function $\phi:\Sigma^*\mapsto Q$ (final-state function) such that $\phi(w)$ is the state $M$ ends up in after scanning the string $w$. $M$ accepts a string $w$ iff $\phi(w)\in A$.

$\phi(\varepsilon)=q_0$

$\phi(wa)=\delta(\phi(w), a)\text{ for }w\in\Sigma^*, a\in \Sigma$

String-matching automata

For $P$ we generate a string-matching automaton in a preprocessing step.

For this we define an auxilary function $\sigma:\Sigma^*\mapsto{0,1,\ldots,m}$, the suffix function corresponding to $P$. $\sigma(x)$ is the length of the longest prefix of $P$ that is also a suffix of $x$.

$\sigma(x)=\max{k: P_k \sqsupset x}$

We have $\sigma(x)=m\iff P\sqsupset x$, also $x\sqsubset y\implies \sigma(x)\le \sigma(y)$ from definition.

We define string-matching automaton as:

• $Q={0,1,\ldots,m}$, $q_0=0$, $A={m}$
• $\delta(q, a)=\sigma(P_qa)$ is the longest prefix of pattern $P$ that has matched the text string $T$ so far.

We consider most recently read characters of $T$. For $T_i=P_j$, $P_j\sqsupset T_i$.

Let $q=\phi(T_i)$. We design $\delta$ such that at $q$, $P_q\sqsupset T_i$ and $q=\sigma(T_i)$. Therefore $\phi(T_i)=\sigma(T_i)$.

If the automaton is in state $q$ and reads the next characters $T[i+1]=a$, then we want the transition to lead to the state corresponding to the longest prefix of $P$ that is a suffix of $T_ia$, i.e. $\sigma(T_ia)$.

Because $P_q$ is the longest prefix of $P$ that is a suffix of $T_i$ , i.e. $P_q=\sigma(T_i)$ we also have the longest prefix of $P$ that is a suffix of $T_ia$ is not only $\sigma(T_ia)$ but also $\sigma(P_qa)$.

• If $a=P[q+1]$, $\delta(q, a)=q+1$.
• If $a\neq P[q+1]$ we find a smaller prefix of $P$ that is also a suffix of $T_i$.

Kunth-Morris-Pratt Algorithm

Given a pattern $P[1..m]$, the prefix function for the pattern $P$ is the function $\pi:{1,2,\ldots, m}\mapsto{0,1,\ldots, m-1}$ such that

$\pi[q]=\max{k:k<q\wedge P_k\sqsupset P_q}$

i.e. $\pi[q]$ is the length of the longest prefix of $P$ that is a proper suffix of $P_q$.

For matching:

• Scan the text $T$ from left to right starting with $q=0$ (number of characters matched is $0$ initially):
  • While $q>0$ and next character doesn’t match, i.e. $P[q+1]\neq T[i]$, keep doing $q\leftarrow\pi[q]$
  • If next character matches, i.e. $P[q+1]=T[i]$, then $q\leftarrow q+1$
  • If $q=m$, pattern is found, and set $q\leftarrow\pi[q]$

      q = 0
      for i = 0 to n - 1:
      	while (k > 0 && T[i] != P[q]):
      		q = pi[q-1]
      	if (T[i] == P[q]):
      		q++
      	if (q == m):
      		# Pattern Found
      		q = pi[q - 1]
      	pi[q] = k
    

For computing prefix-function:

• $\pi[1]\leftarrow0$ by definition

• Scan the pattern $P$ from left to right starting from $q=2$ 2 (loop starts from 2nd character, 1-indexed) and $k=0$ (number of characters matched in 0 initially):

  • While $k>0$ and next character doesn’t match, i.e. $P[k+1]\ne P[q]$, keep doing $k\leftarrow\pi[k]$
  • If next character matches, i.e. $P[k+1]=P[q]$, then $k\leftarrow k+1$.
  • Set $\pi[q]\leftarrow k$

    pi[1] = 0
    k = 0
    for q = 1 to m - 1:
    	while (k > 0 && P[k] != P[q]):
    		k = pi[k-1]
    	if (P[k] == P[q]):
    		k++
    	pi[q] = k
  

Z-Algorithm

The algorithm produces an array $Z$ where $Z[i]$ denotes the length of the longest substring starting from $S[i]$ which is also a prefix of $S$. We refer to prefix-substrings as substrings which are also prefix.

As we iterate over the letters in the string we maintain an interval $[L, R]$ which is the interval with maximum $R$ such that $1\le L\le i\le R$ and $S[L\ldots R]$is a prefix-substring (if no such inteval exists $L=R=-1$)

Now suppose we have correct interval $[L, R]$ for $i-1$ and for all values of $Z$ upto $i-1$, we will compute $Z[i]$ and new $[L, R]$ by following steps:

• $i>R$:
  • there is not a prefix-substring of $S$ that starts before $i$ and ends at $\ge i$. We would have taken that interval instead.
  • Set $[L,R]$ to $[i,i]$ and start comparing $S[0…]$ to $S[i…]$ and $Z[i]=R-L+1$.
• $i\le R$:
  • Let $k=i-L$. We know that $Z[i]\ge \min (Z[k], R-i+1)$
  • $Z[k]<R-i+1$:
    • $Z[i]=Z[k]$
  • $Z[k]\ge R-i+1$:
    • Update $[L,R]$ to $[i,R]$ and start comparing $S[R+1…]$ to $S[k+1…]$

    L = 0
    R = 0
    for i = 1 to n:
    	if (i > R):
    		L = i
    		R = i
    		while (R < n && s[R - L] == s[R]):
    			R++
    		Z[i] = R - L
    		R--
    	else:
    		k = i - L
    		if (Z[k] < R - i + 1):
    			Z[i] = Z[k]
    		else:
    			L = i
    			while (R < n && s[R-L] == s[R]):
    				R++
    			Z[i] = R - L
    			R--
  

For pattern matching we use Z-algorithm on string $P\Phi T$ where $\Phi$ matches nothing Then indices with $Z[i]=m$ correspond to matches in $T$ of $P$.