在开发中常常遇到须要查看一个字符串t是否在字符串s中存在，并找到其第一次出现的位置，也就是在字符串s中查找子串t，我们寻常都是怎么实现那？我们最起码有三个方法能够用。CString和string中的find函数。以及string.h中的strstr函数，用起来既简单又快捷，CString是MFC中的东西，string是C++标准库的东西，strstr是C中string.h中的东西。貌似我们不是必需非要自己实现定位查找功能……可是假设我偏要想自己实现那？我们能不能模仿MFC中的CString或者C++中的string和string.h中的strstr来自己实现一个函数那？以下我们慢慢来找一找，看看能不能实现。
1. 朴素模式匹配
假如s=”ababcababcac”，t=”abcac”。在s中查找t；我们能够最直接想到的办法就是直接拿t中每个字符和s中的每个字符一一进行比較，例如以下：
从比較过程中我们能够发现每次比較失败后，i和j都会回溯；不停得回溯不停得比較。时间复杂度、为O(mn)；算法十分简单。也非常easy实现。代码例如以下：
int BFMatcher(const char* strMain,const char* strSub){ int n = strlen(strMain); int m = strlen(strSub); int j = 0; int i=0; while ( i 2. KMP算法
依据上面的步骤我们细致看第一步和第二步会发现。我们在第一步中比較s中的a和t中的c失败后。第二步直接从第一步中已经比較的过的s中的b開始与t中的第一位a比較。我们通过第一步已经知道s中的第二个是b。不可能与t中的第一位a相等，这一步比較全然是多余的。咱们实现的上面的简单方法全然没有利用第一次比較过得结果，这叫什么，叫没吸取经验，在第二步比較时我们应该利用第一步的比較结果，假设我们利用了比較结果。全然就能够跳过第二步，明显的节省了时间，第一步和第二步的比較应该为以下这样：
依照这种方法来的话，我们这个比較四步也就成功找到t在s中的位置，避免了i和j的反复回溯。比上面的方法不知道快了多少倍。
但是这个样例看起来简单，但是怎么编程实现那？怎么让它一般化那？我们先来看第二步是怎样到达第三步的：
第二步比較開始时i为s中第三个字符a的位置，即i=2；t中j=0；当比較到i=7，j=4时不相等了，比較失败，在第三步时我们发现s中起始比較的位置仍然为i=7不变，t中j的位置变成了1，在第二步中我们发现，”abca”成功在s中找到了位置，我们比較s[6]与t发现。s[6]=t[3]，同一时候s[6]=t[0]；所以在第三步中s[6]和t[0]就无需进行比較。我们通过观察”abca”和t[0]t[3]能够发现。t[0]和t[3]各自是”abca”的真前缀和真后缀，t[0]=t[3]。那么是不是说我们仅仅要找到已经在s匹配成功的t中的串t[0…q]中的相等的真前缀和真后缀的长度。我们就能够知道。下次比較t中j的起始位置那？比方刚刚在第二步中得到的”abca”的真前缀的长度为1，那么下次比較j的位置就为1。由此可知，比較失败后，s中的i不用动。仅仅须要获取下一个j即可，而且这个j的仅仅与s没有关系。
那么我们来总结下，如果s串长度为n，t串长度为m，m<=n，在s中查找t，t[1…q] =s[i+1…i+q] 0<q<m（注:在上面的样例中第二步中,i=2,q=4。这里的t[1…q]表示的是从t[0]到t[q-1]的元素）。且t[1…q+1]!= s[i+1…i+q+1]。而且有t[1…k]=s[i`+1…i`+k]1<k<q i+1 <i`<i+q，当中i`=i+q-k。那么我们后面的匹配測试中就会变得十分的简单。由此可知我们主要求出这个k值就能够了。也就是求出t[1…q]中的最大真前缀的长度即可，这个长度的值就是下一个j的值。
以下的问题就是获取失败后的下一个j，也就是怎么找t[1…q]中的最大真前缀。
能够看到1<q<m，所以我们须要获取t[1…1]到t[1…m]中全部串的最大的真前缀，所以能够直接把这些最大真前缀的长度提前求出放到一个数组next[]中。以供使用。
有了这个next数组之后就能够写出查找函数例如以下:
int KMP_Matcher(const char* strMain,const char* strSub){ if ( NULL == strMain || NULL == strSub ) return -1; int n = strlen(strMain); int m = strlen(strSub); int next[MAX_STRING_LEN] = {0}; GetNext(strSub,next); int q = 0; for ( int i=0 ; i 0 && strSub[q]!=strMain[i] ) q = next[q]; if ( strSub[q] == strMain[i] ) q = q+1; if ( q==m-1 ) return i-q+1; } return -1;} 如今我们就仅仅须要想办法怎么实现这个GetNext函数填充next数组：
我们能够知道next[1]=0。由于t[1…1]没有真前缀。由此能够考虑用递归的方式来实现对next数组的求解。对于q>1。如果已知next[1],next[2],next[3],next[4]……next[q-1]中全部串的最大真前缀的长度。那么next[q]那？设next[q-1]=k。那么t[1…k]是t[1…q-1]中的最大真前缀。因此我们对t[q]如果两种情况:
1. t[k+1]=t[q]，那么这就简单了。这样说明串t[1…k]的后一位与t[1…q-1]的后一位是相等的。已知next[q-1]=k，那么next[q]=k+1。
2. t[k+1]!=t[q]，那么就找t[1…q-1]的第二大真前缀，由于t[1…k]是t[1…q-1]的最大真前缀，所以t[1…k]的最大真前缀就是t[1…q-1]的第二大真前缀。所以此时不相等就是求t[1…k]的最大真前缀，即next[ next[q-1] ] = next[k]；这是就变成了k=next[k]，比較t[next[k]+1]和t[q]。若还不相等，则反复此步骤，直到next[k]=0；j的值回溯到0从头開始匹配。
通过上面两步便可求出next数组。
代码实现例如以下:
void GetNext(const char* str,int* next)//abcac{ next[0] = 0; int m = strlen(str); int k = -1; for ( int q=1 ; q 0 && str[k+1] != str[q] ) k = next[k]; if( str[k+1] == str[q] ) next[q] = ++k; else next[q] = 0; }} 通过上面代码我们能够发现，能够通过对k的初始值调整。得到更加简短的实现，例如以下： void GetNext(const char* str,int* next){ next[0] = 0; int m = strlen(str); int k = 0; for ( int q= 1; q 0 && str[k] != str[q] ) k = next[k]; if ( str[k] == str[q] ) k = k+1; next[q] = k; }} 3. KMP时间复杂度计算
要计算KMP_Matcher的时间复杂度，首先要计算GetNext的时间复杂度，由代码可知，GetNext中的for循环的时间复杂度为m，而for中的while循环那？？能够看到，while循环受k>0限制。k由大于next[k]。也就是说while循环中的操作是以至少1的速度减小k的值，而k的值又是受for中k=k+1限制，k值为零while循环不会做不论什么操作，所以while循环受for循环约束，while循环内减小k值后，若k值不添加。while循环就不会做不论什么操作，所以GetNext的时间复杂度为O(m)。同能够推出KMP_Matcher的时间复杂度为O(m+n)。
终于完整的代码例如以下：
#include參考:《算法与数据结构》 傅清祥、王晓东#include #define MAX_STRING_LEN 255void GetNext(const char* str,int* next){ next[0] = 0; int m = strlen(str); int k = 0; for ( int q= 1; q 0 && str[k] != str[q] ) k = next[k]; if ( str[k] == str[q] ) k = k+1; next[q] = k; }}int KMP_Matcher(const char* strMain,const char* strSub){ if ( NULL == strMain || NULL == strSub ) return -1; int n = strlen(strMain); int m = strlen(strSub); int next[MAX_STRING_LEN] = {0}; GetNext(strSub,next); int q = 0; for ( int i=0 ; i 0 && strSub[q]!=strMain[i] ) q = next[q]; if ( strSub[q] == strMain[i] ) q = q+1; if ( q==m-1 ) return i-q+1; } return -1;}int main(int argc, char* argv[]){ int nIndex = KMP_Matcher("aaababcacabcac","abcacab"); printf("nIndex=%d",nIndex); getchar(); return 0;}