leetcode 重复的子字符串

前要推理

以abababab为例,这里最主要的就是根据相等前后缀进行推导

     s [ 0123                          ]

如 t【 0123               】

        f   【01 23              】

后两个分别是前后缀,第一个是总的字符串,然后可以推导

//首先还是算出 next数组,作为最长前后缀相等的最大长度 ;其次,是根据。前后缀的特性

s[01]=t[01]

t[01]=f[01]

t[23]=s[23]=f[01]

s[01]=s[23]

伪  

具体详解:

步骤一:因为 这是相等的前缀和后缀,t[0] 与 k[0]相同, t[1] 与 k[1]相同,所以 s[0] 一定和 s[2]相同,s[1] 一定和 s[3]相同,即:,s[0]s[1]与s[2]s[3]相同 。

步骤二: 因为在同一个字符串位置,所以 t[2] 与 k[0]相同,t[3] 与 k[1]相同。

步骤三: 因为 这是相等的前缀和后缀,t[2] 与 k[2]相同 ,t[3]与k[3] 相同,所以,s[2]一定和s[4]相同,s[3]一定和s[5]相同,即:s[2]s[3] 与 s[4]s[5]相同。

步骤四:循环往复。

所以字符串s,s[0]s[1]与s[2]s[3]相同, s[2]s[3] 与 s[4]s[5]相同,s[4]s[5] 与 s[6]s[7] 相同。

正是因为 最长相等前后缀的规则,当一个字符串由重复子串组成的,最长相等前后缀不包含的子串就是最小重复子串。

下面的则是代码了

代码实现

class Solution {
public:
void getnext(int *next,const string &s){int j=0;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;}}
//首先还是算出 next数组,作为最长前后缀相等的最大长度 ;其次,是根据。前后缀的特性 
//s[01]=t[01]
//t[01]=f[01]
//t[23]=s[23]=f[01]
//s[01]=s[23]
//递推下去 bool repeatedSubstringPattern(string s) {int next[s.size()];getnext(next,s);if(next[s.size()-1]&&s.size()%(s.size()-next[s.size()-1])==0){//如果总长度-最长相等前后缀的长度  即空开的长度   能被size整除,就是最小重复字串return true;} return false;}
};

总结

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环。

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

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

相关文章

数据库常见理论常见面试题(总结)

一、前言 这里呢&#xff0c;博主会介绍一些平时关于数据库的理论的问题&#xff0c;比如数据库的三级模式两级映射、触发器、范式、存储过程、视图等等概念知识&#xff0c;但是像索引、事务、锁等内容&#xff0c;之前的文章就讲解过了&#xff0c;这里就不作过多的介绍了&am…

【Git教程】(七)变基与拣取 —— 变基操作的概念、适用场景及其实现方式,拣取操作的实现 ~

Git教程 变基与拣取 1️⃣ 工作原理&#xff1a;复制提交2️⃣ 避免“钻石链”3️⃣ 什么情况下会遇到冲突4️⃣ 移植分支5️⃣ 执行变基后原提交的情况6️⃣ 提交的原件与副本存在于同一版本库中所带来的问题7️⃣ 捡取&#x1f33e; 总结 通常&#xff0c; 一段提交历史中往…

HUAWEI 华为交换机 配置基于VLAN的MAC地址学习限制接入用户数量 配置示例

组网需求 如 图 2-15 所示&#xff0c;用户网络 1 通过 LSW1 与 Switch 相连&#xff0c; Switch 的接口为 GE0/0/1 。用户网络2通过 LSW2 与 Switch 相连&#xff0c; Switch 的接口为 GE0/0/2 。 GE0/0/1 、 GE0/0/2 同属于 VLAN2。为控制接入用户数&#xff0c;对 VLAN2 进…

77. 组合(力扣LeetCode)

文章目录 77. 组合题目描述回溯算法组合问题的剪枝操作 77. 组合 题目描述 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1&#xff1a; 输入&#xff1a;n 4, k 2 输出&#xff1a; [ [2,4], [3,4],…

【重要公告】BSV区块链协会宣布将启动多项动态安全增强措施

​​发表时间&#xff1a;2024年2月16日 2024年2月16日&#xff0c;瑞士楚格 - BSV区块链协议的管理机构BSV区块链协会&#xff08;以下简称“BSV协会”&#xff09;宣布对其运营模式实施全新的安全架构&#xff0c;其中包括引入网络访问规则和数字资产找回协议&#xff0c;以及…

Matlab: Introduction to Hybrid Beamforming

文章目录 来源混合波束赋形的基本概念System Setup关键函数 来源 在matlab的命令行输入 doc hybrid beamforming 混合波束赋形的基本概念 混合波束形成简介 本例介绍了混合波束形成的基本概念&#xff0c;并说明了如何模拟这种系统。 现代无线通信系统使用空间复用来提高散…

ARM64汇编02 - 寄存器与指令基本格式

最近的文章可能会有较多修改&#xff0c;请关注博客哦 异常级别 ARMv8处理器支持4种异常等级&#xff08;Exception Level&#xff0c;EL&#xff09;。 EL0 为非特权模式&#xff0c;用于运行应用程序&#xff0c;其他资源访问受限&#xff0c;权限不够。 EL1 为特权模式&…

C++:常量表达式

