代码随想录--字符串--重复的子字符串
题目
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
思路
暴力的解法, 就是一个for循环获取 子串的终止位置, 然后判断子串是否能重复构成字符串,又嵌套一个for循环,所以是O(n^2)的时间复杂度。
有的同学可以想,怎么一个for循环就可以获取子串吗? 至少得一个for获取子串起始位置,一个for获取子串结束位置吧。
其实我们只需要判断,以第一个字母为开始的子串就可以,所以一个for循环获取子串的终止位置就行了。 而且遍历的时候 都不用遍历结束,只需要遍历到中间位置,因为子串结束位置大于中间位置的话,一定不能重复组成字符串。
主要讲一讲移动匹配 和 KMP两种方法。
移动匹配
当一个字符串s:abcabc,内部由重复的子串组成,那么这个字符串的结构一定是这样的
也就是由前后相同的子串组成。
那么既然前面有相同的子串,后面有相同的子串,用 s + s,这样组成的字符串中,后面的子串做前串,前面的子串做后串,就一定还能组成一个s,如图:
当然,我们在判断 s + s 拼接的字符串里是否出现一个s的的时候,要刨除 s + s 的首字符和尾字符,这样避免在s+s中搜索出原来的s,我们要搜索的是中间拼接出来的s。
以上证明的充分性,接下来证明必要性:
如果有一个字符串s,在 s + s 拼接后, 不算首尾字符,如果能凑成s字符串,说明s 一定是重复子串组成。
如图,字符串s,图中数字为数组下标,在 s + s 拼接后, 不算首尾字符,中间凑成s字符串。
图中,因为中间拼接成了s,根据红色框 可以知道 s[4] = s[0], s[5] = s[1], s[0] = s[2], s[1] = s[3] s[2] = s[4] ,s[3] = s[5]
以上相等关系我们串联一下:
s[4] = s[0] = s[2]
s[5] = s[1] = s[3]
即:s[4],s[5] = s[0],s[1] = s[2],s[3]
说明这个字符串,是由 两个字符 s[0] 和 s[1] 重复组成的!
如图:
s[3] = s[0],s[4] = s[1] ,s[5] = s[2],s[0] = s[3],s[1] = s[4],s[2] = s[5]
以上相等关系串联:
s[3] = s[0]
s[1] = s[4]
s[2] = s[5]
s[0] s[1] s[2] = s[3] s[4] s[5]
和以上推导过程一样,最后可以推导出,这个字符串是由 s[0] ,s[1] ,s[2] 重复组成。
如果是这样的呢,如图:
s[1] = s[0],s[2] = s[1] ,s[3] = s[2],s[4] = s[3],s[5] = s[4],s[0] = s[5]
以上相等关系串联
s[0] = s[1] = s[2] = s[3] = s[4] = s[5]
最后可以推导出,这个字符串是由 s[0] 重复组成。
以上 充分和必要性都证明了,所以判断字符串s是否由重复子串组成,只要两个s拼接在一起,里面还出现一个s的话,就说明是由重复子串组成。
代码如下:
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string t = s + s;
t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
if (t.find(s) != std::string::npos) return true; // r
return false;
}
};
时间复杂度: O(n)
空间复杂度: O(1)
不过这种解法还有一个问题,就是 我们最终还是要判断 一个字符串(s + s)是否出现过 s 的过程,大家可能直接用contains,find 之类的库函数, 却忽略了实现这些函数的时间复杂度(暴力解法是m * n,一般库函数实现为 O(m + n))。
充分性证明
如果一个字符串s是由重复子串组成,那么 最长相等前后缀不包含的子串一定是字符串s的最小重复子串。
证明: 如果s 是有是有最小重复子串p组成。
即 s = n * p
那么相同前后缀可以是这样:
也可以是这样:
最长的相等前后缀,也就是这样:
如果字符串s 是有是有最小重复子串p组成,最长相等前后缀就不能更长一些? 例如这样:
如果这样的话,因为前后缀要相同,所以 p2 = p1,p3 = p2,如图:
p2 = p1,p3 = p2 即: p1 = p2 = p3
说明 p = p1 * 3。
这样p 就不是最小重复子串了,不符合我们定义的条件。
所以,如果这个字符串s是由重复子串组成,那么最长相等前后缀不包含的子串是字符串s的最小重复子串。
必要性证明
以上是充分性证明,以下是必要性证明:
如果 最长相等前后缀不包含的子串是字符串s的最小重复子串, 那么字符串s一定由重复子串组成吗?
最长相等前后缀不包含的子串已经是字符串s的最小重复子串,那么字符串s一定由重复子串组成,这个不需要证明了。
关键是要要证明:最长相等前后缀不包含的子串什么时候才是字符串s的最小重复子串呢。
情况一, 最长相等前后缀不包含的子串的长度 比 字符串s的一半的长度还大,那一定不是字符串s的重复子串
情况二,最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除,如图:
步骤一:因为 这是相等的前缀和后缀,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] 相同。
可以推出,在由重复子串组成的字符串中,最长相等前后缀不包含的子串就是最小重复子串。
即 s[0]s[1] 是最小重复子串
以上推导中,你怎么知道 s[0] 和 s[1] 就不相同呢? s[0] 为什么就不能使最小重复子串。
如果 s[0] 和 s[1] 也相同,同时 s[0]s[1]与s[2]s[3]相同,s[2]s[3] 与 s[4]s[5]相同,s[4]s[5] 与 s[6]s[7] 相同,那么这个字符串就是有一个字符构成的字符串。
那么它的最长相同前后缀,就不是上图中的前后缀,而是这样的的前后缀:
情况三,最长相等前后缀不包含的子串的长度 不被 字符串s的长度整除得情况,如图:
步骤一:因为 这是相等的前缀和后缀,t[0] 与 k[0]相同, t[1] 与 k[1]相同,t[2] 与 k[2]相同。
所以 s[0] 与 s[3]相同,s[1] 与 s[4]相同,s[2] 与s[5],即:,s[0]s[1]与s[2]s[3]相同 。
步骤二: 因为在同一个字符串位置,所以 t[3] 与 k[0]相同,t[4] 与 k[1]相同。
步骤三: 因为 这是相等的前缀和后缀,t[3] 与 k[3]相同 ,t[4]与k[5] 相同,所以,s[3]一定和s[6]相同,s[4]一定和s[7]相同,即:s[3]s[4] 与 s[6]s[7]相同。
以上推导,可以得出 s[0],s[1],s[2] 与 s[3],s[4],s[5] 相同,s[3]s[4] 与 s[6]s[7]相同。
那么 最长相等前后缀不包含的子串的长度 不被 字符串s的长度整除 ,就不是s的重复子串
充分条件:如果字符串s是由重复子串组成,那么 最长相等前后缀不包含的子串 一定是 s的最小重复子串。
必要条件:如果字符串s的最长相等前后缀不包含的子串 是 s最小重复子串,那么 s是由重复子串组成。
在必要条件,这个是 显而易见的,都已经假设 最长相等前后缀不包含的子串 是 s的最小重复子串了,那s必然是重复子串。
关键是需要证明, 字符串s的最长相等前后缀不包含的子串 什么时候才是 s最小重复子串。
同上我们证明了,当 最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除,那么不包含的子串 就是s的最小重复子串。
class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.equals(“”)) return false;
int len = s.length();// 原串加个空格(哨兵),使下标从1开始,这样j从0开始,也不用初始化了s = " " + s;char[] chars = s.toCharArray();int[] next = new int[len + 1];// 构造 next 数组过程,j从0开始(空格),i从2开始for (int i = 2, j = 0; i <= len; i++) {// 匹配不成功,j回到前一位置 next 数组所对应的值while (j > 0 && chars[i] != chars[j + 1]) j = next[j];// 匹配成功,j往后移if (chars[i] == chars[j + 1]) j++;// 更新 next 数组的值next[i] = j;}// 最后判断是否是重复的子字符串,这里 next[len] 即代表next数组末尾的值if (next[len] > 0 && len % (len - next[len]) == 0) {return true;}return false;
}
}
相关文章:

