文档介绍：1. BF(Brute-Force) 算法 Brute-Force 算法的基本思想是: 1) 从目标串 s 的第一个字符起和模式串 t 的第一个字符进行比较,若相等,则继续逐个比较后续字符,否则从串 s 的第二个字符起再重新和串 t 进行比较。 2) 依此类推,直至串 t 中的每个字符依次和串 s 的一个连续的字符序列相等,则称模式匹配成功,此时串 t 的第一个字符在串 s 中的位置就是 t在s 中的位置,否则模式匹配不成功。 Brute-Force 算法的实现 c 语言实现: ?// : Defines the entry point for the console application. ?// ?#include "" ?#include <> ?#include "" ?#include <iostream> ? using namespace std; ??// 宏定义??#define TRUE 1 ??#define FALSE 0 ??#define OK1 ??#define ERROR 0 ????#define MAXSTRLEN 100 ???? typedef char SString[MAXSTRLEN + 1]; ??/************************************************************************/ ??/* ??返回子串 T在主串 S中第 pos 位置之后的位置,若不存在,返回 0 ??*/ ??/************************************************************************/ ?? int BFindex(SString S, SString T, int pos) ??{ ?? if (pos <1 || pos > S[0] ) exit(ERROR); ?? int i= pos, j =1; ?? while (i<= S[0] && j <= T[0]) ??{ ?? if (S[i] == T[j]) ??{ ??++i; ++j; ??} else { ??i= i- j+ 2; ??j= 1; ??} ??} ?? if (j > T[0]) return i- T[0]; ?? return ERROR; ??} ???????? void main(){ ?? SString S= {13, 'a' , 'b' , 'a' , 'b' , 'c' , 'a' , 'b' , 'c' , 'a' , 'c' , 'b' , 'a' , 'b' }; ?? SString T= {5, 'a' , 'b' , 'c' , 'a' , 'c' }; ?? int pos; ?? pos = BFindex( S, T, 1); ?? cout<< "Pos:" <<pos; ??}2. KMP 算法 算法思想: 每当一趟匹配过程中出现字符比较不等时, 不需要回溯 I 指针, 而是利用已经的带的“部分匹配”的结果将模式向右滑动尽可能远的一段距离后,继续进行比较。即尽量利用已经部分匹配的结果信息,尽量让