KMP算法(1)

qq1242009750

KMP算法是字符串搜索算法中最高效的算法。
之所以说它高效是因为在目标串中加入了回溯下标，使其在失配时能迅速重新匹配，那接下我们分析一下BF和KMP吧。
BF算法 它在失配的时候目标串会从头开始匹配，而源串则会移动到下一个待匹配的元素上
BF：

BF工作介绍

从上面我们可以得知这样如此的重复匹配导致了时间复杂度增加 O(mXn)   m：源串   n:目标串
而KMP算法呢，正因为有了Next数组，所以在失配时只需要回溯查找就OK啦。
那KMP算法Next是怎样得出来的呢？ 哈哈，其实也很简单，只要记住这句话就可以啦：Next串中前一个目标字符的匹配度决定下一个字符的Next串元素。
KMP：

Kmp

1. void Get_Next(char *t ,int *next)
   
2. {
   
3.         int i/*前*/ = 0, j/*后*/ = 1;
   
4.         next[1] = 0;
   
5.         while (j < t[0])
   
6.         {
   
7.                 if (0 == i || t[i] == t[j])
   
8.                 {
   
9.                         ++i;
   
10.                         ++j;
    
11.                         next[j] = i;
    
12.                 }
    
13.                 else
    
14.                 {
    
15.                         i = next[i];                //回溯工作
    
16.                 }
    
17.         }
    
18. }

复制代码

kMP_Next

从上面的工作图中我们可以看出红色方框倒数第一个元素的Next值完全是由前一个目标串与Next决定的。