理解KMP算法

KMP算法是一个快速的匹配算法, 它是对一般的字符串匹配算法的优化, 对其理解, 可以从一般字符串匹配开始!

(1) 一般字符串匹配算法:

int index(char * s, char * t, int pos)
{
int i = pos, j = 0; int sLen = strlen(s); int tLen = strlen(t);

while (i < sLen && j < tLen)
{
     if (s[i] == t[j] )
      { i++; j++; }
     else
      { i = i - j + 1;   j = 0; } // 回溯到起始比较字符的下一个字符
}

if (j == tLen)
    return i - j ; //匹配成功, 返回子串在查找串中的位子!
else
    return 0;
}

这种算法的效率比较低,主要低在回溯那一步, KMP算法,就是针对这点而研究出来的, 具体而言, 它将问题进行了转化, 本来是原串s的回溯, 现在变成了对串t 的规律研究:
假设, s[i] == t[j] 并且 s[i+1] != t[j+1]; 那么我们需要找这样一个j' , 使得t[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）, 同时, j' 当然要越大越好。

新的j可以取多少与i无关，只与t串有关。我们完全可以预处理出这样一个数组Next[j]，表示当匹配到t数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。Next[j]应该是所有满足 t[1..Next[j]] = t [j-Next[j]+1..j]的最大值。

现在假设该Next[]数组已经存在(并且规定Next[1] = 0;), 那么上面的算法按照 KMP的思路可以改成 (这里重写了下):

int Index_KMP(String S,String T,int pos)
{
i=pos;j=1;//这里S和T 串的第1个元素下标是都是1, 这是为了表述的方便
while(i<=S.Length && j<=T.Length)
{
    if(j==0 || S[i]==T[j]) {++i;++j;} //注意到这里的j==0,和++j的作用就知道为什么规定next[1]=0的好处了
    else j=next[j]; // i 不变（不回溯）j 跳动
}
if(j>T.Length) return i-T.Length; // 匹配成功
else return 0;
}

下面主要就是构造Next数组, 根据Next数组的意义, 它本质上是T串的自身部分匹配，那么，我只要将T串和T串自身来一次匹配就可以求出来了，这里的匹配过程不是从头一个一个匹配，而是从T[1]和T[2]开始匹配，考虑到C中习惯于下标从0开始计算, 故这里从T[0], T[1]开始匹配, 其程序为：
void get_next(char * T, int next[])
{
int i = 0, j = -1; next[0] = -1;
while (i < strlen(T))
{
      if (j == -1 || T[i] == T[j])
      { ++i; ++j; next[i] = j;} //每次增加i ,都为next[i]赋值, 该值是T串自匹配时, 已经比较了的下标 j
      else
        j = next[j]; // j 跳回到以前可以匹配的值
}
}

注: T[i]==T[j]以及 i 前面的、j前面的都匹配的情况下，于是先自增，然后记下来next[i]=j，这样每当i有自增就会求得一个next[i]， 而j一定会小于等于i，于是对于已经求出来的next，可以继续求后面的next，而next[1]=0是已知，所以整个就这样递推的求出来了，方法非常 巧妙。

注意到下面的匹配情况：

...aaac...
   aaaa.
T串中的'a'和S串中的'c'失配，而'a'的next值指的还是'a'，那同样的比较还 是会失配，而这样的比较是多余的，如果我事先知道，当T[i]==T[j]，那next[i]就设为next[j]，在求next值的时候就已经比较了， 这样就可以去掉这样的多余的比较。于是稍加改进得到：

void get_nextval(char * T,int next[])
{
int i=0, j = -1; next[0]= -1;
while(i< strlen(T))
{
    if(j == -1 || T[i]==T[j])
    { ++i;++j;
      if(T[i]!=T[j]) next[i]=j;
      else next[i]=next[j];//消去多余的可能的比较,next再向前跳 (这里j 肯定是小于i的)
    }
    else j=next[j];
}
}

匹配算法不变。

附: 优化 get_nextval() 前后, next数组中的值对比:
int main()
{
     char p[] ="abababcdabcd";
     int next[256];
     int i;
    get_nextval(p,next);
     printf("The length of P:%d\n",strlen(p));
     for(i=0;i         printf("next[%d]:%d\n",i,next[i]);

    return 0;
}

优化前的值:
C:\zyf\C_C++>kmp
next[0]: -1
next[1]: 0
next[2]: 0
next[3]: 1
next[4]: 2
next[5]: 3
next[6]: 4
next[7]: 0
next[8]: 0
next[9]: 1
next[10]: 2
next[11]: 0

优化后的值:
C:\zyf\C_C++>kmp
next[0]: -1
next[1]: 0
next[2]: -1
next[3]: 0
next[4]: -1
next[5]: 0
next[6]: 4
next[7]: 0
next[8]: -1
next[9]: 0
next[10]: 2
next[11]: 0