首页 > 代码库 > 查找字符串的 KMP 算法
查找字符串的 KMP 算法
查找字符串是我们平常编程过程中经常遇到的，现在介绍一种查找字符串算法，增加程序的执行速度。
通常我们是这么写的：
/* content: search a string in a othor string author: lw date: 2015-01-30 target: kmp algorithm */#include <stdio.h>#include <string.h>void compare(char * sourcestr, char * targetstr){ char *moveSource, *moveTarget, *headPoint; int num = 0; headPoint = sourcestr; moveSource = sourcestr; moveTarget = targetstr; while(*headPoint != *moveTarget) headPoint++; moveSource = headPoint; while(*moveSource != ‘\0‘ && *moveTarget != ‘\0‘) { num++; moveSource++; moveTarget++; if(num == 3) break; while(*moveSource != *moveTarget)//-->kmp { headPoint = headPoint + 1; moveSource = headPoint; num = 0; moveTarget = targetstr; } } printf("%s\n", headPoint);}int main(){ char *source = "mabveacabiabcy"; char *target = "abc"; char *sourcestr; char *targetstr; sourcestr = (char *)malloc(15 * sizeof(char)); targetstr = (char *)malloc(4 * sizeof(char)); memset(sourcestr, ‘\0‘, 15 * sizeof(char)); memset(targetstr, ‘\0‘, 4 * sizeof(char)); strncpy(sourcestr, source, 15); strncpy(targetstr, target, 4); compare(sourcestr, targetstr); return 0;}
现在把函数 compare() 函数中的内 while() 中的内容改进一下：
说明：拿字符串 mabveacabiabcy 来说，当查找到字符 v 时发现和 abc 中的 c 不同，则指向字符串 mabveacabiabcy 中的第二个字符的指针就要移动，如果不使用 kmp 算法，那么指针移动一位，如果使用 kmp 算法，则指针移动两位，因为当比较到字符 v 时我们实际已经知道 v 以前的字符是什么了，所以可以断定不止要移动一位，具体移动几位就和字符串 abc 有关了，要判断其是否回文字符串，此例中 abc 对应数组 1,2,0 。
修改后的代码如下：
/* content: search a string in a othor string author: lw date: 2015-01-30 target: kmp algorithm */#include <stdio.h>#include <string.h>void compare(char * sourcestr, char * targetstr){ char *moveSource, *moveTarget, *headPoint; int num = 0; headPoint = sourcestr; moveSource = sourcestr; moveTarget = targetstr; while(*headPoint != *moveTarget) headPoint++; moveSource = headPoint; while(*moveSource != ‘\0‘ && *moveTarget != ‘\0‘) { num++; moveSource++; moveTarget++; if(num == 3) break; while(*moveSource != *moveTarget)//-->kmp { if(num > 0) headPoint = headPoint + num; else headPoint = headPoint + 1; moveSource = headPoint; num = 0; moveTarget = targetstr; } } printf("%s\n", headPoint);}int main(){ char *source = "mabveacabiabcy"; char *target = "abc"; char *sourcestr; char *targetstr; sourcestr = (char *)malloc(15 * sizeof(char)); targetstr = (char *)malloc(4 * sizeof(char)); memset(sourcestr, ‘\0‘, 15 * sizeof(char)); memset(targetstr, ‘\0‘, 4 * sizeof(char)); strncpy(sourcestr, source, 15); strncpy(targetstr, target, 4); compare(sourcestr, targetstr); return 0;}
查找字符串的 KMP 算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。