程序员经验分享-hwhale

《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法）

2023-11-09

一、实验目的

1、了解串的基本概念。

2、掌握串的模式匹配算法的实现 。

二、实验预习

说明以下概念

1、模式匹配：

        串的模式匹配就是子串的定位运算。

        设有两个字符串 S 和 T ，S为主串(正文串)，T为子串(模式串)。在主串S中查找与模式串T相匹配的子串，若匹配成功，确定相匹配的子串中的第一个字符主串S中出现的位置。

2、BF算法：

        即暴力破解算法(Brute Force)，属于模式匹配算法中的一种。

        算法思想：从主串和模式串的第一个字符开始比较，匹配成功则进行下一字符的比较；匹配失败则主串比较的字符回溯到初始比较字符的下一位，而模式串比较的字符回溯到模式串第一个字符，接着继续进行字符比较。

3、KMP算法：

        KMP算法也属于模式匹配算法的一种，是一种改进后的匹配算法。

        KMP算法的改进在于当出现字符不匹配时，主串比较的字符无需回溯，而模式串则利用已经匹配成功的部分字符，确定模式串回溯的位置（无需回溯到第一个字符）。

        KMP算法减少了模式串与主串的匹配次数，达到快速匹配的目的。

三、实验内容和要求

 ！注  ！

        本实验中的字符数组 data 从下标为0的数组分量开始存储字符串。部分教材为便于说明问题，字符串从下标为1的数组分量开始存储，下标为0的分量闲置不用，故代码略有区别。

1、阅读并运行下面程序，根据输入写出运行结果。

#include<stdio.h>
#include<string.h>
#define MAXSIZE 100  //串的最大长度

typedef struct{
	char data[MAXSIZE];  //存储串的一维数组（从下标为0的数组分量开始存储字符串）
	int length;          //串的当前长度
}SqString;

int strCompare(SqString *s1,SqString *s2);  /*串的比较*/
void show_strCompare();
void strSub(SqString *s,int start,int sublen,SqString *sub);  /*求子串*/
void show_subString();

int strCompare(SqString *s1,SqString *s2){
	int i;
	for(i=0;i<s1->length && i<s2->length;i++)
		if(s1->data[i] != s2->data[i])
			return s1->data[i] - s2->data[i];
    //字符比较完成，还需比较字符串长度
	return s1->length - s2->length;
	/* s1=s2,返回值=0
	   s1>s2,返回值>0
       s1<s2,返回值<0 */
}

void show_strCompare(){
    SqString s1,s2;
    int k;
    printf("\n***show Compare***\n");
    printf("input string s1:");
    gets(s1.data);
    s1.length=strlen(s1.data);
    printf("input string s2:");
    gets(s2.data);
    s2.length=strlen(s2.data);
    if((k=strCompare(&s1,&s2))==0)
        printf("s1=s2\n");
    else if(k<0)
        printf("s1<s2\n");
    else
        printf("s1>s2\n");
    printf("\n***show over***\n");
}

void strSub(SqString *s,int start,int sublen,SqString *sub){
	int i;
	if(start<1 || start>s->length || sublen>s->length-start+1)
		sub->length = 0;
    else
    {
        for(i=0;i<sublen;i++)
		sub->data[i]=s->data[start+i-1];
	    sub->length=sublen;
    }
}

void show_subString(){
    SqString s,sub;
    int start,sublen,i;
    printf("\n***show subString***\n");
    printf("input string s:");
    gets(s.data);
    s.length=strlen(s.data);
    printf("input start:");
    scanf("%d",&start);
    printf("input sublen:");
    scanf("%d",&sublen);
    strSub(&s,start,sublen,&sub);
    if(sub.length==0)
        printf("ERROR!\n");
    else{
        printf("subString is:");
        for(i=0;i<sublen;i++)
            printf("%c",sub.data[i]);
    }
    printf("\n***show over***\n");
}

int main(){
    int n;
    do{
        printf("\n---String---\n");
        printf("1. strCompare\n");
        printf("2. subString\n");
        printf("0. EXIT\n");
        printf("\ninput choice:");
        scanf("%d",&n);
        getchar();
        switch(n){
            case 1:
                show_strCompare();
                break;
            case 2:
                show_subString();
                break;
            default:
                n=0;
                break;
        }
    }while(n);
    return 0;
}

输入：

1

student

students

2

Computer Data Stuctures

10

4

运行结果：

2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。

#include<stdio.h>
#include<string.h>

#define MAXSIZE 100  //串的最大长度

typedef struct{
	char data[MAXSIZE];  //存储串的一维数组（从下标为0的数组分量开始存储字符串）
	int length;          //串的当前长度
}SqString;

