字符串匹配：暴力法和KMP算法（C语言）

文章目录KMP算法1.串的定义1.1定长顺序存储和变长分配存储表示1.2 串的初始化2.串的匹配2.1 暴力查找2.2 KMP算法KMP算法的思想手动算next数组next数组值的规律代码全部代码KMP算法1.串的定义串字符串是一种特殊的线性表其数据元素是字符。它是计算机中处理文本信息的基本数据结构。char str[]“Hello world”数据结构的串没有“\0”,不同的编程语言是否用0°作为串的结束标志是没有定论的通过length来约束空间的长度也会更通用。1.1定长顺序存储和变长分配存储表示typedefstruct{charstr[maxSize1]//从0号索引l存储数据1是为了存储\0可选intlength;}typedefstruct{char*str;intlength;//动态分配空间}1.2 串的初始化与普通变量赋值操作不同串的赋值操作不能直接用来实现通过定义初始化函数来实现空间拷贝。//串头初始化字符串intstrAssign(StrType*str,constchar*ch);申请多两个0号不填KMP监视哨‘\0’还要填// tinaStr.h#pragmaoncetypedefstruct{char*str;intlength;}StrType;// 字符串赋值将ch指向的C字符串复制给strvoidstrAssign(StrType*str,constchar*ch);voidreleaseStr(StrType*str);intindex_simple(constStrType*str,constStrType*subStr);#includetinaStr.h#includestdlib.h// 为了 malloc 和 freevoidstrAssign(StrType*str,constchar*ch){// 如果str已经分配了内存先释放if(str-str){free(str-str);str-strNULL;}// 计算ch的长度intlen0;while(ch[len]){len;}// 如果长度为0则str为空串if(len0){str-strNULL;str-length0;return;}// 分配内存长度为len1包括结束符\0str-str(char*)malloc(sizeof(char)*(len2));if(!str-str){// 内存分配失败可以处理错误这里简单地将长度置0并返回str-length0;return;}// 复制字符包括结束符for(inti0;ilen;i){str-str[i1]ch[i];}str-lengthlen;}voidreleaseStr(StrType*str){ifstr{ifstr-str{free(str-str);}}2.串的匹配字符串匹配在主串中找到与模式串相同的子串并返回其所在位置。2.1 暴力查找假设法intindex_simple(constStrType*str,constStrType*subStr){inti1;intj1;intki;// 记录起始位置while(istr-lengthjsubStr-length){if(str-str[i]subStr-str[j]){i;j;}else{j1;k;ik;}}if(jsubStr-length){returnk;// 匹配成功返回起始位置}return0;// 匹配失败}// 测试函数voidtest01(constStrType*str,constStrType*pattern){intresindex_simple(str,pattern);printf(simple find index: %d\n,res);}intmain(){StrType str;StrType subStr;str.strNULL;subStr.strNULL;strAssign(str,ABCDABCABCABABCABCD);strAssign(subStr,ABCABCD);// 调用测试函数test01(str,subStr);releaseStr(str);releaseStr(subStr);return0;}2.2 KMP算法不匹配的字符之前一定是和模式串一致的是否可以从这个已知信息来确定模式失配时下次从模式串的第几个位置假设模式串为abcabd主串为“abcabxxxx“从主串s[1]开始匹配时在p[6]时失配既然在p[6]处失配那么说明s[1:5]的信息一定是模式串的p[1:5]所以按照朴素匹配算s[2]、s[3」… 开始匹配尝试是不是可以明确肯定不会成功。而从s[4]开始有可能成功P[1:5]“abcab”它的前缀不包括自身有“a”, “ab”, “abc”, “abca”P[1:5]“abcab后缀不包括自身有“b”, “ab”, “cab”, “bcab”。最长的公共前后缀是ab”长度为2第一次匹配从 s[1] 开始匹配成功前5个字符 主串 a b c a b x x x x ↑ ↑ ↑ ↑ ↑ × ← s[6] ≠ p[6] (x ≠ d) 模式 a b c a b d ↑ ↑ ↑ ↑ ↑ ↑ 1 2 3 4 5 6 已匹配部分s[1:5] abcab p[1:5]朴素算法的做法试每个位置❌从 s[2] 开始匹配text主串 a b c a b x x x x ↑ ← 从这里开始对齐p[1] 模式 a b c a b d ↑ 1 需要满足s[2] p[1] a 但已知s[2] b 所以❌ 必定失败 为什么已知s[2]b 因为s[2]在第一次匹配时已经看过❌从 s[3] 开始匹配主串 a b c a b x x x x ↑ ← 从这里开始对齐p[1] 模式 a b c a b d ↑ 1 需要满足s[3] p[1] a 但已知s[3] c 所以❌ 必定失败✅从 s[4] 开始可能成功主串 a b c a b x x x x ↑ ← 从这里开始对齐p[1] 模式 a b c a b d ↑ 1 需要满足s[4] p[1] a 已知s[4] a ✅ 满足 继续检查 主串 a b c a b x x x x ↑ ↑ ← 检查p[2] 模式 a b c a b d ↑ ↑ 1 2 需要满足s[5] p[2] b 已知s[5] b ✅ 满足 到这里已经匹配了前2个字符可能继续成功。KMP算法的思想当子串和模式串不匹配时主串指针i不回溯通过改变模式串指针j的值来确定子串从失配处和模式串的哪个位置进行比较因为模式串前面的信息在前面比较的时候已经知道信息了。如果能够存储子串失配后从模式串的哪个位置上进行比较就可以实现KMP算法故引入next数组专门存放这个值。显然next数组里的值只跟模式串有关因为模式串前面已经成功匹配的字符就表示子串中已经包含了这些字符。手动算next数组next数组Next数组记录的是模式串每个位置**“最长相同前后缀”的长度**。当匹配失败时模式串要往前退多少才能继续匹配而不是傻傻地只退1位。串的前缀包含第一个字符且不包含最后一个字符的子串串的后缀包含最后一个字符且不包含第一个字符的子串找前缀和后缀中相同的部分取最长的那个。 还是 abcab 前缀a, ab, abc, abca 后缀b, ab, cab, bcab 相同的只有 ab长度2 所以最长相同前后缀长度 2当第j个字符匹配失败由前[1j-1]个字符组成的串记为S手动计算就是根据这个S来决定的next[j的值S最长相等前后缀的长度1表示对于子串中前j-1个字符而言步骤规则1第一个字符的 Next 值 0因为前面没有字符了。规则2后面的字符按以下公式next[j] (前j-1个字符的串)的最长相同前后缀长度 1一句话解释已经匹配成功的部分如果有相同前后缀前缀部分肯定也能匹配所以跳过它们直接从相同部分的下一个开始比较。举例 模式串abcabd在p[6]失败时前5个字符abcab已匹配abcab有相同前后缀ab长度2前缀ab肯定能匹配因为后缀ab已匹配所以直接从p[3]开始比较21next[6] 2 1 3意思跳过前2个字符从第3个开始为什么 1长度2表示有2个字符肯定匹配但我们要比较的是下一个字符所以是已确定的匹配数 要检查的下一个位置next数组值的规律next[j]的值每次最多增加1模式串的最后一位字符不影响next数组的结果next数组的定义当主串与模式串的某一位字符不匹配时模式串要回退到的位置voidgetNext(StrType*subStr,intnext[]){inti1,j0;// 串从数组下标1位置开始存储//i 模式串短串的位置//j next数组值next[0]0;while(isubStr-length){if(j0||subStr-str[i]subStr-str[j]){i;j;next[i]j;}else{//不等往前看jnext[j];}}}代码voidgetNext(StrType*subStr,intnext[]){//next 填的为公共 前后缀长度加一inti1,j0;// 串从数组下标1位置开始存储//i 模式串短串的位置//j next数组值next[0]0;//i length 时不会进入循环 next索引最大为lengthwhile(isubStr-length){if(j0||subStr-str[i]subStr-str[j]){i;j;next[i]j;}else{//不等往前看jnext[j];}}}// KMP模式匹配算法intindexKMP(constStrType*str,constStrType*subStr,constintnext[]){inti1;// 主串当前位置intj1;// 子串当前位置while(istr-lengthjsubStr-length){//主串不动 子串动if(j0||str-str[i]subStr-str[j]){i;j;}else{jnext[j];}}if(jsubStr-length){returni-subStr-length;// 匹配成功返回起始位置}return0;// 匹配失败}全部代码stringKMP.h#includestdio.h#includestdlib.htypedefstruct{char*s;intlen;}strType;voidinitStr(strType*str);voidCopyStr(strType*str,constchar*s);intsimple_index(strType*str,strType*substr);intKMPIndex(strType*str,strType*substr);voidreleaseStr(strType*str);KMP和暴力#includestringKMP.hvoidinitStr(strType*str){str-len0;str-sNULL;}voidCopyStr(strType*str,constchar*s){if(str-s){free(str-s);str-sNULL;}intlen0;//分配多少空间while(s[len]){len;}//0位置不放字符以及\0str-smalloc(sizeof(strType)*(len2));if(str-sNULL)return;str-lenlen;//赋值for(inti0;ilen;i){//str-s[i 1] [1,len1]//s[i] [0,len]str-s[i1]s[i];}//检验copy成功printf(\n\n);for(inti0;ilen;i){printf(%c,str-s[i1]);}printf(\n\n);}intsimple_index(strType*str,strType*substr){inti1;//主串索引intj1;//模式串索引intki;//记录主串回溯位置 模式串回溯到开头while(istr-lenjsubstr-len){if(str-s[i]substr-s[j]){i;j;ki;}else{k;//主串移动一个位置匹配ik;j1;}}//循环结束模式串走到了末尾 证明是子串if(jsubstr-len){returni-substr-len;}return0;}//回溯数组next[i]//next[i][1,i-1]里面的公共前后缀个数1staticvoidgetnext(strType*substr,intnext[]){next[0]0;//不装东西next[1]0;intcur1;//当前模式串索引intk0;//next值while(cursubstr-len){//if (k 0) {//cur;//k;//索引2 只有一个//没有公共前后缀而且不是本身 next[2]01//next[cur] k;//continue;//}if(k0||substr-s[cur]substr-s[k]){cur;k;next[cur]k;}else{knext[k];}}/*for (int i 1; i cur; i) { printf(%d , next[i]); }*/}//主串不回溯 模式串回溯// 回溯数组next 模式串i位置不匹配时回溯的位置为next[i]intKMPIndex(strType*str,strType*substr){inti1;//主串索引intj1;//模式串索引而且和next数组值有关//空出第一位int*nextmalloc(sizeof(int)*(str-len1));if(nextNULL)return-1;getnext(substr,next);while(istr-lenjsubstr-len){if(j0||str-s[i]substr-s[j]){i;j;}else{jnext[j];}}if(jsubstr-len){returni-substr-len;}return0;}voidreleaseStr(strType*str){if(str-s){free(str-s);str-sNULL;}}voidtest01(){strType str;strType substr;initStr(str);initStr(substr);CopyStr(str,ABCDABCABCABABCABCD);CopyStr(substr,ABCABCD);//abaaabagabaaabaa/*int res simple_index(str, substr); printf(simple_index:%d\n, res);*/intresKMPIndex(str,substr);printf(KMPIndex:%d\n,res);}intmain(){test01();return0;}/*ABCDABCABCABABCABCD ABCABCD */