`
shaojiashuai123456
  • 浏览: 262704 次
  • 性别: Icon_minigender_1
  • 来自: 吉林
社区版块
存档分类
最新评论

kmp算法 --c语言实现

 
阅读更多
#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");
}

 

分享到:
评论

相关推荐

    kmp算法-基于C语言实现KMP算法.zip

    《C语言实现KMP算法详解》 KMP(Knuth-Morris-Pratt)算法是一种在文本串中高效地查找模式串(子串)的字符串匹配算法,由D.E. Knuth、V.R. Morris和J.H. Pratt三位学者于1970年提出。在C语言中实现KMP算法,可以...

    kmp算法-基于C语言kmp算法实现的字符串匹配.zip

    《C语言实现的KMP算法详解》 KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由D.E.Knuth、V.R.Morris和J.H.Pratt三位学者于1977年提出。在计算机科学中,字符串匹配是查找一个字符串(模式)在另一个...

    C语言实现kmp算法的C语言实现源码.zip

    C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现...

    kmp算法-基于C语言实现的kmp模式匹配算法.zip

    在C语言中实现KMP算法,可以帮助我们理解算法的核心思想,并能应用于实际的编程任务中。 KMP算法的主要特点是避免了对已匹配部分的重复比较,从而提高了效率。当模式串中出现不匹配时,它不会像朴素算法那样回溯到...

    C 语言算法集--超多C语言算法实现

    7. 字符串处理:C语言中的KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,对于文本处理和数据分析至关重要。 8. 数据结构:链表、队列、栈、堆、树、图等,它们是算法的基石。理解这些数据结构的C语言实现,有助于...

    c语言常用算法-----列举C语言各种常用算法

    - KMP算法:用于字符串匹配,避免不必要的回溯,时间复杂度为O(n)。 - Rabin-Karp算法:使用哈希函数进行字符串匹配,时间复杂度在最坏情况下为O(nm)。 7. **数据结构**: - 链表:包括单链表、双链表、循环链表...

    kmp算法的实现(c语言)

    kmp算法的实现(c语言)

    数据结构(C语言)--模式匹配--KMP算法

    KMP算法不仅限于C语言实现,它同样适用于其他编程语言。`帮助.docx`文件可能是对该算法的详细解释,或者是C代码的使用说明,可以帮助理解和应用这个算法。 总的来说,KMP算法是一种高效的模式匹配方法,通过避免...

    KMP算法实现(C语言)

    在C语言中实现KMP算法,我们需要理解其核心思想和步骤。 1. **KMP算法的核心思想**: - KMP算法的关键在于构造一个部分匹配表(也叫失配表),用于记录当主串与模式串比较时,如果发生不匹配,模式串应如何移动以...

    数据结构 KMP算法 源程序 c语言

    数据结构 KMP算法 源程序 c语言

    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])...

    KMP算法的C语言实现

    在C语言中实现KMP算法,我们需要理解以下几个关键概念: 1. **前缀表(部分匹配表)**:这是KMP算法的核心,用于存储模式串(待查找的子串)中的部分匹配信息。前缀表记录了模式串中每个字符之前最长的公共前后缀...

    kmp算法模式匹配的实现-C语言.zip

    在C语言中实现KMP算法,我们需要理解其核心思想并编写相应的代码。 1. **KMP算法的核心思想** - KMP算法的核心是构造一个“部分匹配表”(也称为“最长公共前后缀表”),用于记录模式串中的每个字符之前已经匹配...

    KMP算法C语言实现

    在C语言中实现KMP算法,可以有效地处理字符串匹配问题,避免了朴素算法在匹配过程中频繁的回溯。 KMP算法的核心思想是利用已知的前缀和后缀的关系来提高匹配效率。它构建了一个部分匹配表(也称为失败函数或跳跃表...

    字符串KMP算法c语言

    ### 字符串KMP算法C语言实现解析 在计算机科学领域,字符串匹配是常见的操作之一,其中KMP算法(Knuth-Morris-Pratt算法)因其高效性而被广泛使用。KMP算法由Donald Knuth、James H.Morris以及Vaughan Pratt共同...

    kmp算法,C语言实现

    使用C语言实现KMP算法,需要定义数据结构来存储部分匹配表,编写函数来构建此表,并实现主函数来完成字符串匹配。对于初学者而言,理解并实现KMP算法能帮助他们掌握动态规划的思想,提高解决实际问题的能力。通过...

    串的基本操作 kmp算法实现

    串的替换,删除,查找 以及KMP算法的具体的实现 c语言 数据结构

    KMP算法 C语言实现

    用c实现的KMP算法,没有注释,不过程序逻辑清晰,适合了解算法的人观看

    模式匹配中的KMP算法的实现

    下面我们将详细介绍KMP算法的实现原理和C语言实现。 一、KMP算法的原理 KMP算法是由D.E.Knuth、V.R.Pratt和J.H.Morris共同提出的,因此它也被称为克努特-莫里斯-莫拉特操作。该算法的基本思想是:从主串的第POS个...

    kmp算法的代码实现

    数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)

Global site tag (gtag.js) - Google Analytics