int index_bf(SqString *s,SqString *t,int start);              /*模式匹配-BF算法*/
void getNext(SqString *t,int next[]);                         /*计算目标串的next数组*/
int index_kmp(SqString *s,SqString *t,int start,int next[]);  /*模式匹配-KMP算法*/
void show_index();

int index_bf(SqString *s,SqString *t,int start){
    //补充代码 
}

void getNext(SqString *t,int next[]){  /*计算模式串t的next数组*/
	int i=0;
	int j=-1;
	next[0]=-1;
	while(i < t->length){
		if(-1==j || (t->data[i]==t->data[j]))
		{
			i++;
			j++;
			next[i]=j;
		}
		else
            j=next[j];
	}
}

int index_kmp(SqString *s,SqString *t,int start,int next[]){
    //补充代码
}

void show_index(){
	SqString s,t;
	int k;
	int i;
	int next[MAXSIZE]={0};
	int nextval[MAXSIZE]={0};
	printf("\n***show index***\n");
	printf("input string s:");
	gets(s.data);
	s.length=strlen(s.data);
	printf("input string t:");
	gets(t.data);
	t.length=strlen(t.data);
	printf("input start position(1≤start position≤%d):",s.length);
	scanf("%d",&k);
	printf("BF:\nthe result of BF is %d\n",index_bf(&s,&t,k));
	getNext(&t,next);
	printf("KMP:\n");
	printf("next[]:");
	for(i=0;i<t.length;i++)
	    printf("%3d",next[i]);
	printf("\n");
	printf("the result of KMP is %d\n",index_kmp(&s,&t,k,next));
	printf("\n***show over***\n");
}

int main(){
	show_index();
	return 0;
}

BF算法代码：

int index_bf(SqString *s,SqString *t,int start){  /*返回模式串t在主串s中第start个字符开始第一次出现的位置;若不存在,返回0*/
    //模式串t长度为0 或 起始查找位置超出主串范围:直接返回0
    if(0 == t->length || start < 1 || start > s->length)
        return (0);
    int pos=start-1;  //pos记录主串s开始匹配的字符下标
    int i=pos;        //i指向主串s当前正待比较的字符下标
    int j=0;          //j指向模式串t当前正待比较的字符下标
    while( i < s->length && j < t->length )
    {
        if(s->data[i] == t->data[j])  //匹配成功:i,j都++,继续比较后续字符
        {
            i++;
            j++;
        }
        else  //匹配失败
        {
            pos++;  //主串开始匹配的位置+1
            i=pos;  //i回溯到主串初始位置下一字符
            j=0;    //j回溯到模式串第一个字符
        }
    }
    if(j >= t->length)
        return (pos-start+2);  //返回模式串t在主串s中第start个字符开始第一次出现的位置
    else
        return (-1);  //查找失败,返回-1
}/*index_bf*/

KMP算法代码：

int index_kmp(SqString *s,SqString *t,int start,int next[]){  /*返回模式串t在主串s中第start个字符开始第一次出现的位置;若不存在,返回0*/
    //模式串t长度为0 或 起始位置超出主串范围:直接返回0
    if(0 == t->length || start < 1 || start > s->length)
        return (0);
    int i=start-1;  //i指向主串s当前正待比较的字符下标
    int j=0;        //j指向模式串t当前正待比较的字符下标
    while(i<s->length && j<t->length)
    {
        if(-1 == j || (s->data[i] == t->data[j]))
        {
            i++;
            j++;
        }
        else  //匹配失败
        {
            j=next[j];  //i不回溯,j回溯到next[j]
        }
    }
    if(j>=t->length)
        return (i-j-start+2);  //返回模式串t在主串s中第start个字符开始第一次出现的位置
    else
        return (-1);  //查找失败,返回-1
}/*index_kmp*/

输入：

abcaabbabcabaacbacba

abcabaa

1

运行结果：

3、在第2题的基础上，对next数组进行改进，实现计算目标串的nextval数组的算法，并进行验证。

nextval数组算法代码：

void getNextVAL(SqString *t,int nextval[]){  /*计算模式串t的nextval数组*/
	int i=0;
	int j=-1;
	nextval[0]=-1;
	while(i < t->length){
		if(-1 == j || (t->data[i]==t->data[j]))
		{
			i++;
			j++;
			if(t->data[i] != t->data[j])
                nextval[i]=j;
            else
                nextval[i]=nextval[j];
		}
		else
            j=nextval[j];
	}
}/*getNextVAL*/

show_index函数补充代码：

