字符串

一、Kmp模式匹配

（1）問題描述

有兩個分別叫做A和B的字符串，它們的長度分別為N,M。

求出A是否為B的子串，如果是，求出A在B中每次出現(xiàn)的位置（最后一位）

（2）算法描述

①def

我們定義一個next數(shù)組。形式化來說，next的第i位就是A的前綴子串和以第i位為結(jié)尾的非前綴子串可以相等的最長長度。（偽代碼定義下圖）

再定義一個j數(shù)組。形式化來說，j的第i位就是A的前綴子串和以第i位為結(jié)尾的B的子串可以相等的最長長度。（偽代碼定義下圖）

?

根據(jù)j的定義，我們可以知道當(dāng)j數(shù)組的某一位的值為N時，A為B的子串且這次出現(xiàn)的最后一位為i。

②優(yōu)化

顯然，直接暴力next數(shù)組的復(fù)雜度并沒有達(dá)到算法的要求。為了優(yōu)化算法效率，我們需要進(jìn)行優(yōu)化。

首先，我們定義next的第i位的所有can為它的“候選項(xiàng)”。

引理一：next的第i位的所有can根據(jù)從大到小的排序方式，分別為j，next[j]，next[next[j]]，etc.、

//證明：當(dāng)next數(shù)組的前j位和以i結(jié)尾的后j位相等時，next數(shù)組的前x位和以next[i]位結(jié)尾的x位相等，因?yàn)樗麄冊趎ext[i]的計算過程中重疊（形式化如下圖）

?

以上是kmp的算法描述，下一篇中我將寫一個kmp例題的題解。? ?