十堰做网站的公司,网站底部的备案号,济南网站,编程app下载KMP算法的原理是通过构建部分匹配表#xff0c;来利用已经匹配过的信息#xff0c;避免不必要的回溯。部分匹配表是一个长度与模式字符串相等的数组#xff0c;用于记录在每个位置上的最长公共前后缀的长度。 这样图片完全表达了KMP算法的核心思想#xff0c;出处来自添加链…KMP算法的原理是通过构建部分匹配表来利用已经匹配过的信息避免不必要的回溯。部分匹配表是一个长度与模式字符串相等的数组用于记录在每个位置上的最长公共前后缀的长度。 这样图片完全表达了KMP算法的核心思想出处来自添加链接描述
大家如果还看不懂可以结合以下代码来理解
#include iostream
#include vector
using namespace std;// 构建部分匹配表
vectorint buildPartialMatchTable(const string pattern) {int m pattern.length();vectorint table(m, 0);int len 0;int i 1;while (i m) {if (pattern[i] pattern[len]) {len;table[i] len;i;}else {if (len ! 0) {len table[len - 1];}else {table[i] 0;i;}}}for (int i 0; i table.size(); i) {cout table[i];}cout endl;return table;
}// 使用 KMP 算法查找子字符串
void searchKMP(const string text, const string pattern) {int n text.length();int m pattern.length();vectorint table buildPartialMatchTable(pattern);int i 0, j 0;while (i n) {if (pattern[j] text[i]) {i;j;}if (j m) {cout 在位置 i - j 处找到匹配 endl;j table[j - 1];}else if (i n pattern[j] ! text[i]) {if (j ! 0) {j table[j - 1];}else {i;}}}
}int main() {string text ABABDABACDABABCABAB;string pattern ABABCABAB;cout 在文本中查找子字符串 endl;searchKMP(text, pattern);return 0;
}
先不管逻辑我们先看程序输出
在文本中查找子字符串
001201234
在位置 10 处找到匹配001201234为什么是这段代码结合着上面的图片 在部分匹配表中每个索引位置的值表示在该位置之前的最长公共前后缀的长度。代码中的查找字符串为ABABCABAB对应索引位置为
索引位置 i 0 1 2 3 4 5 6 7 8
部分匹配值 0 0 1 2 0 1 2 3 4这样就能够知道遇到不同的字母时需要跳转的路径。
代码逻辑buildPartialMatchTable函数用于构建部分匹配表。函数接受一个模式字符串作为参数返回一个部分匹配表。该函数使用两个指针i和len其中i从1开始len初始化为0。通过遍历模式字符串来逐个计算每个位置上的最长公共前后缀长度。具体步骤如下
如果当前位置的字符和前缀的下一个字符相等那么len加1table[i]等于len然后指针i和len都向后移动一位。 如果当前位置的字符和前缀的下一个字符不相等那么判断len是否为0。如果len不为0将len更新为前一个位置的最长公共前后缀长度然后继续比较当前位置的字符和前缀的下一个字符。如果len为0表示当前位置没有最长公共前后缀将table[i]设为0然后指针i向后移动一位。 最后返回构建好的部分匹配表。 然后searchKMP函数用于在文本字符串中查找子字符串。函数接受一个文本字符串和一个模式字符串作为参数不返回值。函数内部使用两个指针i和j其中i表示在文本字符串中的位置j表示在模式字符串中的位置。具体步骤如下
当模式字符串和文本字符串的字符相等时指针i和j都向后移动一位。 当j等于模式字符串的长度m时表示找到了匹配输出匹配的位置i-j并将指针j更新为部分匹配表中的值table[j-1]继续查找下一个匹配。 当i小于文本字符串的长度n且j不等于模式字符串的长度m时如果当前位置的字符和模式字符串的字符不相等那么判断j是否为0。如果j不为0将j更新为部分匹配表中的值table[j-1]然后继续比较当前位置的字符和模式字符串的字符。如果j为0表示当前位置没有匹配将指针i向后移动一位。
