C语言字符串的模式匹配.docx
7页
数据结构面试之十四——字符串的模式匹配题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考十四、字符串的模式匹配1. 模式匹配定义——子串的定位操作称为串的模式匹配2. 普通字符串匹配 BF 算法（Brute Force 算法，即蛮力算法）【算法思想】：第（1）步；从主串 S 的第 pos 个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之第（2）步骤；依次类推，直至模式 T 中的每一个字符依次和主串 S 中的一个连续的字符序列相等，则称匹配成功；函数值为和模式 T 中第一个字符相等的字符在主串 S 中的序号，否则称为匹配不成功，函数值为 0比如对于主串 S=”abacababc”; 模式串 T=”abab”; 匹配成功，返回 4对于主串 S=”abcabcabaac”; 模式串 T=”abab”; 匹配不成功，返回 0算法实现】：//普通字符串匹配算法的实现int Index(char* strS, char* strT, int pos) { //返回 strT 在 strS 中第 pos 个字符后出现的位置。
int i = pos;int j = 0;int k = 0;int lens = strlen(strS); int lent = strlen(strT);while(i = lent){return i;}else{return 0;}}//end[算法时间复杂度]：设主串长度为 m,模式串的长度为 n一般情况下 n 正文 t t1 t2 t3 tm tn模式 p p1 p2 p3 …. pm .【next（j）定义】:表示当 pi 不等于 tr 时，下一次将 pnext[i] 与 tr 开始继续后继对应字符的比较其中 next[0]=-1,表明当 p0 不等于 tr 时，将从 p-1 与 tr 开始继续后继对应字符的比较；显然p-1 是不存在的，我们可以将这种情况理解成下一步将从 p0 与 tr+1 开始继续后继对应字符的比较举例说明 1：模式串 p=“google”,对应的 next[j]={-1,0,0,0,1,0}解读：g 设定为-1o 字符 o 之前没有匹配的字符o 字符 o（第 2 个）之前的字符（g，o）不同g 字符 g 之前的字符（g，o，o ）前缀、后缀（如：g 与 o；go 与 oo）不匹配l 字符 l 之前的字符（g，o，o ，g）前缀、后缀（如： g 与 g）相同，返回 1e 字符 e 之前的字符（ g，o，o，g ，l）前缀、后缀（如：goo 与 ogl）不同举例说明 2：模式串 p=“abaabcaba”，对应的 next[j]={-1,0,0,1,1,2,0,1,2}。 KMP 算法实现】：第一步：求解 next 数组typedef struct {char str[100];int length;}seqString;//根据模式 t 的组成求其对应的 next 数组void getNext(seqString t, int next[]){next[0] = -1;int i = 0;int j = -1;while(i < t.length){if(j == -1 || t.str[i] == t.str[j]){++i;++j;next[i] = j;}else{j = next[j];}}//end whilecout << "next[ "<< t.length << " ]" << endl;for(i = 0; i < t.length; i++) {cout << next[i] << "\t";}cout << endl;}//end第二步：KMP 匹配算法的实现//t 代表正文源串，p 代表模式匹配串， next 代表匹配 next 数组int kmp(seqString t, seqString p, int next[]){int i = 0;int j = 0;while(i < t.length && j < t.length){if(j == -1 || t.str[i] == p.str[j]){i++;j++;}else{j = next[j];}}if(j == p.length){return( i -p.length);}else{return -1; }}int main(){int rtnPos = 0;seqString strS;strcpy(strS.str,"goodgoogle"); //源串strS.length = strlen(strS.str);seqString strT;strcpy(strT.str,"abaabcaba"); //模式串strT.length = strlen(strT.str);int *pNext = new int[strT.length];getNext(strT,pNext);rtnPos = kmp(strS,strT,pNext);cout << rtnPos << endl; //输出匹配位置return 0;}4. 手动演示 BF 算法与 KMP 算法的不同（如下图所示）。 字符串的匹配不是很好理解，JULY 曾经用很长的篇幅去讲，大家可以参考很多材料讲的思路一致，但实现稍有差别，本文的实现和图示是一致的，有错误的话希望大家提出，不胜感激！。
