KMP算法学习

2016-08-08 · 3 min read · kmp

20170801update:当时竟然没有强调next函数的含义？

next[i]的含义是,i之前的整个前缀中，最长的该前缀的前缀和后缀相同的长度。

看图：

KMP感觉是我学到现在最难懂的一个算法了QAQ 为什么你们都那么强啊，看几个小时就看懂了...

先放一波我觉得值得看的资料： kmp算法讲解（配图比较全....） kmp学习资料2

说下我对kmp算法的理解：

理解kmp算法大概分成两个部分。

一部分是理解一个naive的kmp算法，可以叫"fast slide" algorithm

思想大概就是，当mismatch发生时，我们并不是一无所有，而是知道在mismatch发生前所匹配的字符的信息的。

然后知道这些信息我们可以做什么呢？

先观察一下最最暴力的求解字符串匹配的算法：

1//***********************************************************
2//brute force 
3 n = T.length();
4      m = P.length();

1      i0 = 0;              // Line P up with the first character of T       
2      i = 0;               // Start matching with first char in T
3      j = 0;               // Start matching with first char in P

1      while ( i < n )     // Not all characters used
2      {
3         if ( T[i] == P[j] )
4         {
5            /* ===============================================
6	       T[i] and P[j] match ==> try next pair
7	       =============================================== */
8            i++;           // Match next pair
9            j++;

 1            if ( j == m )
 2               return ( i0 );    // Match found at position i0 !!!
 3         }
 4         else
 5         {  /* ===========================================
 6               T[i] ≠ P[j]:
 7                  1. Slide P up 1 position
 8		  2. restart from beginning of string
 9               =========================================== */
10            i0 = i0 + 1;   // Slide pattern P one character further

1            i  = i0;       // Restart matching at position i0 in T
2            j  = 0;        // Restart matching at position 0 in P
3         }
4      }

      return -1;           // Return not found
   }

这个算法低效在，当mismatch发生时，我只是往前移动了一个字符。

因此我们定义了 maxoverlap函数。。

需要特别强调的是：

这样我们就可以利用maxoverlap函数来优化当mismatch发生的时候，移动的过程。

1  KMP( T,  P )
2   {
3      int i0, i, j, m, n;

      n = T.length();
      m = P.length();

1      i0 = 0;              // Line P up with the first character of T
2      i = 0;               // Start matching with first char in T
3      j = 0;               // Start matching with first char in P

1      while ( i < n )     // Not all characters used
2      {
3         if ( T[i] == P[j] )
4         {
5            i++;           // Match next pair
6            j++;

1            if ( j == m )
2               return ( i0 );    // Match found atposition i0 !!!
3         }
4         else
5         {  /* ===========================================
6	       T[i] ≠ P[j]
7               =========================================== */

 1             if ( j == 0 )
 2	     {  /* ==============================================
 3	           First character already mismatched
 4		   We have NO prefix info. to work with...
 5		   =============================================== */
 6	        i0++;        // Just slide P 1 character over
 7		i = i0;      //
 8		j = 0;
 9             }
10	     else
11             {
12	        prefix = P[ 0..(j-1) ];  // Prefix of pattern at the mismatch

	        k = MaxOverlap( prefix );

1	        j = k;
2	        i0 = (i - j);
3		// i is unchanged !
4             }
5         }
6      }

      return -1;           // No match found
   }

这样我们就得到了**"fast slide" algorithm算法**

但是。。。能不能再给力一点呢

我们发现，上述代码中，我们每次都要计算一次maxoverlap函数...

但是。。一个字符串。。。它的子串个数是有限的。。。

我们能不能加速这个过程呢。。。

很容易想到预处理一波。。。

也就是求所谓的failure function ,中文应该叫失配函数...

所以第二部分就是如何快速求出失配函数

这也是我认为的kmp算法最精(nan)髓(dong)的地方。