字符串模式匹配算法KMP算法及其改进
//得到子串搜索时的回退个数
void get_next(String T, int *next)
{
int i = 0, j = -1;//i,j分别表示子串中前缀和后缀的下标
next[0] = -1;//next初始化为-1
while(i < T.length)
{
if(j == -1 || T[i] == T[j])
{
i++;
j++;
if(T[i] != T[j])
next[i] = j;
else
next[i] = next[j];
}
else
j = next[j];
}
}
匹配算法
//S为主串,T为子串,从主串中第pos位开始匹配
int Index_KMP(String S, String T, int pos)
{
int next[255];//存放子串回退个数
int i = 0, j = 0;//i,j分别为主串S和子串T的下标。
//获得next
get_next(T,next);
while(i<S.length && j<T.length)
{
if(j == -1 || S[i] == T[j])
{
i++; j++;
}else
j = next[j];
}
//出while只有三种情况:a.主串遍历完,子串未完则---》查找失败,为找到
//b.主串完子串完,则找到返回 i-T.length+1
//c.主串未完,子串完 找到 返回结果 i-T.length+1
if(j >= T.length)
{
return i-T.length+1;
}else
return 0;//未找到
}
分享到:
相关推荐
KMP(Knuth-Morris-Pratt)模式匹配算法是一种在主串(目标字符串)中查找子串(模式字符串)的高效算法,由D.E. Knuth、V.R. Morris和J.H. Pratt于1977年提出。相较于简单的暴力匹配方法,KMP算法在模式匹配过程中...
KMP模式匹配算法C语言实现程序KMP模式匹配算法C语言实现程序
在本实验报告中,主题是“串的操作与KMP模式匹配算法”,这涉及到计算机科学中的字符串处理和算法设计。实验的目的是让学生掌握基本的串操作以及实现著名的Knuth-Morris-Pratt(KMP)模式匹配算法。串在计算机科学中指...
模式匹配算法主要有两种,分别是朴素模式匹配算法和KMP算法。KMP算法因其实现高效而备受关注,本文将详细解读KMP算法的工作原理及其实现过程。 KMP算法全称为Knuth-Morris-Pratt算法,由Donald Knuth、Vaughan ...
用C语言编写的kmp模式匹配算法 源代码
kmp算法KMP模式匹配算法C源码.zipKMP模式匹配算法C源码.zipKMP模式匹配算法C源码.zipKMP模式匹配算法C源码.zipKMP模式匹配算法C源码.zipKMP模式匹配算法C源码.zipKMP模式匹配算法C源码.zipKMP模式匹配算法C源码....
综上所述,KMP模式匹配算法是字符串处理中的一种高效算法,通过构建和使用next数组,避免了不必要的字符比较,提高了匹配效率。在C语言中实现KMP算法需要理解next数组的构建及其在匹配过程中的作用,同时,可以通过...
《KMP模式匹配算法在C++中的实现及字符串查找》 KMP(Knuth-Morris-Pratt)模式匹配算法是计算机科学中一种高效的字符串匹配算法,由D.E.Knuth、V.R.Morris和J.Pratt于1977年提出。它主要用于在一个长文本串(通常...
这里介绍的"4-4KMP模式匹配算法1"是Knuth-Morris-Pratt (KMP)算法的一种实现。KMP算法是一种高效的字符串匹配算法,它避免了不必要的字符比较,提高了匹配速度。 KMP算法的核心思想是通过构建一个部分匹配表...
### BF与KMP模式匹配算法的实现与应用 #### 一、Brute-Force(BF)算法 ##### 1.1 算法描述 **Brute-Force (BF)算法**是一种简单直接的字符串模式匹配算法。它通过将目标字符串(记作`target`)中的每一个可能的...
《大话数据结构》———C语言简单实现KMP模式匹配算法
KMP(Knuth-Morris-Pratt)算法是一种在文本串中高效地查找模式串的字符串匹配算法。它由D.E. Knuth、V. Morris和J.H. Pratt于1970年提出,主要用于解决计算机科学中的字符串处理问题。在C语言中实现KMP算法,可以...