1140:验证子串--next.data()、KMP和find

1140:验证子串--KMP

    • 题目
  • 解析
    • next.data()
    • KMP代码
    • Find代码

题目

在这里插入图片描述

解析

对于字符串的匹配常见的KMP算法【面试常考】

KMP中需要注意的是:应该从下标1开始遍历,因为下标0前面无值,不能匹配next
固在循环外应初始next[0]=0;//易忘点

next[0]=0;//易错点
//i需从1开始遍历,因为下标0前面无值,不能匹配nextfor(int i=1;i<s.size();i++)

便于使用的find代码也在下面了

next.data()

next.data()是std::vector容器的一个成员函数,它的作用是获取底层数组的首地址

vector<int> next(10); // 创建一个有10个int的数组
int* ptr = next.data(); // 获取底层数组的首地址

KMP代码

#include <iostream>
#include <vector>
#include<set>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
#include<map>
using namespace std;void getNext(string s,int *next){int j=0;next[0]=0;
//i需从1开始遍历,因为下标0前面无值,不能匹配nextfor(int i=1;i<s.size();i++){while(j>0&&s[i]!=s[j]) j=next[j-1];if(s[i]==s[j]) j++;next[i]=j;}
}bool check(string s1,string s2){if(s2.size()==0) return true;vector<int>next(s2.size());getNext(s2,next.data());int j=0;for(int i=0;i<s1.size();i++){while(j>0&&s1[i]!=s2[j]) j=next[j-1];if(s1[i]==s2[j]) j++;if(j==s2.size()) return true;}return false;
}
int main(){string s1,s2;cin>>s1>>s2;if(check(s2,s1)){cout<<s1 << " is substring of " << s2 << endl;return 0;}if(check(s1,s2)){cout<< s2 << " is substring of " << s1 << endl;return 0;}cout<<"No substring" << endl;
return 0;
}

