c语言中使用BF-KMP算法实例

2024-03-02 09:11:19

直接上代码

代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_SIZE 255 //定义字符串的最大长度

typedef unsigned char SString[MAX_SIZE];//数组第一个保存长度
//BF
int BFMatch(char *s,char *p)
{
    int i,j;
    i=0;
    while(i < strlen(s))
    {
        j=0;
        while(s[i]==p[j]&&j < strlen(p))
        {
            i++;
            j++;
        }
        if(j==strlen(p))
            return i-strlen(p);
        i=i-j+1;                //指针i回溯
    }
    return -1;
}
//getNetx
void getNext(char *p,int *next)
{
    int j,k;
    next[0]=-1;
    j=0;
    k=-1;
    while(j < strlen(p)-1)
    {
        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]
        {
            j++;
            k++;
            next[j]=k;
        }
        else
        {                  //p[j]!=p[k]
            k=next[k];
        }
    }
}

//KMP
int KMPMatch(char *s,char *p)
{
    int next[100];
    int i,j;
    i=0;
    j=0;
    getNext(p,next);
    while(i < strlen(s))
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];       //消除了指针i的回溯
        }
        if(j==strlen(p))
        {
            return i-strlen(p);
        }
    }
    return -1;
}

int main()
{
int a, b;
char s[MAX_SIZE], p[MAX_SIZE];

printf("请输入模式串：");
    scanf("%s", &s);
    printf("请输入子串：");
    scanf("%s", &p);

a = BFMatch(s, p);
b = KMPMatch(s, p);

if(a != -1)
    {
        printf("使用BF算法：%d\n", a);
    }
    else
    {
        printf("未匹配\n");
    }

if(b != -1)
    {
        printf("使用KMP算法：%d\n", a);
    }
    else
    {
        printf("未匹配\n");
    }

system("pause");
}

结果

代码如下:

请输入模式串：lalalalalaaaa
请输入子串：lalaa
使用BF算法：6
使用KMP算法：6
请按任意键继续. . .

C语言实现字符串匹配KMP算法

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

以前看过kmp算法,当时接触后总感觉好深奥啊,抱着数据结构的数啃了一中午,最终才大致看懂,后来提起kmp也只剩下"奥,它是做模式匹配的"这点干货.最近有空,翻出来算法导论看看,原来就是这么简单(下不说程序实现,思想很简单). 模式匹配的经典应用:从一个字符串中找到模式字串的位置.如"abcdef"中"cde"出现在原串第三个位置.从基础看起朴素的模式匹配算法 A:abcdefg B:cde 首先B从A的第一位开始比较,B++==A++,如果全
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语言中实现KMP算法的实例讲解

一般的算法为什么这么低效呢?那是因为主串指针回溯情况过多: 主串指针如果不回溯的话,速度就会加快,那我们就会想: 如何让主串指针不回溯? KMP算法就是解决了这个问题,所以速度变得更快速了. 它是这样子的: 用一个数组:next[] 求得失配时的位置,然后保存下来. 要说清楚KMP算法,可以从朴素的模式匹配算法说起. 朴素的模式匹配算法比较容易理解,其实现如下 int Index(char s[], char p[], int pos) { int i, j, slen, plen; i =
字符串的模式匹配详解--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
KMP算法精解及其Python版的代码示例

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

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

C语言中数据结构之链表归并排序实例代码问题设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏. 源程序 #include <stdio.h> #include<stdlib.h> #define N1 6 /*链表La的长度*/ #define N2 6 /*链表Lb的
C语言中枚举与指针的实例详解

C语言中枚举与指针的实例详解总结一下, 定义枚举,用typedef enum关键字, 比如 typedef enum{Red,Green,Blue} Color3; 枚举到数值的转换,如果没有指定代表数值就是从0开始算, 比如 Color3 c=Red; printf("%d",c);会显示0, 除非指定如typedef enum{Red=3,Green=5,Blue=10} Color3; 关于类型指针的定义, 定义的时候在变量名左边加*代表此变量只是一个空指针而已, 若需要赋
KMP 算法实例详解

KMP 算法实例详解 KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式匹配算法. 分析:KMP模板题.KMP的关键是求出next的值.先预处理出next的值.然后一遍扫过.复杂度O(m+n) 实例代码: #include<stdio.h> #include<string.h> #define N 1000005 int s[N]; int p[N]; int n
C语言中实现itoa函数的实例

C语言中实现itoa函数的实例一.原型: char *itoa( int value, char *string,int radix); 二.函数说明: value:欲转换的数据. string:目标字符串的地址. radix:转换后的进制数,可以是10进制.16进制等. 三.函数简单实现: #include <iostream> #include <string> using namespace std; char* My_itoa(int value,char str[],i
Java语言中的自定义类加载器实例解析

本文研究的主要是Java语言中的自定义类加载器实例解析的相关内容,具体如下. 自己写的类加载器需要注意的是:如果想要对这个实例进行测试的话,首先需要在c盘建立一个c://myjava的目录.然后将相应的java文件放在这个目录中.并将产生的.clas文件放在c://myjava/com/lg.test目录下,否则是找不到的.这是要注意的.. class FileClassLoader : package com.lg.test; import java.io.ByteArrayOutputSt
列举java语言中反射的常用方法及实例代码

Java反射机制一.什么是反射机制简单的来说,反射机制指的是程序在运行时能够获取自身的信息.在java中,只要给定类的名字, 那么就可以通过反射机制来获得类的所有信息. 二.哪里用到反射机制有些时候,我们用过一些知识,但是并不知道它的专业术语是什么,在刚刚学jdbc时用过一行代码, Class.forName("com.mysql.jdbc.Driver.class").newInstance();但是那时候只知道那行代码是生成驱动对象实例,并不知道
R语言中字符串的拼接操作实例讲解

在R语言中 paste 是一个很有用的字符串处理函数,可以连接不同类型的变量及常量. 函数paste的一般使用格式为: paste(..., sep = " ", collapse = NULL) 其中-表示一个或多个R可以被转化为字符型的对象:参数sep表示分隔符,默认为空格:参数collapse可选,如果不指定值,那么函数paste的返回值是自变量之间通过sep指定的分隔符连接后得到的一个字符型向量:如果为其指定了特定的值,那么自变量连接后的字符型向量会再被连接成一个字符串,之间
GO语言中常见的排序算法使用示例

目录快排冒泡选择排序插入排序希尔排序二分法查找快排 package main import ( "fmt" "math/rand" "time" ) func main() { li:=[]int{1,3,5,2,4,6,9,7} left:=0 right:=len(li)-1 fmt.Println(quick_sort(li,left,right)) } func quick_sort(li []int, left,right
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 =

c语言中使用BF-KMP算法实例

相关推荐

随机推荐