void show_index(){
	SqString s,t;
	int k;
	int i;
	int next[MAXSIZE]={0};
	int nextval[MAXSIZE]={0};
	printf("\n***show index***\n");
	printf("input string s:");
	gets(s.data);
	s.length=strlen(s.data);
	printf("input string t:");
	gets(t.data);
	t.length=strlen(t.data);
	printf("input start position(1≤start position≤%d):",s.length);
	scanf("%d",&k);
	printf("BF:\nthe result of BF is %d\n",index_bf(&s,&t,k));
	getNext(&t,next);
    getNextVAL(&t,nextval);
	printf("KMP:\n");
	printf("   next[]:");
	for(i=0;i<t.length;i++)
	    printf("%3d",next[i]);
	printf("\n");
    printf("nextval[]:");
	for(i=0;i<t.length;i++)
	    printf("%3d",nextval[i]);
	printf("\n");
	printf("the result of KMP is %d\n",index_kmp(&s,&t,k,nextval));
	printf("\n***show over***\n");
}

输入：

abcaabbabcabaacbacba

abcabaa

1

运行结果：

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

c语言

BF算法

KMP算法

《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法） 的相关文章

  • 学一点Wi-Fi：WPA3 BP/OCV/SCV/PK/H2E/TD

    WFA在2020年底发布了WPA3标准的第三版 其中又提出了一些新的feature 这里结合之前的版本简单总结一下 1 BP BP是Beacon Protection的缩写 问 Beacon中的信息都是未加密的 所以可能存在攻击者会对AP发

  • 课设：影院管理系统

    影院管理系统 导言 知识点总结 课设介绍 导言 从3月份开始到现在 大概两周多的时间 写了一个影院管理系统 功能有待改善 有的功能还有点bug需要该 现在总结一下 影院管理系统告一段落 接下来要学习算法和数据结构 知识点总结 一 三层架构

  • 一文看懂npm、yarn、pnpm之间的区别

    本文作者对比了当前主流的包管理工具npm yarn pnpm之间的区别 并提出了合适的使用建议 以下为译文 NPM npm是Node js能够如此成功的主要原因之一 npm团队做了很多的工作 以确保npm保持向后兼容 并在不同的环境中保持一

  • 大数据毕设选题 - 深度学习口罩佩戴检测系统（python OpenCV YOLO）

    文章目录 0 前言 1 课题介绍 2 算法原理 2 1 算法简介 2 2 网络架构 3 关键代码 4 数据集 4 1 安装 4 2 打开 4 3 选择yolo标注格式 4 4 打标签 4 5 保存 5 训练 6 实现效果 6 1 pyqt实

  • Linux（ubuntu）上安装RDP Server（Xrdp）使用的注意事项

    ubuntu上的基本安装方法 1 apt get install xrdp 基本上就已经安装完成了 但是此时连接会出现异常 类似黑屏的情况 原因 1 Xrdp不支持unity 3D的图形 解决方法 1 使用xfce或者gnome 2d等 如

  • C#小知识

    项目编译后复制文件到生成目录 方法1 对于单个文件 可以点击属性 输出目录里选择始终复制 方法2 把项目中的ServerScripts复制到输出目录 在项目设置中 生成事件里添加批处理 xcopy ProjectDir ServerScri

  • anaconda用法

    查看已经安装的包 pip list 或者 conda list 安装和更新 pip install requests pip install requests upgrade 或者 conda install requests conda

