赞
踩
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和 Vaughan Pratt共同发明。KMP算法的核心思想是当一次字符比较失败时,利用已经得到的部分匹配信息,将模式字符串向右滑动一段距离后继续比较,从而避免从头开始匹配,提高匹配效率。
#include <stdio.h> #include <string.h> #include <stdlib.h> // 计算部分匹配表(PMT) void computePMT(char *P, int *PMT) { int m = strlen(P); // 模式串的长度 PMT[0] = -1; // PMT数组的第一个元素设为-1 PMT[1] = 0; // PMT数组的第二个元素设为0 int k = 0; // 初始化k为0,用于PMT的计算 // 计算PMT数组 for (int i = 2; i < m; i++) { // 如果当前字符不匹配,并且k不为0,则回退k的位置 while (k > 0 && P[k] != P[i - 1]) { k = PMT[k]; } // 如果当前字符匹配,则k增加1 if (P[k] == P[i - 1]) { k++; } PMT[i] = k; } } // KMP搜索算法 int KMP(char *S, char *P) { int n = strlen(S); // 主串的长度 int m = strlen(P); // 模式串的长度 int *PMT = (int *)malloc(m * sizeof(int)); // 动态分配PMT数组的空间 computePMT(P, PMT); // 计算PMT数组 int i = 0, j = 0; // 初始化i和j,分别用于主串和模式串的索引 // 遍历主串S while (i < n) { // 如果j为-1或当前字符匹配,则继续匹配下一个字符 if (j == -1 || S[i] == P[j]) { i++; j++; } else { // 如果字符不匹配,则根据PMT数组回退j的位置 j = PMT[j]; } // 如果j等于模式串的长度,则找到了匹配 if (j == m) { free(PMT); // 释放PMT数组的空间 return i - j; // 返回匹配的起始索引 } } free(PMT); // 释放PMT数组的空间 return -1; // 如果没有找到匹配,则返回-1 } int main() { char S[] = "ababcabcafgghrfthrhrthrtjtyjcbab"; // 主串 char P[] = "rhrthrtj"; // 模式串 int index = KMP(S, P); // 使用KMP算法搜索模式串在主串中的位置 // 输出结果 if (index != -1) { printf("Pattern found at index %d\n", index); } else { printf("Pattern not found\n"); } return 0; }
运行结果:
KMP算法是一种高效的字符串匹配算法,通过计算模式字符串的部分匹配表(PMT),在匹配过程中利用已匹配的信息,避免了不必要的重复比较,提高了匹配效率。本文通过C语言实现KMP算法,帮助读者更好地理解KMP算法的原理和实现过程。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。