郑州优之客网站建设,建设网站内容,wordpress 自定义分类,九江seo公司1 KMP算法 KMP#xff08;Knuth-Morris-Pratt#xff09;算法是一种改进的字符串匹配算法#xff0c;由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出#xff0c;用于在一个文本串#xff08;主串#xff09;中搜索一个词#xff08;模式串#xff09;的位置。KMP算法的关…1 KMP算法 KMPKnuth-Morris-Pratt算法是一种改进的字符串匹配算法由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出用于在一个文本串主串中搜索一个词模式串的位置。KMP算法的关键在于当字符串匹配过程中出现字符不匹配时能知道部分已经比较过的字符的信息利用这些信息避免重新比较这些字符从而提高算法的效率。
2 KMP算法实现
#include stdio.h
#include stdlib.h
#include string.h // 构建部分匹配表失败函数表
void computeLPSArray(char *pat, int M, int *lps) { int len 0; // 前缀后缀的最大长度 int i 1; lps[0] 0; // lps[0]总是0 // 遍历模式串 while (i M) { if (pat[i] pat[len]) { len; lps[i] len; i; } else { if (len ! 0) { len lps[len - 1]; } else { lps[i] len; i; } } }
} // KMP搜索算法
int KMPSearch(char *pat, char *txt) { int M strlen(pat); int N strlen(txt); // 创建lps数组 int *lps (int *)malloc(sizeof(int) * M); computeLPSArray(pat, M, lps); int j 0; // 模式串索引 for (int i 0; i N; i) { if (pat[j] txt[i]) { j; } if (j M) { free(lps); // 释放lps数组内存 return i - j 1; // 返回模式串在主串中首次出现的起始位置 } // 如果模式串中当前字符不匹配则j变为lps[j-1] if (i N pat[j] ! txt[i]) { if (j ! 0) j lps[j - 1]; else i; } } free(lps); // 释放lps数组内存 return -1; // 没有找到模式串
} int main() { char txt[] ABABDABACDABABCABAB; char pat[] ABABCABAB; int result KMPSearch(pat, txt); if (result -1) printf(Pattern not found\n); else printf(Pattern found at index: %d\n, result); return 0;
} 3 KMP算法原理 KMP算法的核心在于当主串中的某个字符与模式串中的相应字符不匹配时可以知道模式串中一定存在一个最长的相同前缀后缀使得模式串可以向右滑动继续从该前缀后缀之后的那个字符开始比较。这个最长的相同前缀后缀的长度存储在“部分匹配表”lps数组中。
4 KMP算法优化及实现 KMP算法本身已经是一种高效的字符串匹配算法但在实际应用中可以根据具体需求进行进一步的优化。例如减少lps数组的计算时间可以通过一些技巧来减少计算lps数组的时间例如使用递归、动态规划等方法来优化计算过程。
