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;
       ++i;
     }
    else if(j==0)
     {
       j=-2;

     }
    else j=Next[j-1];
  }
}
int main()
{
  cout << "Hello world!" << endl;
  char pat[12]="actabactace";
  int next[11];
  preKmp(pat,11,next);
  for(int i=0;i<11;i++)
    cout<<"next["<<i<<"]="<<next[i]<<endl;
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • C++数据结构与算法之双缓存队列实现方法详解

    C++数据结构与算法之双缓存队列实现方法详解

    本文实例讲述了C++数据结构与算法之双缓存队列实现方法.分享给大家供大家参考,具体如下: "双缓存队列"是我在一次开发任务中针对特殊场景设计出来的结构.使用场景为:发送端持续向接收端发送数据包--并且不理会接收端是否完成业务逻辑.由于接收端在任何情况下停止响应即可能产生数据丢失,因此无法简单的设计一条线程安全队列来对数据写入或读取(读取数据时将队列上锁视为对写入的停止响应). 鉴于此,我的设计思路如下: 接收端首先向A队列中写入数据,然后当数据处理请求到来的时候切换到B队列继续写入,之

  • C++非递归队列实现二叉树的广度优先遍历

    本文实例讲述了C++非递归队列实现二叉树的广度优先遍历.分享给大家供大家参考.具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode*> q; // 队列 q.enqueue(root); TNode* p; while(q.hasElement()) { p = q.dequeue(); // 队首元素出队列 visit(p); // 访问p结点 if(p->left) q.enqu

  • C++ STL入门教程(3) deque双向队列使用方法

    一.简介 deque(Double Ended Queues,双向队列)和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <deque> #include <iostream> #include <algorithm> #include <stdexcept> using namespace std; void print(int num) { cout <&

  • C++中队列的建立与操作详细解析

    C++中队列的建立与操作详细解析

    什么是队列结构 队列结构是从数据运算来分类的,也就是说队列结构具有特殊的运算规则.而从数据的逻辑结构来看,队列结构其实就是一种线性结构.如果从数据的存储结构来进一步划分,队列结构可以分成两类. 顺序队列结构:即使用一组地址连续的内存单元依次保存队列中的数据.在程序中,可以定义一个指定大小的结构数组来作为队列. 链式队列结构:即使用链表形式保存队列中各元素的值. 在队列结构中允许对两端进行操作,但是两端的操作不同.在表的一端只能进行删除操作,称为队头:在表的另一端只能进行插入操作,称为队尾.如果队

  • 解析C++无锁队列的实现代码

    本文给出一种C++无锁队列的实现代码,主要用于一个线程读取数据另外一个线程写数据 复制代码 代码如下: #ifndef LOCK_FREE_QUEUE_H_#define LOCK_FREE_QUEUE_H_ //不加锁队列,适合一个线程读取,一个线程写#include <list>template <typename T>class LockFreeQueue{    public:        LockFreeQueue()        {             list

  • C++数据结构之实现循环顺序队列

    数据结构–用C++实现循环顺序队列 队列的操作特性:先进先出 队列中元素具有相同类型 相邻元素具有前驱和后继关系 设置队头.队尾两个指针,以改进出队的时间性能 约定:队头指针front指向队头元素的前一个位置,队尾指针rear指向队尾元素 为了解决假溢出,我们将存储队列的数组头尾相接,从而产生了循环队列. 如何判断循环队列队空? 队空:front=rear 如何盘对循环队列堆满? 队满:front=rear 那么问题就来了,队空和队满的判断条件相同,为了避免队满时产生队空的判断或者相反,我们需要

  • C++ 中消息队列函数实例详解

    C++ 中消息队列函数实例详解 1.消息队列结构体的定义 typedef struct{ uid_t uid; /* owner`s user id */ gid_t gid; /* owner`s group id */ udi_t cuid; /* creator`s user id */ gid_t cgid; /* creator`s group id */ mode_t mode; /* read-write permissions 0400 MSG_R 0200 MSG_W*/ ul

  • C++中实现队列类链式存储与栈类链式存储的代码示例

    队列类链式存储 代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le

  • C++中用两个标准容器stack,实现一个队列的方法详解

    代码如下所示: 复制代码 代码如下: // StackToQueue.cpp : 定义控制台应用程序的入口点.//用两个标准容器stack,实现一个队列#include "stdafx.h"#include <iostream>#include <stack>using namespace std;template <class T>class StackToQueue{public: StackToQueue() {  stack1;  stack

  • C++数据结构与算法之判断一个链表是否为回文结构的方法

    本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

  • C++ 数据结构实现两个栈实现一个队列

    C++ 数据结构实现两个栈实现一个队列 栈为后进先出,队列为先进先出 用两个栈实现一个队列.是一个比较经典的问题. 看到这个问题,我的第一个解题思路为: 定义两个栈,s1,s2.s1作为入队列栈,s2作为出队列栈: 入队列:每次入队列的时候,将数值压入s1栈中: 出队列:出队列时,将s1中的所有数据,压进s2栈中,然后删除s2的栈顶数据,然后再将s2中的剩余数据压入s1中. 在这其中s1是一个存储空间,s2是一个辅助空间. 进一步想一下上述办法,在出队列时,每一次都要将s1倒进s2,然后删除s2

  • C++循环队列实现模型

    本文实例讲述了C++循环队列实现模型.分享给大家供大家参考.具体分析如下: 前段时间在知乎上看到这样一个小题目: 用基本类型实现一队列,队列要求size是预先定义好的的.而且要求不可以使用语言自带的api,如C++的STL.普通的实现很简单,但是现在要求要尽可能的时间和空间复杂度的优化,要和语言自带的api比较时间和空间.这个队列还要支持如下的操作: constructor: 初始化队列 enqueue:入队 dequeue:出队 队列是一种基本的数据结构,在平常的应用中十分广泛,多数情况队列都

随机推荐