学点字符串匹配—

学点字符串匹配——kmp算法

　　kmp被分类成基于前缀搜索的匹配算法，把模式串（要寻找的串）当作一个滑动窗口在匹配串上滑动，匹配顺序是从左到右。不论是基于前缀搜索，基于后缀搜索，还是子串搜索，每次失配向后移动多个字符好像是这些单串匹配算法的共同特点。kmp的思想是每次失配或者匹配成功进行下一次匹配的时候，不像暴力那样只移动一个字符之后重模式串头部匹配，而是每次最优的向后移动多个字符并且之后可以从失配的地方开始匹配。

　　为了实现这个，kmp初始化了每个模式串前缀的最大边界，即代码中的nextjmp[],存的是边界作为模式串前缀的末尾下标。所谓字符窜的边界，是指既是字符窜的前缀又是字符窜的后缀的真子串（不能是本身，否则相当于滑动窗口没有移动）。用这个边界来进行失配后的模式串移动，移动后直接重匹配串的失配处开始和模式串的length[边界]个字符之后开始匹配，因为很明显该边界已经在匹配串上匹配过了，不需要再次匹配。

　　先介绍下代码，InitKmp()是对nextjmp数组的初始化，Kmp()函数是kmp算法的匹配过程。代码中用MatchingInfo这个结构保存搜集到的匹配信息。变量patternString是模式串，dataString是匹配串，psLen，idxPs是模式串的长度和下标的记录，dsLen和idxDs是对匹配串的类似描述。

　　下面的Kmp()函数可以这样理解：当前正在匹配下标为 idxDs的字符，for循环内的while循环正在寻找一个能匹配到idxDs上的模式串前缀，相当于同时滑动模式串，while循环结束的时候如果 idxPs==-1（模式串前缀为空），如果idxPs != -1（模式串长度为idxPs + 1）。下一行如果idxPs自加1说明idxDs处的字符已经匹配上，已经匹配上的模式串长度加1（模式串前缀长度加1），否则必然是模式串前缀为空。这时下一个匹配串字符对应模式串做匹配的初始位置也已经确定，等待下一个循环中的调整。

nextjmp的求法是模式串匹配模式串的过程，也像是一个动态规划的过程：

1 if((patternString[k + 1] == patternString[i])) 
2     nextjmp[i] = k + ((patternString[k + 1] == patternString[i]) ? 1 : 0);
3 //其中 k = nextjmp[i - 1], nextjmp[nextjmp[i - 1]], ...直到k == -1.
4 //找到满足条件的第一个k
5 //这时已匹配的模式串前缀最长，而且模式串窗口滑动的距离最小，不会遗漏一个解

　　kmp匹配过程的复杂度是O(n+m),n为匹配串长度，m为模式串长度。初始化过程和匹配主过程的复杂度主要看62行的代码：

1 while(idxPs != -1 && patternString[idxPs + 1] != dataString[idxDs])  idxPs = nextjmp[idxPs];

　　此处idxPs是持续减小的，直到匹配串匹配上模式串刚刚失配的字符或者边界为空， idPs最小是-1。而63行的idxPs最多自加1，由于主循环会循环n次，idxPs至主循环结束最多增加到n，所以while循环的次数最多不会超过n次，均摊到每个循环只有O(1)。所以kmp的复杂度是线性的。

1 if(patternString[idxPs + 1] == dataString[idxDs]) ++idxPs;

上代码吧～

 1  /*
 2  *kmp.h : this file is a presentation of KMP algorithm in C
 3 
 4  *write by zuanyg at 2012.12.28
 5 
 6  *
 7  *
 8  *
 9   */
10 
11 
12 #include <stdio.h>
13 #include <stdlib.h>
14 #include <string.h>
15 
16 typedef struct MatchingInfo
17 {
18     unsigned int numOfMatch;
19     unsigned int allocLen;
20     unsigned int *indexOfMatch;
21 }MatchingInfo;
22 
23 void FreeMatchingInfo(MatchingInfo *mi);
24 static void InitKmp(int *nextJmp, char *patternString);
25 MatchingInfo * Kmp(char *patternString, char *dataString, unsigned int dsLen);

 1  /*
 2  *kmp.c : this file is a presentation of KMP algorithm in C
 3 
 4  *write by zuanyg at 2012.12.28
 5 
 6  *
 7  *
 8  *
 9   */
10 #include "kmp.h"
11 
12 void FreeMatchingInfo(MatchingInfo *mi)
13 {
14     if(mi == NULL) return;
15     free(mi->indexOfMatch);
16     mi->indexOfMatch = NULL;
17     free(mi);
18     mi = NULL;
19 }
20 
21 static void InitKmp(int *nextJmp, char *patternString)
22 {
23     int idxPs = -1, idxDs = 0;
24     int psLen = strlen(patternString);
25     int dsLen = psLen;
26 
27     nextJmp[0] = -1;
28     for(idxDs = 1; idxDs < dsLen; ++idxDs)
29     {
30         //this is just like the main process of kmp
31         while(idxPs != -1 && patternString[idxPs + 1] != patternString[idxDs])
32         {
33             idxPs = nextJmp[idxPs];
34         }
35         if(patternString[idxPs + 1] == patternString[idxDs]) ++idxPs;
36         nextJmp[idxDs] = idxPs;
37     }
38 
39     return;
40 }
41 
42 MatchingInfo * Kmp(char *patternString, char *dataString, unsigned int dsLen)
43 {
44     unsigned int psLen = strlen(patternString);
45     MatchingInfo *mi = NULL;
46     int *nextjmp = NULL;
47 
48     mi = (MatchingInfo *)malloc(sizeof(MatchingInfo));
49     nextjmp = (int *)malloc(psLen * sizeof(int));
50 
51     if(nextjmp == NULL || mi == NULL) return NULL;
52     InitKmp(nextjmp, patternString);
53 
54     mi->indexOfMatch = (unsigned int *)malloc(sizeof(unsigned int));
55     mi->numOfMatch = 0;
56     mi->allocLen = 1;
57 
58     int idxPs = -1, idxDs = 0;
59 
60     for(idxDs = 0; idxDs < dsLen; ++idxDs)
61     {
62         while(idxPs != -1 && patternString[idxPs + 1] != dataString[idxDs])  idxPs = nextjmp[idxPs];
63         if(patternString[idxPs + 1] == dataString[idxDs]) ++idxPs;
64         if(idxPs + 1 == psLen)  //得到一组匹配，记录开始处下标
65         {
66             if(mi->allocLen > mi->numOfMatch)
67             {
68                 mi->indexOfMatch[mi->numOfMatch++] = idxDs - psLen + 1;
69             }
70             else
71             {
72                 //realloc the MatchingInfo, and realloc a little more
73                 mi->indexOfMatch = (unsigned int *)realloc(mi->indexOfMatch, (mi->allocLen << 1) * sizeof(unsigned int));
74                 mi->allocLen <<= 1;
75                 mi->indexOfMatch[mi->numOfMatch++] = idxDs - psLen + 1;
76             }
77             idxPs = nextjmp[idxPs];
78         }
79     }
80 
81     free(nextjmp);
82     nextjmp = NULL;
83 
84     return mi;
85 }

欢迎批评指正，欢迎交流，大牛轻喷，只是写下自己的理解。