35开始学网站开发,崇信县门户网,徐州建设工程网,wordpress连接设置欢~迎~光~临~^_^ 目录
知识树
1、什么是串的模式匹配
2、简单的模式匹配算法
3、KMP算法
3.1 算法原理
3.2 C语言实现KMP算法
3.3 求next数组
3.4 KMP算法优化#xff08;对next数组的优化#xff09; 知识树 1、什么是串的模式匹配 串的模式匹配是在一个字符串中… 欢~迎~光~临~^_^ 目录
知识树
1、什么是串的模式匹配
2、简单的模式匹配算法
3、KMP算法
3.1 算法原理
3.2 C语言实现KMP算法
3.3 求next数组
3.4 KMP算法优化对next数组的优化 知识树 1、什么是串的模式匹配 串的模式匹配是在一个字符串中查找另一个较小的字符串称为模式的过程。模式匹配的目的是在文本串中查找一个或多个匹配字符串。这种搜索可以使用各种算法进行包括暴力算法KMP算法和Boyer-Moore算法等。模式匹配广泛应用于文本编辑器、搜索引擎、计算机网络和计算机安全等领域。
2、简单的模式匹配算法 这个算法的时间复杂度是O(mn)其中m是模式串的长度n是文本串的长度。在最坏情况下即文本串中的每个字符都匹配模式串中的每个字符时间复杂度为O(m(n-m1))因此朴素模式匹配算法在处理大型文本串时可能会变得很慢。
#include stdio.h
#include string.hint naive_search(const char text[], const char pattern[]) {int text_len strlen(text);int pattern_len strlen(pattern);for (int i 0; i text_len - pattern_len; i) {int j;for (j 0; j pattern_len; j) {if (text[i j] ! pattern[j])break;}if (j pattern_len)return i;}return -1;
}int main() {char text[] ABABCABCABABABD;char pattern[] ABABD;int pos naive_search(text, pattern);if (pos 0)printf(Pattern found at position %d in the text., pos);elseprintf(Pattern not found in the text.);return 0;
} 3、KMP算法
3.1 算法原理 KMP算法是一种字符串匹配算法它的原理是利用已知的信息尽可能减少匹配次数。KMP算法的核心是一个跳转表格也称为Next数组或失配函数。 在匹配的过程中当发现不匹配的情况时KMP算法会利用跳转表格中已经计算好的信息直接跳过部分不需要匹配的字符从而减少匹配次数。具体来说KMP算法会根据当前匹配的位置和已知的信息计算出下一个字符需要匹配的位置从而避免了不必要的匹配操作。 KMP算法的时间复杂度为O(mn)其中m和n分别为模式串和文本串的长度求next数组时间复杂度Om模式匹配过程最坏时间复杂度On。相比于朴素的字符串匹配算法KMP算法在匹配效率和性能上有了很大的提高。
3.2 C语言实现KMP算法 下述代码中next()函数用于计算模式串的next数组kmp()函数用于在文本串中查找模式串。在main()函数中首先输入文本串和模式串然后调用next()函数生成模式串的next数组最后调用kmp()函数在文本串中查找模式串。若模式串存在于文本串中输出模式串在文本串中的位置否则输出不存在的信息。
#include stdio.h
#include stdlib.h
#include string.hvoid next(char *pattern, int *next_arr) {int i 0, j -1;next_arr[0] -1;int len strlen(pattern);while (i len - 1) {if (j -1 || pattern[i] pattern[j]) {i;j;next_arr[i] j;} else {j next_arr[j];}}
}int kmp(char *text, char *pattern, int *next_arr) {int i 0, j 0;int text_len strlen(text), pattern_len strlen(pattern);while (i text_len j pattern_len) {if (j -1 || text[i] pattern[j]) {i;j;} else {j next_arr[j];}}if (j pattern_len) {return i - j;} else {return -1;}
}int main() {char text[100], pattern[100];int next_arr[100];printf(请输入文本串);gets(text);printf(请输入模式串);gets(pattern);next(pattern, next_arr);int index kmp(text, pattern, next_arr);if (index ! -1) {printf(模式串在文本串中的位置是%d\n, index);} else {printf(文本串中不存在模式串\n);}return 0;
} 3.3 求next数组 nextj的含义是在子串的第j个字符与主串发生失配时则跳到子串的nextj位置重新与主串当前位置进行比较。 next1都无脑写0next2都无脑写1 其他next在不匹配的位置前划一根分界线模式串一步一步往后退直到分界线之前“能对上”或模式串完全跨过分界线为止此时 j 指向哪next数组值就是多少。
void next(char *pattern, int *next_arr) {int i 0, j -1;next_arr[0] -1;int len strlen(pattern);while (i len - 1) {if (j -1 || pattern[i] pattern[j]) {i;j;next_arr[i] j;} else {j next_arr[j];}}
} 在上述代码中pattern表示模式串next_arr表示next数组。首先将next_arr[0]置为-1i表示当前已匹配的字符数初始值为0j表示当前已匹配的字符中能和下一位字符匹配的最长前缀的末尾位置初始值为-1。在循环中若第i个字符能和第j1个字符匹配则更新next_arr[i1]j1否则将j更新为next_arr[j]重复此过程直到结束。 例1若模式串为ABCDABD则next数组为[-1, 0, 0, 0, 0, 1, 2, 0]。 例2下面是ababaaababaa模式串对应的next数组值 - a b a b a a a b a b a a - 0 0 1 2 3 4 5 2 3 4 5 6 因此ababaaababaa模式串的next数组值为[0, 0, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6]。 next数组的生成过程是KMP算法的核心部分它可以大大提高模式匹配的效率。
3.4 KMP算法优化对next数组的优化 KMP算法优化可以采用KMP算法的优化手段通过推导next[j]和nextval[next[j]]的关系减少计算次数。
//核心代码
nextval[1]0;
for(int j 2;j pattern.length;j)
{if(pattern[next[j]] pattern[j])nextval[j] nextval[next[j]];elsenextval[i] nextval[j];
} ❤️❤️❤️串的模式匹配的知识点总结就到这里啦如果对博文还满意的话劳烦各位看官动动“发财的小手”留下您对博文的赞和对博主的关注吧❤️❤️❤️
