当前位置: 首页 > news >正文

重复的子字符串

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 

示例 1:

输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:

输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。

方法一:枚举

class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();for (int i = 1; i * 2 <= n; ++i) {if (n % i == 0) {bool match = true;for (int j = i; j < n; ++j) {if (s[j] != s[j - i]) {match = false;break;}}if (match) {return true;}}}return false;}
};

 方法二:双指针

class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();for (int len = 1; len <= n / 2; len++) {if (n % len == 0) {bool isMatch = true;for (int i = 0; i < n; i += len) {for (int j = 0; j < len; j++) {if (s[i + j] != s[j]) {isMatch = false;break;}}if (!isMatch) {break;}}if (isMatch) {return true;}}}return false;}
};

方法三:字符串匹配

class Solution {
public:bool repeatedSubstringPattern(string s) {return (s + s).find(s, 1) != s.size();}
};

(s+s)将字符串与其自身进行拼接,目的是利用拼接后的字符串的特性来判断字符串是否由重复子串组成。 在拼接得到的新字符串上调用find成员函数查找指定子串在当前字符串在子串总出现的位置。第二个参数从索引一的位置开始查找(跳过拼接字符串开头与原字符串s起始重复的部分)。将 find  函数返回的位置与原字符串 s  的长度进行比较。如果查找结果不等于原字符串的长度,说明在拼接字符串中从索引 1  开始找到了与 s  匹配的子串,也就意味着原字符串 s  是由重复子串组成的,此时返回 true  ;否则返回 false  。

 

方法四:KMP算法

class Solution {
public:bool repeatedSubstringPattern(string s) {if(s.size()==0){return false;}int j=0;int next[s.size()];next[0]=0;for(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;}int len=s.size();if(next[len-1]!=0&&len%(len-next[len-1])==0){return true;}return false;}
};

如果s的长度为0,则返回false。定义一个变量j初始化为0。用来记录后续next的索引。定义一个整数类型的数组next,数组大小与字符串s长度相同,用于存储s的部分匹配信息。初始化next的的一个元素为0。遍历字符串s。当j大于0且当前字符s[i]与匹配字符s[j]不相等时进入循环。通过next数组回溯j的位置,目的是找到一个合适的j,使得从该位置开始能继续匹配。回溯j的位置,利用好已经计算好的next值,让j跳到合适的位置继续匹配。如果当前字母m[i]与m[j]相等,j加加。将当前位置i的最长前后缀记录到next数组中。定义一个变量冷并赋值为字符串s。如果next数组的最后一个元素不为0且字符串长度能被最小重复子串长度整除,则返回true。否则返回false。 

http://www.xdnf.cn/news/380593.html

相关文章:

  • 【ts】defineProps数组的类型声明
  • 人工智能100问☞第19问:什么是专家系统?
  • 自定义类型-结构体(二)
  • 基于ssm的超市库存商品管理系统(全套)
  • Vue.js框架的优缺点
  • 2025年PMP 学习六 -第5章 项目范围管理 (5.1,5.2,5.3)
  • ubunut20.04 安装运行lvi-sam
  • JavaSE核心知识点02面向对象编程02-05(方法)
  • 【比赛真题解析】混合可乐
  • 翻转数位题目解释和代码
  • C语言复习--动态内存管理
  • 同步、异步、并发的区别
  • Python与YOLO:自动驾驶中的实时物体检测
  • comfyui 如何优雅的从Hugging Face 下载模型,文件夹
  • 2025年特种作业操作证考试题库及答案(登高架设作业)
  • AST(抽象语法树)与 HBO(基于历史的优化)详解
  • 使用 Jackson 在 Java 中解析和生成 JSON
  • Spring事务管理实现机制
  • Windows右键管理工具:轻松添加/删除/修改右键菜单项!
  • xml与注解的区别
  • 机器学习 day01
  • 如何更改typora图片存储位置
  • 将一张100 元的钞票换成1 元、2元、5 元和10 元的零钱,每种零钞至少一张
  • CH579 CH573 CH582 CH592 蓝牙主机(Central)实例应用讲解
  • C. scanf 函数基础
  • Linux--JsonCpp
  • 【C++】内存管理
  • Lettuce 节点刷新、连接优化与 Spring 升级适配全解析:从环境约束到生产验证
  • printf调试时候正常,运行时打印不出来
  • spring响应式编程系列:异步消费数据