0%

# KMP

KMP algorithm is an improved version of pattern matching. It’s reduced the number of repeated mathcing.

## Partial Match Array

### Define

Prefix string: All header substrings of a string except the last character.

Suffix string: All trailing substrings of a string execept the first character.

PM: PM is the maximum length of string at the intersection of prefix and suffix string.

Index 1 2 3 4 5
S=”ababa” a b a b a
PM 0 0 1 2 3
1. ‘a’: $pre=suf=\varnothing$, PM = 0.
2. ‘ab’: $pre={a}, \ suf={b}, \ pre \cap suf = \varnothing$, PM = 0.
3. ‘aba’:$pre={a,ab}, \ suf={a,ba}, \ pre \cap suf = {a}$, PM = 1.
4. ‘abab’:$pre={a,ab,aba}, \ suf={b,ab,bab}, \ pre \cap suf = {ab}$, PM = 2.
5. ‘ababa’:$pre={a,ab,aba,abab}, \ suf={a,ba,aba,baba}, \ pre \cap suf = {a,aba}$, PM = 3.

### Matching Process

j is mathcing pointer position of current substring.

The number of digits moving to the right = The number of characters have been matched - PM value of corresponding section.

Index 1 2 3 4 5
S=”abcac” a b c a c
PM 0 0 0 1 0

step 1:

a b a b c a b c a c b a b
a b c

step 2:

a b a b c a b c a c b a b
a b c a c

step 3:

a b a b c a b c a c b a b
a b c a c

## Principle

a b a b c a b c a c b a b
a b c
a b c a c
a b c a c

For PM, when matching failed, we query the PM value of previous element. We move the PM values one place to right, this new array is called Next, we use -1 to fill in the first place. Now we can use Next value of current position when matching failed.

Index 1 2 3 4 5
S=”abcac” a b c a c
Next -1 0 0 0 1

So we can simplify the formula. Add 1 to all values in Next.

Index 1 2 3 4 5
S=”abcac” a b c a c
Next 0 1 1 1 2

## Get Next

We can get it form the previous PM, but it’s too troublesome.

k means it’s being compared to the k-th character in the pattern string. i is the current matching pointer of main string.

Here refer to the calculation of PM value. PM is the maximum value, so they’re the same when it doesn’t reach the maximum.

The strings in parentheses are the same.

$s_1$ [… …] [$s_{i-k+1}$ $s_{i-1}$] $s_i$ $s_n$
[$p_1$ $p_{k-1}$] [$p_{i-k+1}$ $p_{j-1}$] $p_j$ $p_{m}$
[$p_1$ $p_{k-1}$] $p_k$ $p_{m}$

## References

KMP 算法之求 next 数组代码讲解