代码随想录--字符串--重复的子字符串
题目 给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。 示例 1: 输入: "abab" 输出: True 解释: 可由子字符串 "ab" 重复两次构成。示例 2: 输入: "…...

No.5 笔记 | 网络端口协议概览:互联网通信的关键节点
1. 常用端口速览表 端口范围主要用途1-1023系统或特权端口1024-49151注册端口49152-65535动态或私有端口 远程访问类(20-23) 端口服务记忆技巧安全风险21FTP"File Transfer Port"爆破、嗅探、溢出、后门22SSH"Secure Shell"爆破、…...

手机地址IP显示不对?别急,这里有解决方案
在当今的数字化生活中,手机已成为我们连接世界的重要工具。而手机的IP地址,作为我们在网络上的“身份证”,其准确性对于网络体验至关重要。然而,有时我们可能会遇到手机IP地址显示不正确的问题,这不仅会影响网络连接质…...

人工智能对未来工作影响的四种可能性
随着人工智能(AI)技术的迅速发展,其对人类工作的影响已成为讨论的热点话题。我们经常听到有关AI威胁论的观点,担心它将取代人类工作,但也有专家认为AI将成为一种辅助工具,帮助人类提升工作效率。宾夕法尼亚…...

SpringBoot+ElasticSearch7.12.1+Kibana7.12.1简单使用
案例简介 本案例是把日志数据保存到Elasticsearch的索引中,并通过Kibana图形化界面的开发工具给查询出来添加的日志数据,完成从0到1的简单使用 ElasticSearch职责用法简介 ElasticSearch用在哪 ElasticSearch在我这个案例中,不是用来缓解增…...

RESTful风格接口+Swagger生成Web API文档
RESTful风格接口Swagger生成Web API文档 文章目录 RESTful风格接口Swagger生成Web API文档1.RESTful风格接口RESTful简介RESTful详细图示常见http状态码springboot实现RESTfulRESTful springboot设计实例demo 2.Swagger生产Web API文档Swagger简介使用Swagger1.加入依赖2.配置S…...