C11开始constexpr作为一种声明&#xff0c;为编译器提供了在编译期间确认结果的优化建议&#xff0c;满足部分编译期特性的需求 constexpr和const区别 int b10; const int ab; //运行成功 constexpr int cb; //编译器报错&#xff0c;b的值在编译期间不能确定 const int size1…

电视盒子什么牌子好?老烧分享电视盒子品牌排行榜

多年前开始我就用电视盒子了至今已经七年&#xff0c;对各个品牌的电视盒子我都有详细深入的了解&#xff0c;看到网友们在讨论电视盒子什么牌子好&#xff0c;不知道如何挑选电视盒子的朋友们可以关注发烧友圈公认的电视盒子品牌排行榜&#xff0c;看看入围的都有哪些品牌吧。…

数据库之MVCC

1、什么是MVCC MVCC&#xff08;Multi-Version Concurrency Control&#xff09;即多版本并发控制。MVCC 是一种并发控制的方法&#xff0c;一般在数据库管理系统中&#xff0c;实现对数据库的并发访问。MVCC使得大部分支持行锁的事务引擎&#xff0c;不再单纯的使用行锁来进行…

如何让电脑待机而wifi不关的操作方法!!

1、一台电脑如果一天不关机&#xff0c;大约消耗0.3度电。 一般一台电脑的功耗约为250-400W&#xff08;台式机&#xff09;。 一台电脑每月的耗电量&#xff1a;如果是每小时300W每天10小时每月30天90KW&#xff0c;即90千瓦时的电。 这只是保守估计。 2、使用完毕后正常关闭…

小兴教你做平衡小车-stm32程序开发(串口打印)

文章目录 1 前言2 串口打印库函数版本3 串口打印寄存器版本3.1 配置时钟3.2 配置GPIO功能3.3 配置CR2寄存器3.4 配置CR1寄存器3.5 配置CR3寄存器 1 前言 我们在调试的过程中&#xff0c;都比较喜欢直观的数据&#xff0c;这时候我们可以使用芯片的串口功能&#xff0c;把数据打…

回归预测 | Matlab实现OOA-HKELM鱼鹰算法优化混合核极限学习机多变量回归预测

回归预测 | Matlab实现OOA-HKELM鱼鹰算法优化混合核极限学习机多变量回归预测 目录 回归预测 | Matlab实现OOA-HKELM鱼鹰算法优化混合核极限学习机多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现OOA-HKELM鱼鹰算法优化混合核极限学习机多变量…

智慧生活,从餐厅开始:开发智能扫码点餐系统的技术详解

本篇文章&#xff0c;小编将深入为大家讲解开发智能扫码点餐系统的技术细节&#xff0c;从系统架构到关键功能实现&#xff0c;为读者提供全面的技术指南。 一、智能扫码点餐系统概述 可实现在线浏览菜单、点餐、支付等操作&#xff0c;大大简化了点餐流程&#xff0c;提升了…

Spring Cloud Gateway官方文档学习

文章目录 推荐写在前面一、熟悉Gateway基本概念与原理1、三大概念2、工作流程 二、基本使用路由断言的两种写法 三、路由断言工厂1、After路由断言工厂2、Before路由断言工厂3、Between路由断言工厂4、Cookie路由断言工厂5、Header路由断言工厂6、Host路由断言工厂7、Method路由…

大话设计模式——4.装饰模式(Decorator Pattern)

1.定义 1&#xff09;可以在不改动原有对象代码的情况下扩展对象的功能&#xff0c;通过聚合的方式相较于继承更加灵活。 2&#xff09;UML图 2.示例 汽车有很多装饰可选&#xff0c;如座椅、音响、轮胎等都可以进行自定义组装 1&#xff09;抽象汽车对象 public interfac…

代码库管理工具Git介绍

阅读本文同时请参阅-----免费的Git图形界面工具sourceTree介绍 Git是一个分布式版本控制系统&#xff0c;它可以帮助开发者跟踪和管理代码历史。Git的命令行工具是使用Git的核心方式&#xff0c;虽然它可能看起来有些复杂&#xff0c;但是一旦掌握了基本命令&#xff0c;你…

回归预测 | Matlab实现SSA-BiLSTM-Attention麻雀算法优化双向长短期记忆神经网络融合注意力机制多变量回归预测

回归预测 | Matlab实现SSA-BiLSTM-Attention麻雀算法优化双向长短期记忆神经网络融合注意力机制多变量回归预测 目录 回归预测 | Matlab实现SSA-BiLSTM-Attention麻雀算法优化双向长短期记忆神经网络融合注意力机制多变量回归预测预测效果基本描述程序设计参考资料 预测效果 基…

Pytorch添加自定义算子之(5)-配置GPU形式的简单add自定义算子

参考:https://zhuanlan.zhihu.com/p/358778742 一、头文件 命名为:add2.h void launch_add2(float *c,const float *a,const float *b,int n);

【Unity】构建简单实用的年份选择器(简单原理示范)

在许多应用程序和游戏中&#xff0c;年份选择是一个常见的需求。无论是在日历应用程序中查看事件&#xff0c;还是在历史类游戏中选择时间段&#xff0c;年份选择器都是用户体验的重要组成部分&#xff0c;下面实现一个简易的年份选择器。 一、效果预览&#xff1a; 目录 一、…