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

141.字符串:重复的字符串(力扣)

题目描述

代码解决

class Solution 
{
public:// 计算字符串s的next数组,用于KMP算法void getNext(int *next, const string& s){int j = 0; // j是前缀的长度next[0] = 0; // 初始化next数组,第一个字符的next值为0for (int i = 1; i < s.size(); i++) // 注意这里的i从1开始{// 如果s[i] != s[j],则向前回溯,直到找到匹配的前缀或到达字符串开始while (j > 0 && s[i] != s[j]){j = next[j - 1];}// 如果s[i] == s[j],前缀长度增加1if (s[i] == s[j]){j++;}next[i] = j; // 更新next数组}}bool repeatedSubstringPattern(string s) {if (s.size() == 0){return false;}int next[s.size()];getNext(next, s); // 计算next数组int len = s.size();int pattern_length = len - next[len - 1]; // 计算模式字符串的长度// 如果next[len - 1] != 0 且 len 能被 pattern_length 整除,则表示有重复的模式if (next[len - 1] != 0 && len % pattern_length == 0) {return true;}return false;}
};
  1. 计算Next数组

    • getNext 函数通过计算 next 数组来确定每个字符前缀的最大长度,使得这些前缀同时也是后缀。
    • 具体地,对于每一个字符 s[i],如果它不能匹配当前的前缀字符 s[j],则通过 j = next[j - 1] 回溯到前一个匹配位置,直到找到匹配的前缀或到达字符串的开始。
  2. 检查重复子串模式

    • 如果 next[len - 1] 不为0,表示字符串存在部分重复。
    • 计算模式字符串的长度 pattern_length,这个长度等于字符串的总长度减去最后一个前缀值 next[len - 1]
    • 如果字符串长度 len 可以被 pattern_length 整除,则表示字符串可以由重复的模式字符串构成。

相关文章:

  • Stable Diffusion教程
  • Midjourney绘画关键词参数汇总(二)
  • currentTarget指向监听者Target:指向触发者
  • TikTok矩阵管理系统:品牌增长的新引擎
  • Php composer 基础教程
  • 基于springboot+vue的学生考勤管理系统
  • FreeRTOS_同步互斥与通信_队列集_学习笔记
  • MySQL实战——主从异步复制搭建(一主一从)
  • 解决ModuleNotFoundError: No module named ‘open_clip‘问题
  • 三维空间坐标系变换(旋转平移)
  • python实现520表白图案
  • LLama3 | 一. 本地 Web Demo 部署
  • 手写tomcat(Ⅱ)——Socket通信+tomcat静态资源的获取
  • python手写数字识别(PaddlePaddle框架、MNIST数据集)
  • 嵌入式科普(18)Ubuntu在移动硬盘的安装和启动
  • [原]深入对比数据科学工具箱:Python和R 非结构化数据的结构化
  • 【跃迁之路】【519天】程序员高效学习方法论探索系列(实验阶段276-2018.07.09)...
  • android百种动画侧滑库、步骤视图、TextView效果、社交、搜房、K线图等源码
  • Angular Elements 及其运作原理
  • Angular6错误 Service: No provider for Renderer2
  • C语言笔记(第一章:C语言编程)
  • Django 博客开发教程 16 - 统计文章阅读量
  • eclipse(luna)创建web工程
  • ES6 学习笔记(一)let,const和解构赋值
  • express如何解决request entity too large问题
  • JavaScript/HTML5图表开发工具JavaScript Charts v3.19.6发布【附下载】
  • java中具有继承关系的类及其对象初始化顺序
  • JDK9: 集成 Jshell 和 Maven 项目.
  • js学习笔记
  • php的插入排序,通过双层for循环
  • Redux 中间件分析
  • seaborn 安装成功 + ImportError: DLL load failed: 找不到指定的模块 问题解决
  • Spring Security中异常上抛机制及对于转型处理的一些感悟
  • Spring思维导图,让Spring不再难懂(mvc篇)
  • 猴子数据域名防封接口降低小说被封的风险
  • 回顾 Swift 多平台移植进度 #2
  • 容器化应用: 在阿里云搭建多节点 Openshift 集群
  • 时间复杂度与空间复杂度分析
  • 用Visual Studio开发以太坊智能合约
  • #include<初见C语言之指针(5)>
  • #我与Java虚拟机的故事#连载08:书读百遍其义自见
  • %3cli%3e连接html页面,html+canvas实现屏幕截取
  • (C语言)逆序输出字符串
  • (附源码)ssm捐赠救助系统 毕业设计 060945
  • (介绍与使用)物联网NodeMCUESP8266(ESP-12F)连接新版onenet mqtt协议实现上传数据(温湿度)和下发指令(控制LED灯)
  • (求助)用傲游上csdn博客时标签栏和网址栏一直显示袁萌 的头像
  • (十七)devops持续集成开发——使用jenkins流水线pipeline方式发布一个微服务项目
  • (一)Thymeleaf用法——Thymeleaf简介
  • (转)mysql使用Navicat 导出和导入数据库
  • (转)Scala的“=”符号简介
  • (转)编辑寄语:因为爱心,所以美丽
  • (转)总结使用Unity 3D优化游戏运行性能的经验
  • .net 微服务 服务保护 自动重试 Polly
  • .NET/C# 检测电脑上安装的 .NET Framework 的版本
  • .Net程序猿乐Android发展---(10)框架布局FrameLayout