# KMP算法学习

Posted by 111qqz on Monday, August 8, 2016

## TOC

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

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

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

``````//***********************************************************
//brute force
n = T.length();
m = P.length();

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

while ( i < n )     // Not all characters used
{
if ( T[i] == P[j] )
{
/* ===============================================
T[i] and P[j] match ==> try next pair
=============================================== */
i++;           // Match next pair
j++;

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

i  = i0;       // Restart matching at position i0 in T
j  = 0;        // Restart matching at position 0 in P
}
}

}
``````

``````  KMP( T,  P )
{
int i0, i, j, m, n;

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

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

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

if ( j == m )
return ( i0 );    // Match found atposition i0 !!!
}
else
{  /* ===========================================
T[i] ≠ P[j]
=========================================== */

if ( j == 0 )
{  /* ==============================================
We have NO prefix info. to work with...
=============================================== */
i0++;        // Just slide P 1 character over
i = i0;      //
j = 0;
}
else
{
prefix = P[ 0..(j-1) ];  // Prefix of pattern at the mismatch

k = MaxOverlap( prefix );

j = k;
i0 = (i - j);
// i is unchanged !
}
}
}

return -1;           // No match found
}
``````

「真诚赞赏，手留余香」