c++ 实现KMP算法

2024-10-11 19:49:05

KMP

KMP算法解决的问题

字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中开始的位置。

如何做到时间复杂度O(N)完成？

思路：

首先判断两个字符串是否为空串，并且str2的长度是否小于str1的长度，因为题目要求str1中包含str2。

以上都满足的情况下，首先定义两个变量分别为 x ，y 作为后续字符串中字符遍历的下标，然后再生成一个vector容器next，用来后续的匹配加速

然后在str2中，做加速操作，也就是看当前 i - 1和之前的所有字符，有没有相同的，最大匹配长度。

从上图可以看到，下标0和1位置的值永远都是固定的-1和0,。

x 字符是 i 位置，x 前面的 c 是 i - 1 位置，也就是从下标0位置到5位置，找最大的匹配长度，然后填到 i 的next中。这是循环中的case1

如果当next中的值大于0的时候，从b开始，找到next中的2位置，然后跳转到当前位置的next中的坐标上，接着进行匹配。

最后如果到next为0或者-1的位置上，就标记当前位置为0，然后到下一个坐标继续判断。

当 i 遍历完str2后，循环结束，代表next中的值已经全部设置好了。

当str1 和 str2 没有循环遍历到尾部的时候，只要 str1 中 x 的位置等于 str2 中 y 的位置，x 和 y 就同时自增。

如果next中的值等于 -1 ，就说没有匹配成功，x 单独自增。让str1往后挪一位

如果str2中的没有匹配成功，就往前找next数组的值，只要不等于 -1 ，就一直执行这个往前移的过程。

最后看 y 是否已经到了str2的位置，如果到了就说明找到了，直接返回 x的位置减去 y的位置，就是匹配开始的位置，否则就是没有找到，直接返回 -1

void getNextArray(string str, vector<int>& next)
{
  if (str.length() == 1)
  {
    next.push_back(-1);
  }
  next.resize(str.length());
  next[0] = -1;
  next[1] = 0;
  int i = 2;
  int cn = 0;
  while (i < next.size())
  {
    if (str[i - 1] == str[cn])
    {
      next[i++] = ++cn;
    }
    else if (cn > 0)
    {
      cn = next[cn];
    }
    else {
      next[i++] = 0;
    }
  }
}

int getIndexOf(string s, string m)
{
  if (s == "" || m == "" || s.length() < 1 || s.length() < m.length())
  {
    return -1;
  }
  int x = 0;
  int y = 0;
  vector<int> next;
  getNextArray(m,next);
  while (x < s.length() && y < m.length())
  {
    if (s[x] == m[y])
    {
      x++;
      y++;
    }
    else if (next[y] == -1)
    {
      x++;
    }
    else {
      y = next[y];
    }
  }
  return y == m.length() ? x - y : -1;
}

以上就是c++ 实现KMP算法的详细内容，更多关于c++ KMP算法的资料请关注我们其它相关文章！

C++求所有顶点之间的最短路径（用Dijkstra算法）

本文实例为大家分享了C++求所有顶点之间最短路径的具体代码,供大家参考,具体内容如下一.思路: 不能出现负权值的边 (1)轮流以每一个顶点为源点,重复执行Dijkstra算法n次,就可以求得每一对顶点之间的最短路径及最短路径长度,总的执行时间为O(n的3次方) (2)另一种方法:用Floyd算法,总的执行时间为O(n的3次方)(另一文章会写) 二.实现程序: 1.Graph.h:有向图 #ifndef Graph_h #define Graph_h #include <iostream> u
c++如何实现Base64算法

