给定两个字符串s和t，在主字符串s中寻找部分字符串t的过程称为串匹配string
matching，也称为模式匹配)，t称为模式。 这里介绍处理字符串匹配问题的两个算法，BF算法和KMP算法。
BF算法(暴力匹配算法)
BF算法概要f(bruteforce )算法是一种常用的模式匹配算法，BF算法的思想是将目标列s的第一个字符与模式列t的第一个字符进行匹配，如果相等，则继续比较s的第二个字符和t的第二个字符如果不相等，则将s的第二个字符与t的第一个字符进行比较，依次进行比较直到得到最后的一致结果。
BF算法的原理首先，给出“主字符串”和“模式字符串”如下。
BF算法使用简单粗暴的方法，逐字符比较主字符串和模式字符串：
如果检测到字符不一致，则将模式列向后移动一位，与主列的第二个等长子列进行比较。
当检测到字符不一致时，图案列进一步向后移动一位，与主列的第三个子列进行比较
重复上述步骤直到匹配成功或匹配失败。 也就是说，它在主字符串的末尾结束。
算法intBF(char*s，char* T ) (intslen=Strlen ) s )； //字符串长度inttlen=strlen(t )； //图案列长int i=0； int j=0； while(Islenjtlen ) if(s(I )=t (j ) ) /当前字符匹配成功的情况)即s ) I )==t (j ) )时，I，j i； j； (else )//失配)也就是说S[i]！=T[j] )、I=I-(j-1 )、j=0 i=i - j 1； j=0； //匹配成功，返回图案列t在文本列s中的位置。 否则-1if(j==Tlen ) return i - j； else return -1； }测试# include stdio.h # include stdlib.h # include string.hint BF (char * s，char* T ) intslen=strlen ) s； //字符串长度inttlen=strlen(t )； //图案列长int i=0； int j=0； while(Islenjtlen ) if(s(I )=t (j ) ) /当前字符匹配成功的情况)即s ) I )==t (j ) )时，I，j i； j； (else )//失配)也就是说S[i]！=T[j] )、I=I-(j-1 )、j=0 i=i - j 1； j=0； //匹配成功，返回图案列t在文本列s中的位置。 否则-1if(j==Tlen ) return i - j； else return -1； }int main () chars ()='ABCABCDabABCDABCDABDW )； char T[]='ABCDABD '； int num； char *ch=T； num=BF(s，t )； if(num=0) printf(matched@:%sn )，ch )； }else{printf('matchedfail！ n '； } return 0； }执行结果：
matched @ : ABCD Abd http://www.Sina.com/: BF算法是一种比较直接、无力的方法。 该算法最坏情况下进行了m*(n-m1 )次比较，时间复杂度为o ) m*n )。 以下，我们来看一下非常高效的字符串匹配算法(即kched )
之所以将KMP算法KMP算法的概要称为KMP，是因为该算法是由Knuth、Morris、Pratt个提出的，取了这3个人的名字的首字母。 KMP算法的关键是利用匹配失败后的信息，尽量减少模式列和主列的匹配次数，实现快速匹配。 具体来说，就是实现包含模式列的本地匹配信息的next (函数。 时间复杂度o(mn )。
简单地说，KMP算法是为了处理字符串匹配而带来的。 换句话说，如果给定两个字符串，则需要回答b列是否是a列的子列
（A串是否包含B串）。 KMP算法原理（参考自：看，未来的博客）
首先，给定 “主串” 和 “模式串” 如下：
第一轮，模式串和主串的第一个等长子串比较，发现前5个字符都是匹配的，第6个字符不匹配，是一个“坏字符”：
这时候，我们可以有效利用已匹配的前缀 “GTGTG” 。通过观察我们可以发现，在前缀“GTGTG”当中，后三个字符“GTG”和前三位字符“GTG”是相同的：
在下一轮的比较时，只有把这两个相同的片段对齐，才有可能出现匹配。这两个字符串片段，分别叫做最长可匹配后缀子串和最长可匹配前缀子串。
第二轮，我们直接把模式串向后移动两位，让两个“GTG”对齐，继续从刚才主串的坏字符A开始进行比较：
显然，主串的字符A仍然是坏字符，这时候的匹配前缀缩短成了GTG：
按照第一轮的思路，我们来重新确定最长可匹配后缀子串和最长可匹配前缀子串：
第三轮，我们再次把模式串向后移动两位，让两个“G”对齐，继续从刚才主串的坏字符A开始进行比较：
·········接下来还是重复步骤，就不往写了。
什么是next数组？next数组用来干什么？
next数组是决定kmp算法快速移动的核心。
next数组的生成示例：
说白了就是把子串拆分，然后看尾部有多少个字符重复，没有写-1，有一个就写0，有两个写1，依次类推（你也可以写0，1，2，具体想写啥看个人吧，我这里只是全部减1了，当然在代码里也要记得修改）。
有了next数组，我们就可以通过已匹配前缀的下一个位置（坏字符位置），快速寻找到最长可匹配前缀的下一个位置，然后把这两个位置对齐。
算法 void compute_prefix(const char *pattern, int next[]){ int i; //前缀 int j = -1; //前缀尾巴 const int m = strlen(pattern); next[0] = j; for (i = 1; i < m; i++) { while (j > -1 && pattern[j + 1] != pattern[i]) //前后缀不相等 { j = next[j]; } if (pattern[i] == pattern[j + 1]) //前后缀相等 { j++; } next[i] = j; }}int kmp(const char *text, const char *pattern){ int i; int j = -1; const int n = strlen(text); const int m = strlen(pattern); if (n == 0 && m == 0) return 0; if (m == 0) return 0; int *next = (int*)malloc(sizeof(int) * m); compute_prefix(pattern, next); for (i = 0; i < n; i++) { while (j > -1 && pattern[j + 1] != text[i]) j = next[j]; if (text[i] == pattern[j + 1]) j++; if (j == m - 1) { free(next); return i-j; } } free(next); return -1;} 测试 #include<stdio.h>#include <stdlib.h>#include <string.h>void compute_prefix(const char *pattern, int next[]){ int i; //前缀 int j = -1; //前缀尾巴 const int m = strlen(pattern); next[0] = j; for (i = 1; i < m; i++) { while (j > -1 && pattern[j + 1] != pattern[i]) //前后缀不相等 { j = next[j]; } if (pattern[i] == pattern[j + 1]) //前后缀相等 { j++; } next[i] = j; }}int kmp(const char *text, const char *pattern){ int i; int j = -1; const int n = strlen(text); const int m = strlen(pattern); if (n == 0 && m == 0) return 0; if (m == 0) return 0; int *next = (int*)malloc(sizeof(int) * m); compute_prefix(pattern, next); for (i = 0; i < n; i++) { while (j > -1 && pattern[j + 1] != text[i]) j = next[j]; if (text[i] == pattern[j + 1]) j++; if (j == m - 1) { free(next); return i-j; } } free(next); return -1;}int main(){ char text[] = "ABC ABCDAB ABCDABCDABDE"; char pattern[] = "ABCDABD"; char *ch = pattern; int i = kmp(text, pattern); if (i >= 0) { printf("matched @: %sn", ch); } else { printf("matched fail!n"); } return 0;}执行结果：
matched @: ABCDABD