#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
int next[1000]; //记录跳转位置
int kmp_next(char *base)
{
int i,j;
i=0;
j=-1;
next[0]=-1; //记录第一个字符的跳转位置为-1
while(base[i]!='\0')
{
//如果跳转到-1,说明只能从头开始匹配;
//如果当前匹配点和跳转后的匹配点匹配
if(j==-1||(base[i]==base[j]))
{
//查看下一匹配点的情况
i++;
j++;
//如果下一匹配点还是匹配的,则下一跳地址一样
if(base[i]==base[j])
{
next[i]=next[j];
}
//如果一匹配点不匹配,则下一跳地址为当前前缀地址
else
{
next[i]=j;
}
}
else
{
j=next[j];
}
}
}
int kmp(char *b,char *base)
{
int i,j;
i=0;j=0;
//通过跳转数组,进行快速匹配
while(b[i]!='\0'&&base[j]!='\0')
{
if(b[i]==base[j])
{
i++;j++;
}
else
{
j=next[j];
if(j==-1)
{
i++;j++;
}
}
}
if(base[j]=='\0')
{
return i-j;
}
else
return -1;
}
int main()
{
char base[]="abacba";
char b[1000];
kmp_next(base);
for(int i=0;i<strlen(base);i++)
{
printf("%d ",next[i]);
}
printf("\n %s\n",base);
while(scanf("%s",b)!=EOF)
{
printf("%d \n",kmp(b,base));
}
system("pause");
}
分享到:
相关推荐
《C语言实现KMP算法详解》 KMP(Knuth-Morris-Pratt)算法是一种在文本串中高效地查找模式串(子串)的字符串匹配算法,由D.E. Knuth、V.R. Morris和J.H. Pratt三位学者于1970年提出。在C语言中实现KMP算法,可以...
《C语言实现的KMP算法详解》 KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由D.E.Knuth、V.R.Morris和J.H.Pratt三位学者于1977年提出。在计算机科学中,字符串匹配是查找一个字符串(模式)在另一个...
C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现...
在C语言中实现KMP算法,可以帮助我们理解算法的核心思想,并能应用于实际的编程任务中。 KMP算法的主要特点是避免了对已匹配部分的重复比较,从而提高了效率。当模式串中出现不匹配时,它不会像朴素算法那样回溯到...
7. 字符串处理:C语言中的KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,对于文本处理和数据分析至关重要。 8. 数据结构:链表、队列、栈、堆、树、图等,它们是算法的基石。理解这些数据结构的C语言实现,有助于...
- KMP算法:用于字符串匹配,避免不必要的回溯,时间复杂度为O(n)。 - Rabin-Karp算法:使用哈希函数进行字符串匹配,时间复杂度在最坏情况下为O(nm)。 7. **数据结构**: - 链表:包括单链表、双链表、循环链表...
kmp算法的实现(c语言)
KMP算法不仅限于C语言实现,它同样适用于其他编程语言。`帮助.docx`文件可能是对该算法的详细解释,或者是C代码的使用说明,可以帮助理解和应用这个算法。 总的来说,KMP算法是一种高效的模式匹配方法,通过避免...
在C语言中实现KMP算法,我们需要理解其核心思想和步骤。 1. **KMP算法的核心思想**: - KMP算法的关键在于构造一个部分匹配表(也叫失配表),用于记录当主串与模式串比较时,如果发生不匹配,模式串应如何移动以...
数据结构 KMP算法 源程序 c语言
void kmp_matcher(sstring s,sstring s1) { int i = 1,j=1; /* Number of characters mached */ int n = s.length; int m = s1.length; int *x = get_next (s1); while(i) { if(j==0 || s.p[i]==s1.p[j])...
在C语言中实现KMP算法,我们需要理解以下几个关键概念: 1. **前缀表(部分匹配表)**:这是KMP算法的核心,用于存储模式串(待查找的子串)中的部分匹配信息。前缀表记录了模式串中每个字符之前最长的公共前后缀...
在C语言中实现KMP算法,我们需要理解其核心思想并编写相应的代码。 1. **KMP算法的核心思想** - KMP算法的核心是构造一个“部分匹配表”(也称为“最长公共前后缀表”),用于记录模式串中的每个字符之前已经匹配...
在C语言中实现KMP算法,可以有效地处理字符串匹配问题,避免了朴素算法在匹配过程中频繁的回溯。 KMP算法的核心思想是利用已知的前缀和后缀的关系来提高匹配效率。它构建了一个部分匹配表(也称为失败函数或跳跃表...
### 字符串KMP算法C语言实现解析 在计算机科学领域,字符串匹配是常见的操作之一,其中KMP算法(Knuth-Morris-Pratt算法)因其高效性而被广泛使用。KMP算法由Donald Knuth、James H.Morris以及Vaughan Pratt共同...
使用C语言实现KMP算法,需要定义数据结构来存储部分匹配表,编写函数来构建此表,并实现主函数来完成字符串匹配。对于初学者而言,理解并实现KMP算法能帮助他们掌握动态规划的思想,提高解决实际问题的能力。通过...
串的替换,删除,查找 以及KMP算法的具体的实现 c语言 数据结构
用c实现的KMP算法,没有注释,不过程序逻辑清晰,适合了解算法的人观看
下面我们将详细介绍KMP算法的实现原理和C语言实现。 一、KMP算法的原理 KMP算法是由D.E.Knuth、V.R.Pratt和J.H.Morris共同提出的,因此它也被称为克努特-莫里斯-莫拉特操作。该算法的基本思想是:从主串的第POS个...
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)