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

代码随想录--字符串--重复的子字符串

题目

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过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;
}

}

相关文章:

代码随想录--字符串--重复的子字符串

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

No.5 笔记 | 网络端口协议概览:互联网通信的关键节点

1. 常用端口速览表 端口范围主要用途1-1023系统或特权端口1024-49151注册端口49152-65535动态或私有端口 远程访问类&#xff08;20-23&#xff09; 端口服务记忆技巧安全风险21FTP"File Transfer Port"爆破、嗅探、溢出、后门22SSH"Secure Shell"爆破、…...

手机地址IP显示不对?别急,这里有解决方案

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

人工智能对未来工作影响的四种可能性

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

SpringBoot+ElasticSearch7.12.1+Kibana7.12.1简单使用

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

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&#xff09;概念 狭义上讲&#xff1a;就是单用户测试。测试环境确定后&#xff0c;对业务模型中的重要业务做单独的测试&#xff0c;获取单用户运行时的各项性能指标。 广义上&#xff1a;是一种测量和评估软件性能指标的活动。可以在某个时刻通过基准测试建立…...

【C++】—— 继承(上)

【C】—— 继承&#xff08;上&#xff09; 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保研经验帖】东南大学计算机学院夏令营

前言 背景&#xff1a;末211&#xff0c;专业计算机科学与技术&#xff0c;rk前5%&#xff0c;无科研&#xff0c;只有几个竞赛 东南大学计算机学院夏令营需要老师推荐&#xff0c;一个老师的推荐名额感觉应该挺多的&#xff0c;因为学硕和专硕都进了两百多人&#xff0c;总共…...

dz论坛可可积分商城插件价值399元

界面简洁美观大方&#xff0c;适合各类站点。支持多用户商城&#xff0c;可让商家入驻站点发布商品&#xff0c;亦可站长自己发布商品。支持向商家抽佣抽成功能&#xff0c;可设置商家在成交商品后按一定比例扣除抽成&#xff0c;达到网站盈利目的采用队列技术处理&#xff0c;…...

python的extend和append

在Python中&#xff0c;list的append和extend方法都是用来向列表添加元素的&#xff0c;但它们之间有一些关键的区别&#xff1a; append方法&#xff1a; append方法用于将一个对象添加到列表的末尾。无论添加的对象是什么类型&#xff08;整数、字符串、列表等&#xff09;&a…...

贪心算法相关知识

目录 基础 定义 工作原理 步骤一&#xff1a;分解问题 步骤二&#xff1a;确定贪心策略 步骤三&#xff1a;求解子问题 步骤四&#xff1a;合并结果 适用场景 活动安排问题 找零问题 哈夫曼编码 局限性 高级 与动态规划的对比 决策方式 最优性保证 时间复杂度和…...

济南比较出名的人物颜廷利:全球最具影响力的思想家起名大师

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

第100+27步 ChatGPT学习:概率校准 Temperature Scaling

基于Python 3.9版本演示 一、写在前面 最近看了一篇在Lancet子刊《eClinicalMedicine》上发表的机器学习分类的文章&#xff1a;《Development of a novel dementia risk prediction model in the general population: A large, longitudinal, population-based machine-learn…...

Python知识点:如何应用Python工具,使用NLTK进行语言模型构建

开篇&#xff0c;先说一个好消息&#xff0c;截止到2025年1月1日前&#xff0c;翻到文末找到我&#xff0c;赠送定制版的开题报告和任务书&#xff0c;先到先得&#xff01;过期不候&#xff01; 如何使用NLTK进行语言模型构建 在自然语言处理&#xff08;NLP&#xff09;中&a…...

深入浅出MySQL

深入浅出MySQL 以下内容参考自 《MySQL是怎样运行的&#xff1a;从根儿上理解MySQL》一书&#xff0c;强烈推荐 存储引擎 对于不同的表可以设置不同的存储引擎 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工具使用快速启动&#xff08;Quick start&#xff09;情景1&#xff1a;MPI-ESM-1-2-HR&#xff08;默认&#xff09;&#xff1a;情景2&#xff1a;BCMM情景3&#xff1a;EC-Earth3 更改使用&#x…...

大厂面试真题:阿里经典双重检测DCL对象半初始化问题

阿里面试题中提到的双重检测DCL&#xff08;Double-Checked Locking&#xff09;对象半初始化问题&#xff0c;是Java多线程编程中一个经典的问题。以下是对这一问题的详细解析&#xff1a; 一、双重检测锁&#xff08;DCL&#xff09;概述 双重检测锁是一种用于实现单例模式…...

20款奔驰CLS300升级原厂抬头显示HUD 23P智能辅助驾驶 触摸屏人机交互系统

以下是为您生成的一份关于 18 款奔驰 CLS 老款改新款的改装文案&#xff1a; 18 款奔驰 CLS 老款改新款&#xff1a;科技升级&#xff0c;畅享极致驾驶体验 在汽车改装的世界里&#xff0c;每一次的升级都是对卓越的追求。今天&#xff0c;让我们一同探索 18 款奔驰 CLS 老款改…...

GoogleNet原理与实战

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

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...