Base64用途 1.用于对SOHO级路由器(网关设备)管理员帐户密码的加密 2.流媒体网站对于播放的流媒体文件的路径的加密 3.迅雷等下载软件对下载链接地址的加密 Base64算法 Base64编码要求把3个8位字节(3*8=24)转化为4个6位的字节(4*6=24),之后在6位的前面补两个0,形成8位一个字节的形式. Base64类函数: unsigned int CreateMatchingEncodingBuffer (unsigned int p_InputByteCount, ch
C++简单实现Dijkstra算法

本文实例为大家分享了C++简单实现Dijkstra算法的具体代码,供大家参考,具体内容如下 // Dijkstra.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <iostream> #include <stack> #define MAX_VALUE 1000 using namespace std; struct MGraph { int *edges[MAX_VALUE]; int iVertex
C++ 数据结构之kmp算法中的求Next()函数的算法

C++ 数据结构之kmp算法中的求Next()函数的算法实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++
C++实现快速排序(Quicksort)算法

本文实例为大家分享了C++快速排序算法,供大家参考,具体内容如下一.基本思想是: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 二.方法1实现程序:左右两个方向扫描 // 快速排序:选第一个对象作为基准,按照该对象的排序码大小,将整个对象 // 序列划分为左右两个字序列: // 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码: /
C++实现哈夫曼树算法

如何建立哈夫曼树的,网上搜索一堆,这里就不写了,直接给代码. 1.哈夫曼树结点类:HuffmanNode.h #ifndef HuffmanNode_h #define HuffmanNode_h template <class T> struct HuffmanNode { T weight; // 存储权值 HuffmanNode<T> *leftChild, *rightChild, *parent; // 左.右孩子和父结点 }; #endif /* HuffmanNode
C++实现Dijkstra(迪杰斯特拉)算法

Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,是广度优先算法的一种,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离.当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性.不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破
C++实现Dijkstra算法

本文实例为大家分享了C++实现Dijkstra算法的具体代码,供大家参考,具体内容如下 #include <iostream> #include <limits> using namespace std; struct Node { //定义表结点 int adjvex; //该边所指向的顶点的位置 int weight;// 边的权值 Node *next; //下一条边的指针 }; struct HeadNode{ // 定义头结点 int nodeName; // 顶点信息
java 中模式匹配算法-KMP算法实例详解

java 中模式匹配算法-KMP算法实例详解朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的
python实现的二叉树算法和kmp算法实例

主要是:前序遍历.中序遍历.后序遍历.层级遍历.非递归前序遍历.非递归中序遍历.非递归后序遍历复制代码代码如下: #!/usr/bin/env python#-*- coding:utf8 -*- class TreeNode(object): def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right =
KMP算法精解及其Python版的代码示例

KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题.算法名称来源于发明者Knuth,Morris,Pratt. 假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm). 朴素的字符串查找方法从字符串S的第一个字符开始与M进行比较,如果匹配失败.从下一字符开始,重新比较.指导第 (ls - lm) 个字符. 这种方法容易想到并且容易理解,效率不高. 问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些. KMP的字符串查找方法假定在模式
字符串的模式匹配详解--BF算法与KMP算法

一.BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果. 举例说明: S: ababcababa P: ababa BF算法匹配的步骤如下 i=0 i=1 i=2 i=3 i=4 第一趟:ababcababa 第二趟:ababcababa 第三趟:ababcababa 第四趟:ababcabab
C语言中实现KMP算法的实例讲解

一般的算法为什么这么低效呢?那是因为主串指针回溯情况过多: 主串指针如果不回溯的话,速度就会加快,那我们就会想: 如何让主串指针不回溯? KMP算法就是解决了这个问题,所以速度变得更快速了. 它是这样子的: 用一个数组:next[] 求得失配时的位置,然后保存下来. 要说清楚KMP算法,可以从朴素的模式匹配算法说起. 朴素的模式匹配算法比较容易理解,其实现如下 int Index(char s[], char p[], int pos) { int i, j, slen, plen; i =
JavaScript中数据结构与算法(五)：经典KMP算法

KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从左到右后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右. 通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上蛋疼的KMP是讲解很多,基本都是走的高大上路线看的你也是一头雾水,我试图用自己的理解用最接地气的方式描述 KMP KMP也是一种优化版的
C语言实现字符串匹配KMP算法

字符串匹配是计算机的基本任务之一. 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KMP算法的解释步骤 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较.因为B与A不匹配,所以搜索词后移一位. 2. 因为B与A不匹配,搜索词再往后移. 3. 就这样,直到字符
JAVA实现KMP算法理论和示例代码

一.理论准备KMP算法为什么比传统的字符串匹配算法快?KMP算法是通过分析模式串,预先计算每个位置发生不匹配的时候,可以省去重新匹配的的字符个数.整理出来发到一个next数组, 然后进行比较,这样可以避免字串的回溯,模式串中部分结果还可以复用,减少了循环次数,提高匹配效率.通俗的说就是KMP算法主要利用模式串某些字符与模式串开头位置的字符一样避免这些位置的重复比较的.例如主串: abcabcabcabed ,模式串:abcabed.当比较到模式串'e'字符时不同的时候完全没有必要从模式串开始位
深入串的模式匹配算法(普通算法和KMP算法)的详解

串的定位操作通常称作串的模式匹配,是各种处理系统中的最重要操作之一.模式匹配最朴素的算法是回溯法,即模式串跟主串一个字符一个字符的匹配,当模式串中跟主串不匹配时,主串回溯到与模式串匹配开始的下一个位置,模式串回溯到第一个位置,继续匹配.算法的时间复杂度为O(m*n),算法如下: 复制代码代码如下: //朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替{

c++ 实现KMP算法

相关推荐

随机推荐