`

KMP算法

阅读更多
这个KMP算法效率有点问题。有个地方又回溯了~Find out and fix it.
>> >>>>>>>>>>Okey。小哥,怎么样了?哥们写得一手好字啊~
这是修正后的代码:
voidkmpNextEx(char *pattern, int *next, int len) {
   int i = 1;
   int j = -1;
 
   next[0]= -1;
 
   while(i < len) {
      if(j == -1 || pattern[i - 1] == pattern[j]) {
        /* 注意这里:如果发现与上一次匹配的值相同,则直接将上一次匹配的值赋予给新的
         * next[i],这样可以改进如果Pattern有重复字符出现的情况
         */
        if(pattern[i - 1] != pattern[j - 1]) {
           next[i]= j + 1;
        }else {
           next[i]= next[j];
        }
        ++j;
        ++i;
      }
      else {
        j= next[j];
      }
   }
}
图片
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
voidkmpNext(char*, int*, int);
intkmpIndexOf(char*, char*);
intbfIndexOf(char*, char*);
 
int main(int argc, char*argv[]) {
   char *s1 = "2aaaaaaaaaaaaaaasdfasdf134123asdffffffo1asd1234\
      ffffasdf213fvzazxcnvjklnaskld./zca;sdjkfjaiou21o3elan'[ \
      123454154sa4df6548210ykzht4341bwasd1231234239r \
      4sauioj9j91u8hdjkadu9891nkjklfau12 \
      134j0zhcjkvuiuizuionvjjksanfjih2bjkbmzjkxvhiannzjkvjkla \
      4=01293=0ykzht4341bwasd123123423l";
   char *pat = "0ykzht4341bwasd123123423l";
   char *answer = (char*)malloc(sizeof(pat) + 1);
 
   printf("Patter:\t%s\n", pat);
   printf("%-20s%d\n", "ByKMP:", kmpIndex(s1, pat));
   strncpy(answer,s1 + kmpIndex(s1, pat), strlen(pat));
   answer[strlen(pat)]= '\0';
   printf("Answer:\t%s\n", answer);
   getchar();
 
   return 0;
}
 
intkmpIndex(char *strsrc, char*pattern) {
   int *next = (int*)malloc(sizeof(int) *strlen(pattern));
 
   int strsrcLen = strlen(strsrc);
   int patLen = strlen(pattern);
 
   int i = 0;
   int j = 0;
 
   kmpNext(pattern,next, strlen(pattern));
  
   while(i < strsrcLen && j < patLen) {
      if(j == -1 || strsrc[i] == pattern[j]) {
        //printf("%d\n", i);
        ++i;
        ++j;
      }
      else {
        j= next[j] - 1;
      }
   }
 
   if(j >= patLen) {
      return i - patLen;
   }
   else {
      return -1;
   }
}
 
voidkmpNext(char *pattern, int*next, int len) {
   int i = 2;
 
   int j = 1;
   int count = 0;
  
   next[0]= 0;
   next[1]= 1;
 
   while(i < len) {
      j= 0;
      count= 0;
      while(pattern[j] == pattern[i - j - 1] && j< i - 1) {
        count++;
        ++j;
      }
      if(count == 0) {
        count= 1;
      }
      next[i]= count;
      ++i;
   }
  
}

 

分享到:
评论

相关推荐

    KMP算法算法 KMP算法 KMP

    算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP

    KMP算法详解 KMP算法详解

    KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Morris和Robert Pratt三位学者提出。它的主要目标是在一个长字符串(主串A)中查找是否存在一个指定的短字符串(模式...

    数据结果 kmp算法实验报告

    ### 数据结果 KMP算法实验报告 #### 实验背景与目的 本实验主要针对《数据结构》课程中的字符串处理部分,具体涉及的是模式匹配算法——KMP算法。通过实验加深学生对串类型及其基本操作的理解,并重点掌握两种重要...

    传统KMP算法与改进KMP算法的对比

    KMP算法,全称为Knuth-Morris-Pratt算法,是一种在字符串中寻找子串的高效搜索算法。它由D.E. Knuth、V. Morris和J.H. Pratt三位学者于1970年提出,主要用于解决模式匹配问题。传统的KMP算法避免了不必要的字符比较...

    易语言KMP算法模块

    KMP算法是一种改进的字符串匹配算法,由Donald Knuth、Morris和Frank Pratt共同提出,其主要特点是在匹配过程中能够避免不必要的字符比较,从而提高搜索效率。 KMP算法的核心思想是构建一个部分匹配表(也称为失败...

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

    `KMP算法.cpp`文件应该包含了这些实现逻辑,通过编译生成的`KMP算法.exe`可执行文件可以直接运行并测试。 4. **性能分析** KMP算法的时间复杂度为O(n + m),其中n为主串长度,m为子串长度。这是因为即使最坏情况下...

    KMP算法实现模板(c++版)ACM算法

    **KMP算法实现模板(C++版) ACM算法** KMP(Knuth-Morris-Pratt)算法是一种在文本字符串中查找子串匹配的有效方法,尤其适用于已经预处理了模式串(子串)的匹配信息。它是由D.E. Knuth、V. Morris和J.H. Pratt...

    C++实现的KMP算法

    用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。

    模式匹配的KMP算法

    "模式匹配的KMP算法" 模式匹配的KMP算法是计算机科学领域中的一种经典算法,用于解决串的模式匹配问题。该算法可以高效地查找目标串中是否包含某个模式串,并返回模式串在目标串中的起始位置。 模式匹配的KMP算法...

    《字符串模式匹配KMP算法》教学课例设计[归纳].pdf

    《字符串模式匹配KMP算法》教学课例设计 在这篇教学设计中,我们旨在帮助学生掌握KMP字符串模式匹配算法的基本概念和应用。通过本课例设计,学生将了解KMP算法的应用普遍性、实现机制和时间复杂度,并掌握计算next...

    数据结构KMP算法

    数据结构中的KMP算法是一种高效的字符串匹配算法,由D.E.Knuth、V.J.Morris和J.H.Pratt三位学者提出,因此得名KMP(Knuth-Morris-Pratt)。该算法主要用于在一个文本串中查找一个模式串(即目标字符串)是否存在。...

    kmp算法的代码实现

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

    DS串应用--KMP算法

    DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法

    BF算法和KMP算法

    BF 算法和 KMP 算法在字符串匹配中的应用 BF 算法和 KMP 算法是两种常用的字符串匹配算法,分别应用于不同的场景中。本文将对这两种算法进行详细的分析和比较,以便更好地理解它们的原理和应用。 BF 算法 BF ...

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

    模式匹配中的KMP算法的实现 模式匹配是计算机科学领域中的一个研究热点,串的模式匹配算法是其中的一个重要分支。在模式匹配中,KMP算法是一个非常重要的算法,它可以高效地实现串的模式匹配。下面我们将详细介绍...

    字符串KMP算法c语言

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

    KMP算法KMP算法KMP算法KMP算法

    KMP算法,全称Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和 Vaughan Pratt三位学者在1970年提出。该算法主要用于解决在一个大文本串(A)中查找是否存在一个指定的小...

    KMP算法Flash演示

    数据结构中KMP算法过程的Flash演示

    KMP算法,求子字符串位置

    在数据结构和算法的学习中,理解并掌握KMP算法对于解决字符串匹配问题至关重要。 KMP算法的核心是构建一个“部分匹配表”(也称为“失败指针”或“前缀函数”),它记录了子字符串的每一个前缀和后缀的最大公共长度...

    Python实现字符串匹配的KMP算法

    kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串...

Global site tag (gtag.js) - Google Analytics