当前位置: 首页 > 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在移动硬盘的安装和启动
  • Android框架之Volley
  • Babel配置的不完全指南
  • CentOS7简单部署NFS
  • CSS实用技巧干货
  • ECMAScript 6 学习之路 ( 四 ) String 字符串扩展
  • JS数组方法汇总
  • leetcode讲解--894. All Possible Full Binary Trees
  • Perseus-BERT——业内性能极致优化的BERT训练方案
  • 搭建gitbook 和 访问权限认证
  • 开放才能进步!Angular和Wijmo一起走过的日子
  • 微信小程序--------语音识别(前端自己也能玩)
  • 用Python写一份独特的元宵节祝福
  • 如何通过报表单元格右键控制报表跳转到不同链接地址 ...
  • ​软考-高级-系统架构设计师教程(清华第2版)【第9章 软件可靠性基础知识(P320~344)-思维导图】​
  • (1/2) 为了理解 UWP 的启动流程,我从零开始创建了一个 UWP 程序
  • .class文件转换.java_从一个class文件深入理解Java字节码结构
  • .mat 文件的加载与创建 矩阵变图像? ∈ Matlab 使用笔记
  • .NET C# 使用GDAL读取FileGDB要素类
  • .NET HttpWebRequest、WebClient、HttpClient
  • .NET Standard 的管理策略
  • .NET 服务 ServiceController
  • .Net中间语言BeforeFieldInit
  • .one4-V-XXXXXXXX勒索病毒数据怎么处理|数据解密恢复
  • @EventListener注解使用说明
  • []T 还是 []*T, 这是一个问题
  • []利用定点式具实现:文件读取,完成不同进制之间的
  • [20170705]lsnrctl status LISTENER_SCAN1
  • [Algorithm][动态规划][两个数组的DP][正则表达式匹配][交错字符串][两个字符串的最小ASCII删除和][最长重复子数组]详细讲解
  • [AX]AX2012 AIF(四):文档服务应用实例
  • [C++]:for循环for(int num : nums)
  • [CF494C]Helping People
  • [codevs1288] 埃及分数
  • [cogs2652]秘术「天文密葬法」
  • [go] 迭代器模式
  • [GXYCTF2019]禁止套娃
  • [Hadoop in China 2011] 蒋建平:探秘基于Hadoop的华为共有云
  • [iOS开发]iOS中TabBar中间按钮凸起的实现
  • [LeetCode]—Longest Palindromic Substring 最长回文子串
  • [NISACTF 2022]easyssrf
  • [NOI2014]购票