Find代码

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
int a[N];
int cnt;
int main()
{string s1, s2;cin >> s1 >> s2;if (s1.length() > s2.length()){if (s1.find(s2) != -1)cout << s2 << " is substring of " << s1;elsecout << "No substring";}//这里的else覆盖率长度相等的情况elseif (s2.find(s1) != -1)cout << s1 << " is substring of " << s2;elsecout << "No substring";
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/33848.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python 实现大文件的高并发下载

项目背景 基于一个 scrapy-redis 搭建的分布式系统&#xff0c;所有item都通过重写 pipeline 存储到 redis 的 list 中。这里我通过代码演示如何基于线程池 协程实现对 item 的中文件下载。 Item 结构 目的是为了下载 item 中 attachments 保存的附件内容。 {"crawl_tim…

ubuntu中用docker下载opengauss

1.安装docker sudo apt install docker.io2.拉取opengauss镜像 sudo docker pull enmotech/opengauss3.创建容器 sudo docker run --name opengauss --privilegedtrue -d -e GS_PASSWORDEnmo123 enmotech/opengauss:latest3.5.如果容器停止运行&#xff08;比如关机了&#…

从零基础到能独立设计单片机产品,一般需要经历哪些学习阶段?

相信很多人&#xff0c;内心都有“钢铁侠”的幻想&#xff0c;成为能写程序&#xff0c;能设计硬件&#xff0c;能设计结构&#xff0c;能焊接的全能型人才。 上次徐工问我&#xff0c;如果你财富自由了&#xff0c;想去做啥&#xff1f; 我说出来&#xff0c;可能大家都不信&a…

cursor中git提交记录出现 签出(已分离)

我当时在cursor中的git记录右键点击 签出(已分离) 就导致最左边的记录图标的颜色由蓝色变为了橙色 后面提交的记录都不在显示本地分支和远程分支 创建新分支&#xff1a;在您当前的分离HEAD状态下&#xff0c;创建一个新的分支来保存这些提交。 git checkout -b new-branch-nam…

软件测试之测试用例

1. 什么是测试用例 测试用例&#xff08;TestCase)是为了实施测试而向被测试的系统提供的一组集合&#xff0c;这组集合包含&#xff1a;测试环境、操作步骤、测试数据、预期结果等要素。 设计测试⽤例原则⼀&#xff1a; 测试⽤例中⼀个必需部分是对预期输出或结果进⾏定义 使…

Unity2D 井字棋

Unity版本2022.3 场景布置 其中可以通过给Board对象添加Grid Layout Group&#xff0c;然后设置每个子物体所占宽高快速排整齐。用完删掉。每个落子的方格ChessBox都是一个Button。 根据Board的宽高除以三即可。 然后隐藏按钮&#xff0c;通过设置alpha值实现。 将ChessBox的…

专题三搜索插入位置

1.题目 题目分析&#xff1a; 给一个目标值&#xff0c;然后要在排序的整数数组中&#xff0c;找到跟目标值一样的&#xff0c;如果没有就把这个值插入进去&#xff0c;然后返回插入后的下标。 2.算法原理 根据题目的时间复杂度可以知道要用二分&#xff0c;开始划分区域&…

正式进入linux 1.0

切记&#xff1a;在Linux中空格很重要 回车键也很重要&#xff0c;不要按两次回车键 ls是显示当前所有文件夹 具体解释&#xff1a; 前面的东西是用户名 后面的是设备名&#xff08;计算机名&#xff09; 这是因为linux允许不同用户在终端下进行操作&#xff0c;这么做可以…

分页查询的实现

目录 前言 一.问题描述 二.后端实现步骤 2.1配置PageHelper插件 ①导入依赖 ②在application.yml配置文件中添加相关配置 2.2编写一个入门的程序&#xff0c;体验分页过程 2.3定义一个vo&#xff0c;用来收集分页后的所有信息 2.4修改serviceImpl层的代码 2.5动态设…

16003. orin camera 相机驱动源码 imx477分析记录

文章目录 1 背景2 原理图2.1 CAM_MUX_SEL 4 lane 选通2.2 J21 和 J20 原理图3 驱动源码及设备树3.1 子设备树 tegra234-p3768-camera-rbpcv3-imx477.dtsi3.2 顶层设备树 tegra234-camera-rbpcv3-imx477.dtsi3.2.1 tegra-capture-vi 视频输入子系统节点配置.3.2.2 host1x 主机控…

无标签数据增强+高效注意力GAN:基于CARLA的夜间车辆检测精度跃升

目录 一、摘要 二、引言 三、框架 四、方法 生成合成夜间数据 昼夜图像风格转换 针对夜间图像的无标签数据增强技术 五、Coovally AI模型训练与应用平台 六、实验 数据 图像风格转换 夜间车辆检测和分类 结论 论文题目&#xff1a;ENHANCING NIGHTTIME VEHICLE D…

开源工具利器:Mermaid助力知识图谱可视化与分享

在现代 web 开发中&#xff0c;可视化工具对于展示流程、结构和数据关系至关重要。Mermaid 是一款强大的 JavaScript 工具&#xff0c;它使用基于 Markdown 的语法来呈现可定制的图表、图表和可视化。对于展示流程、结构和数据关系至关重要。通过简单的文本描述&#xff0c;你可…

C++算法学习2:二分算法精讲

一、实数二分法回顾 1.1问题背景 在1~2的范围内找到一个x&#xff0c;使得式子5x2 -9x 1 的绝对值<10-9&#xff08;即无限接近0&#xff09; 要求&#xff1a;x精确到小数点后9位。 换句话说也就是求&#xff1a;就是求方程 5x2- 9x 1 0 在1~2内的近似解 1.2怎么找到…

手写一个简易版的tomcat

Tomcat 是一个广泛使用的开源 Servlet 容器&#xff0c;用于运行 Java Web 应用程序。深入理解 Tomcat 的工作原理对于 Java 开发者来说是非常有价值的。本文将带领大家手动实现一个简易版的 Tomcat&#xff0c;通过这个过程&#xff0c;我们可以更清晰地了解 Tomcat 是如何处理…

object.assign和扩展运算法是深拷贝还是浅拷贝,两者区别

object.assign和扩展运算法是深拷贝还是浅拷贝&#xff0c;两者区别 1. 浅拷贝的本质2. Object.assign 和扩展运算符的区别‌3. 具体场景对比‌合并多个对象‌‌复制数组‌‌处理默认值‌ ‌4. 如何实现深拷贝&#xff1f;JSON.parse(JSON.stringify(obj))‌‌递归深拷贝函数第…

X-CLIP和X-FLORENCE论文解读

1.研究背景 尽管已有研究探索了如何将语言-图像模型迁移到其他下游任务&#xff08;如点云理解和密集预测&#xff09;&#xff0c;但视频识别领域的迁移和适应性研究还不够充分。例如&#xff0c;ActionCLIP提出了一种“预训练、提示和微调”的框架用于动作识别&#xff0c;但…

微信小程序刷题逻辑实现:技术揭秘与实践分享

页面展示&#xff1a; 概述 在当今数字化学习的浪潮中&#xff0c;微信小程序以其便捷性和实用性&#xff0c;成为了众多学习者刷题备考的得力工具。今天&#xff0c;我们就来深入剖析一个微信小程序刷题功能的实现逻辑&#xff0c;从代码层面揭开其神秘面纱。 小程序界面布局…

Android UI 组件系列(二):Button 进阶用法

引言 在上一篇博客中&#xff0c;我们介绍了 Button 的基本用法和常见属性&#xff0c;掌握了 Button 的基础知识。然而&#xff0c;在实际开发中&#xff0c;Button 远不止于简单的点击功能&#xff0c;它还可以支持不同的变体、丰富的自定义样式&#xff0c;以及更灵活的状态…

【云馨AI-大模型】RAGFlow功能预览:Dify接入外部知识库RAGFlow指南

介绍 Dify介绍 开源的 LLM 应用开发平台。提供从 Agent 构建到 AI workflow 编排、RAG 检索、模型管理等能力&#xff0c;轻松构建和运营生成式 AI 原生应用。比 LangChain 更易用。官网&#xff1a;https://dify.ai/zh RAGFlow介绍 RAGFlow 是一款基于深度文档理解构建的…

Redis超高并发分key实现

Redis扛并发的能力是非常强的&#xff0c;所以高并发场景下经常会使用Redis&#xff0c;但是Redis单分片的写入瓶颈在2w左右&#xff0c;读瓶颈在10w左右&#xff0c;如果在超高并发下即使是集群部署Redis&#xff0c;单分片的Redis也是有可能扛不住的&#xff0c;如下图所示&a…