性能测试学习2:常见的性能测试策略(基准测试/负载测试/稳定性测试/压力测试/并发测试)
一.基准测试 1)概念 狭义上讲:就是单用户测试。测试环境确定后,对业务模型中的重要业务做单独的测试,获取单用户运行时的各项性能指标。 广义上:是一种测量和评估软件性能指标的活动。可以在某个时刻通过基准测试建立…...

【C++】—— 继承(上)
【C】—— 继承(上) 1 继承的概念与定义1.1 继承的概念1.2 继承定义1.2.1 定义格式1.2.2 继承父类成员访问方式的变化 1.3 继承类模板 2 父类和子类对象赋值兼容转换3 继承中的作用域3.1 隐藏规则3.2 例题 4 子类的默认成员函数4.1 构造函数4.1.1 父类有…...
【2024保研经验帖】东南大学计算机学院夏令营
前言 背景:末211,专业计算机科学与技术,rk前5%,无科研,只有几个竞赛 东南大学计算机学院夏令营需要老师推荐,一个老师的推荐名额感觉应该挺多的,因为学硕和专硕都进了两百多人,总共…...

dz论坛可可积分商城插件价值399元
界面简洁美观大方,适合各类站点。支持多用户商城,可让商家入驻站点发布商品,亦可站长自己发布商品。支持向商家抽佣抽成功能,可设置商家在成交商品后按一定比例扣除抽成,达到网站盈利目的采用队列技术处理,…...
python的extend和append
在Python中,list的append和extend方法都是用来向列表添加元素的,但它们之间有一些关键的区别: append方法: append方法用于将一个对象添加到列表的末尾。无论添加的对象是什么类型(整数、字符串、列表等)&a…...
贪心算法相关知识
目录 基础 定义 工作原理 步骤一:分解问题 步骤二:确定贪心策略 步骤三:求解子问题 步骤四:合并结果 适用场景 活动安排问题 找零问题 哈夫曼编码 局限性 高级 与动态规划的对比 决策方式 最优性保证 时间复杂度和…...

济南比较出名的人物颜廷利:全球最具影响力的思想家起名大师
颜廷利教授是一位在思想、哲学、教育、易学、国学、心理学、命名学等多个领域具有深远影响的学者。他被誉为“世界点赞第一人”,在国内外享有极高的声誉,被认为是现代易经三大泰斗之首。山东目前比较厉害的名人颜廷利教授的学术成就和影响力横跨哲学、思…...

第100+27步 ChatGPT学习:概率校准 Temperature Scaling
基于Python 3.9版本演示 一、写在前面 最近看了一篇在Lancet子刊《eClinicalMedicine》上发表的机器学习分类的文章:《Development of a novel dementia risk prediction model in the general population: A large, longitudinal, population-based machine-learn…...
Python知识点:如何应用Python工具,使用NLTK进行语言模型构建
开篇,先说一个好消息,截止到2025年1月1日前,翻到文末找到我,赠送定制版的开题报告和任务书,先到先得!过期不候! 如何使用NLTK进行语言模型构建 在自然语言处理(NLP)中&a…...

深入浅出MySQL
深入浅出MySQL 以下内容参考自 《MySQL是怎样运行的:从根儿上理解MySQL》一书,强烈推荐 存储引擎 对于不同的表可以设置不同的存储引擎 CREATE TABLE tableName (xxxx ) ENGINE 引擎名称; # 修改 ALTER TABLE tableName ENGINE xxx; 编码格式 my…...

【WRF工具】cmip6-to-wrfinterm工具概述:生成WRF中间文件
cmip6-to-wrfinterm工具概述 cmip6-to-wrfinterm工具安装cmip6-to-wrfinterm工具使用快速启动(Quick start)情景1:MPI-ESM-1-2-HR(默认):情景2:BCMM情景3:EC-Earth3 更改使用&#x…...
大厂面试真题:阿里经典双重检测DCL对象半初始化问题
阿里面试题中提到的双重检测DCL(Double-Checked Locking)对象半初始化问题,是Java多线程编程中一个经典的问题。以下是对这一问题的详细解析: 一、双重检测锁(DCL)概述 双重检测锁是一种用于实现单例模式…...

20款奔驰CLS300升级原厂抬头显示HUD 23P智能辅助驾驶 触摸屏人机交互系统
以下是为您生成的一份关于 18 款奔驰 CLS 老款改新款的改装文案: 18 款奔驰 CLS 老款改新款:科技升级,畅享极致驾驶体验 在汽车改装的世界里,每一次的升级都是对卓越的追求。今天,让我们一同探索 18 款奔驰 CLS 老款改…...

GoogleNet原理与实战
在2014年的ImageNet图像识别挑战赛中,一个名叫GoogLeNet 的网络架构大放异彩。以前流行的网络使用小到11,大到77的卷积核。本文的一个观点是,有时使用不同大小的卷积核组合是有利的。 回到他那个图里面你会发现,这里的一个通过我们最大的池化…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...