串匹配问题是计算机科学中的一个基本问题，在文字编辑、图像处理等利于都得到了广泛的应用，串匹配算法在这些应用中起到至关重要的作用。因此研究快速的串匹配算法具有重要的理论和实际意义。
KMP是一种改进的字符串模式匹配的算法，他能够在o(m+n)时间复杂度内完成字符串的模式匹配算法。本文将详细的介绍KMP算法的思想，串行及并行实现。
一、KMP算法思想
1、问题描述
给定主串S[0...n-1]、模式串T[0...m-1]，其中m<=n。在主串S中找出所有模式串T的起始位置。
2、算法思想
令指针i指向主串S，指针j指向模式串T中当前正在比较的位置。令指针i和指针j指向的字符比较之，如两字符相等，则顺次比较后面的字符；如不相等，则指针i不动，回溯指针j，令其指向模式串T的第pos个字符，使T[0...pos-1] == S[i-pos, i-1],然后，指针i和指针j所指向的字符按此种方法继续比较，知道j == m-1，即在主串S中找到模式串T为止。
从算法的思想思想中我们可以看出，其算法的难点在于如何求出指针j的回溯值，即：当指针j回溯时，j将指向的位置，我们几位next[j]。下面我们首先对kmp的算法做出详细的描述。
二、KMP算法描述
输入：主串S[0...n-1], 模式串T[0...m-1]
输出：m[0...n-1],当m[i] = 1时，则主串S中匹配到模式串，且i为起始位置
begin
i = 0； j = 0;
while(i < n)
if(S[i] != T[j])
j = next[j]
if( j == -1)
i++ j++
endif;
contiue;
endif
if (j == m-1)
m[i-j+1] = 1
j = -1
i = i-j+1
endif
i++ j++
end while
end
在上面的算法描述中，next函数的编写为整个算法的核心，设计出快速正确的next函数也为KMP算法的重中之重。如何设计我们的next函数呢，我们利用递推思想：
1）令next[0] = -1，（为什么要等于-1呢，从上面的算法可以看出，当next[j] == -1时，证明字符串匹配要从模式串的第0个字符开始,且第0个字符并不和主串的第i个字符相等，i指针向前移动。）
2）假设next[j] = k ,说明T[0..k-1] == T[j-k...j-1]
3) 现在我们来求next[j+1]
3.1 当T[j] == T[k]时,说明T[0..k] == T[j-k..j],这时分为两种情况讨论：
3.1.1 当T[j+1] != T[k+1]，显然
next[j+1] = k+1;
3.1.2 当T[j+1] == T[k+1]，当这两个字符相等时，说明T[k+1]和T[j+1]一样，都不和主串的字符相匹配，因此：
m = k+1, j=next[m] 直到T[m] != t[j+1]
next[j+1] = m
3.2 当T[j] != T[k]时,我们必须在T[0..k-1]中找到next[j+1],这时：
k = next[k],直到T[j] ==T[k]
next[j+1] = next[k]
这样我们就通过数学中递推的方式求得了匹配串T的next函数。
三、串行实现
有了以上的算法描述，我们可以编写我们的kmp串行实现，本文不想黏贴过多的代码，仅仅给出next函数的实现：
1: int *get_next(char *match_string, int match_string_length){
2:
3: int *next;
4: int next_index;
5:
6: int i;
7:
8: next = (int *)my_malloc(sizeof(int) * match_string_length);
9:
10: next[0] = -1;
11: i =0;
12: next_index = -1 ;
13:
14: while(i < match_string_length){
15:
16: if(next_index == -1 || match_string[next_index] == match_string[i]){//对应于3.1
17: i++;
18: next_index++;
19:
20: if(match_string[i] != match_string[next_index])//对应于3.1.1
21: next[i] = next_index;
22: else//对应于3.1.2
23: next[i] = next[next_index];
24: }
25: else//对应于3.2
26: next_index = next[next_index];
27: }
28:
29: return next;
30: }
四：并行算法
现在我们考虑如何将KMP算法并行化，我们很容易考虑到得是将主串S平均分成P段（假设有p个处理器），每个处理器处理其中的一段。但这时要考虑一个问题，那就是如何处理每段字符串最后m-1个子字符串的匹配问题，因为这m-1个字符可能会和其后一段的前t个字符共同构成模式串。我们首先考虑到得是每个处理器将其负责字符串的后m-1个字符的字串发送给其后面的处理器，但这样会造成通信过大的问题，每个处理器都要发送m-1个字符。如何减少处理器间的通信呢？起始我们只需发送和模式串前t个字符想匹配的t个字符就可以了。这样就减少了进程间的通信。其算法描述如下：
输入:主串T[0...n-1],模式串S[0...m-1]
输出：m[0...n-1],当m[i] = 1时，则主串S中匹配到模式串，且i为起始位置
条件：t个处理器
1）p0读取主串和模式串，将模式串广播到起到所有的处理器中，并将主串分段发送到其对应的处理器中
2）处理器并行计算next函数，这样每个处理器都有统一的next函数和模式串
3）处理器p0 ,p1,...,pt-1并行计算各自负责字符串的后m-1个字符的字串和模式串的最小匹配串，并将最小匹配串发往下一个处理器
4）处理器接收上个处理器发送的字符串，并和本身的字符串合并成一个新的字符串
5）各处理器并行计算匹配结果m
6）处理器p0对各处理器的匹配结果进行整合，得到最终结果。
因为kmp并行算法相对简单，也没有用到新的MPI函数，这里不列出其并行实现代码。
下一篇：图论：单源最短路径的并行算法