随机推荐

  • LINUX权限-bash: ./startup.sh: Permission denied

    LINUX权限 bash startup sh Permission denied 执行 startup sh 或者 shutdown sh的时候 报 Permission denied 需要用命令 chmod 修改一下bin目录下的 sh

  • spring boot配置双Kafka方法

    第一步 application yml的配置 server port 8080 spring application name demo kafka one bootstrap servers xxx xxx xxx xxx consume

  • android动态毛玻璃,Android模糊处理简单实现毛玻璃效果

    自从iOS系统引入了Blur效果 也就是所谓的毛玻璃 模糊化效果 磨砂效果 各大系统就开始竞相模仿 这是怎样的一个效果呢 我们先来看一下 如下面的图片 实现效果大家都知道了 如何在Android中实现呢 说白了就是对图片进行模糊化处理 小编

  • Vue项目生成二维码

    场景 民主测评 闭卷测试 Vue项目生成二维码 使用手机浏览器扫码录入答题 一 创建vue项目 样式布局 接口联调 npm run build 打包成dist 文件 让后台发送到服务器中 页面地址就获取到了 二 前引入vue qr 二维码地

  • openwrt 编译笔记

    错误一 Creating filesystem with parameters Size 50331648 Block size 4096 Blocks per group 32768 Inodes per group 6000 Inode

  • 基于OpenCV-Python实现的人脸识别

    在初步学习了数字图像处理的相关知识并在Matlab进行了初步的模拟后 我将学习的中重点转向了Python环境下的OpenCV库的学习 以此博客记录一下学习的进程 本文章代码主要参考OpenCV库源代码 刘波译的 OpenCV3计算机视觉Py

  • Apache Tomcat

    简介 简而言之 Tomcat是一个免费的开放源代码的Web应用服务器 属于轻量级应用服务器 Apache Tomcat Tomcat是Apache 软件基金会 Apache Software Foundation 的Jakarta 项目中的

  • 邻接矩阵广度优先遍历算法 连通图采用邻接表深度优先遍历的非递归过程 图G中距离顶点v的最短路径长度最大迪杰斯特拉

    1 采用邻接矩阵存储图的广度优先遍历算法的实现 参考教材算法6 5选作 2 一个连通图采用邻接表作为存储结构 设计一个算法 实现从顶点v出发的深度优先遍历的非递归过程 3 设计一个算法 求图G中距离顶点v的最短路径长度最大的一个顶点 设v可

  • 函数调用之回调函数

    重新回到CSDN 工作以来写第一个博客 不码代码 不追求高大上的专业术语 只求通俗的理解 以前听过回调函数 也研究过 但由于没有在实际中用过 所以也没太懂 每次一听到回调函数这个词 感觉很高大上 最近在工作上遇到了 而且被公司前辈广而用之

  • Pickle包的使用

    想要将Python程序运行中得到的字符串 列表 字典等数据 长久的保存下来 而不是简单的放入内存中关机断电就丢失数据 Pickle模块就是专门用来完成此功能的模块 它可以将对象转换为一种可以传输或存储的格式 它实现了基本的数据序列和反序列化

  • 如何保证token的安全

    接口的安全性主要围绕token timestamp和sign三个机制展开设计 保证接口的数据不会被篡改和重复调用 下面具体来看 Token授权机制 用户使用用户名密码登录后服务器给客户端返回一个Token 通常是UUID 并将Token U

  • Sqli-labs之Less-29和Less-30和Less-31

    Less 29 基于错误 GET 双服务器 单引号 字符型注入 服务器 两层 架构 注 截图等来自 MySQL注入天书 Less 29 服务器端有两个部分 第一部分为 tomcat 为引擎的 jsp 型服务器 第二部分为 apache 为引

  • 传输线的物理基础（十）：特性阻抗的频率变化

    到目前为止 我们一直假设传输线的特性阻抗随频率保持不变 正如我们所见 从传输线前端看 输入阻抗与频率密切相关 毕竟 在低频时 远端开路的传输线的输入阻抗看起来像一个电容器 阻抗开始很高 然后下降得很低 特性阻抗是否随频率变化 在本节中 我们

  • 【Linux入门】Linux编译器gcc/g++基础

    目录 1 背景知识 2 gcc g 的用法 3 指令补充 3 1 ldd指令 3 2 file指令 4 Linux下的头文件 库 4 1 指令的库 4 1 1 动态库 4 1 2 静态库 4 1 3 动静态库的优缺点 5 gcc g 静态链

  • v-if 和 v-show的区别 vue面试题

    v for 指令 作用 遍历数组 并重复生成对应长度的相同标签 语法 列表渲染 v for item in 数组名 遍历下标 v for item index in items 注意点 这个指令写在哪一个元素身上 就重复生成哪一个元素 数组

  • 小程序用户开放接口调整时间-2021年4月28日24时

    官方实例demo

  • 【编译原理龙书笔记】（三）词法分析（附联系答案）（仍未完成）

    这篇博客是根据自己学习龙书的过程编写 因为博主习惯了英语环境 在强行从英语转化为中文的时候难免会有些不自然 请大家谅解 配套的练习题答案可以在 https github com Oh233 Dragon book exercise 看到 感

  • L2F：第二层转发协议－－网络大典

    第二层转发协议 L2F 是一种用来建立跨越公用结构组织 如因特网 的安全隧道 为企业家庭通路连接一个 ISP POP 的协议 这个隧道建立了一个用户与企业客户网路间的虚拟点对点连接 第二层转发协议 L2F 允许链路层协议隧道技术 使用这样的

  • 高性能计算实验——矩阵乘法基于OpenMP的实现及优化

    高性能计算实验 矩阵乘法基于OpenMP的实现及优化 1 实验目的 1 1 通过OpenMP实现通用矩阵乘法 1 2 基于OpenMP的通用矩阵乘法优化 1 3 构造基于Pthreads的并行for循环分解 分配和执行机制 2 实验过程和核

  • 《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法）

    一 实验目的 1 了解串的基本概念 2 掌握串的模式匹配算法的实现 二 实验预习 说明以下概念 1 模式匹配 串的模式匹配就是子串的定位运算 设有两个字符串 S 和 T S为主串 正文串 T为子串 模式串 在主串S中查找与模式串T相匹配的子

热门标签