数据结构- 串的模式匹配算法：BF和KMP算法Brute-Force算法的思想Brute-Force算法的基本思想是：1) 从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。

2) 依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。

Brute-Force算法的实现c语言实现：1.// Test.cpp : Defines the entry point for the console application.2.//3.#include "stdafx.h"4.#include <stdio.h>5.#include "stdlib.h"6.#include <iostream>ing namespace std;8.9.//宏定义10.#define TRUE 111.#define FALSE 012.#define OK 113.#define ERROR 014.15.#define MAXSTRLEN 10016.17.typedef char SString[MAXSTRLEN + 1];18./************************************************************************/19./*20.返回子串T在主串S中第pos位置之后的位置，若不存在，返回021.*/22./************************************************************************/23.int BFindex(SString S, SString T, int pos)24.{25.if (pos <1 || pos > S[0] ) exit(ERROR);26.int i = pos, j =1;27.while (i<= S[0] && j <= T[0])28. {29.if (S[i] == T[j])30. {31. ++i; ++j;32. } else {33. i = i- j+ 2;34. j = 1;35. }36. }37.if(j > T[0]) return i - T[0];38.return ERROR;39.}40.41.42.43.void main(){44. SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};45. SString T = {5,'a','b','c','a','c'};46.int pos;47. pos = BFindex( S, T, 1);48. cout<<"Pos:"<<pos;49.}2.1 算法思想：每当一趟匹配过程中出现字符比较不等时，不需要回溯I指针，而是利用已经的带的“部分匹配”的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。

即尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。

需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是高效率的?现在讨论一般情况:假设主串：s: …s(1)s(2) s(3) ……s(n)‟ ; 模式串：p: …p(1)p(2) p(3)…..p(m)‟现在我们假设主串第i个字符与模式串的第j(j<=m)个字符…失配‟后，主串第i个字符与模式串的第k(k<j)个字符继续比较。

此时，s(i)≠p(j)：由此，我们得到关系式：即得到到1 到 j -1 的"部分匹配"结果:‘P(1)P(2) P(3)…..P(j-1)’= ’ S(i-j+1)……S(i-1)’从而推导出k 到j- 1位的“部分匹配”：即P的j-1～j-k＝S前i-1～i- (k -1))位‘P(j - k + 1) …..P(j-1)’ = ’S(i-k+1)S(i-k+2)……S(i-1)’由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在k‟>k满足下列关系式：(k<j)有关系式：即(P的前k- 1 ~ 1位＝S前i-1～i-(k-1) )位) ,：‘P(1) P(2) P(3)…..P(k-1)’= ’S(i-k+1)S(i-k+2)……S(i-1)’现在我们把前面总结的关系综合一下,有：由上，我们得到关系：‘p(1)p(2) p(3)…..p(k-1)’ = ‘p(j - k + 1) …..p(j-1)’反之，若模式串中满足该等式的两个子串，则当匹配过程中，主串中的第i 个字符与模式中的第j个字符等时，仅需要将模式向右滑动至模式中的第k个字符和主串中的第i个字符对齐。

此时，模式中头k-1个字符的子串…p(1)p(2) p(3)…..p(k-1)‟必定与主串中的第i 个字符之前长度为k-1 的子串‟s(j-k+1)s(j-k+2)……s(j-1)‟相等，由此，匹配仅需要从模式中的第k 个字符与主串中的第i 个字符比较起继续进行。

若令next[j] = k ,则next[j] 表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行的比较的位置。

由此可引出模式串的next函数：根据模式串P的规律：‘p(1)p(2) p(3)…..p(k-1)’ = ‘p(j - k + 1) …..p(j-1)’由当前失配位置j(已知) ，可以归纳计算新起点k的表达式。

由此定义可推出下列模式串next函数值：模式匹配过程:KMP算法的实现:第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来；第二步：执行定位函数Index_kmp（与BF算法模块非常相似）1.int KMPindex(SString S, SString T, int pos)2.{3.if (pos <1 || pos > S[0] ) exit(ERROR);4.int i = pos, j =1;5.while (i<= S[0] && j <= T[0])6. {7.if (S[i] == T[j]) {8. ++i; ++j;9. } else {10. j = next[j+1];11. }12. }13.if(j > T[0]) return i - T[0];14.return ERROR;15.}完整实现代码：1.// Test.cpp : Defines the entry point for the console application.2.//3.#include "stdafx.h"4.#include <stdio.h>5.#include "stdlib.h"6.#include <iostream>ing namespace std;8.9.//宏定义10.#define TRUE 111.#define FALSE 012.#define OK 113.#define ERROR 014.15.#define MAXSTRLEN 10016.17.typedef char SString[MAXSTRLEN + 1];18.19.void GetNext(SString T, int next[]);20.int KMPindex(SString S, SString T, int pos);21./************************************************************************/22./*23.返回子串T在主串S中第pos位置之后的位置，若不存在，返回024.*/25./************************************************************************/26.int KMPindex(SString S, SString T, int pos)27.{28.if (pos <1 || pos > S[0] ) exit(ERROR);29.int i = pos, j =1;30.int next[MAXSTRLEN];31. GetNext( T, next);32.while (i<= S[0] && j <= T[0])33. {34.if (S[i] == T[j]) {35. ++i; ++j;36. } else {37. j = next[j];38. }39. }40.if(j > T[0]) return i - T[0];41.return ERROR;42.}43.44./************************************************************************/45./* 求子串next[i]值的算法46.*/47./************************************************************************/48.void GetNext(SString T, int next[])49.{ int j = 1, k = 0;50. next[1] = 0;51.while(j < T[0]){52.if(k == 0 || T[j]==T[k]) {53. ++j; ++k; next[j] = k;54. } else {55. k = next[k];56. }57. }58.}59.60.void main(){61. SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};62. SString T = {5,'a','b','c','a','c'};63.int pos;64. pos = KMPindex( S, T, 1);65. cout<<"Pos:"<<pos;66.}2.2 求串的模式值next[n]k值仅取决于模式串本身而与相匹配的主串无关。