KMP-重复子字符串
Problem: 459. 重复的子字符串
文章目录
- 题目
- 思路
- 复杂度
- Code
题目
给定一个字符串str1, 判断其是否由重复的子串构成。
例子1:输入 str1=‘ababab’ ;输出 true
例子2:输入 str1=‘ababac’ ;输出 false
思路
重复子字符串组成的字符串,其肯定存在一个后缀和前缀是一样的,并且这个后缀其由后缀前面的字符子串组成。所以可以用前缀数组,先找到每个位置的最长相等前缀后缀,若最后一个字符的最长相等前缀后缀值不为零且最长后缀前的字符串长度被原字符串长度整除,那代表该最长后缀就是由前面的字符子串组成,即原字符串也由前面的字符子串组成。
复杂度
时间复杂度:
O ( n ) O(n) O(n)
空间复杂度:
O ( n ) O(n) O(n)
Code
class Solution:def repeatedSubstringPattern(self, s: str) -> bool:def get_next(str1):n = len(str1)pres = [-1] * (n +1)for i in range(n):t = pres[i]while str1[i] != str1[t] and t!=-1:t = pres[t]pres[i+1] = t + 1 return pres[1:]pres = get_next(s)if pres[-1] and len(s) % (len(s)-pres[-1])==0:return Truereturn False
相关文章:
KMP-重复子字符串
Problem: 459. 重复的子字符串 文章目录 题目思路复杂度Code 题目 给定一个字符串str1, 判断其是否由重复的子串构成。 例子1:输入 str1‘ababab’ ;输出 true 例子2:输入 str1‘ababac’ ;输出 false 思路 重复子字符串组成的字…...
如何使用Markdown生成目录索引
一、Markdown生成目录索引怎么折叠 在Markdown中,可以使用[TOC]语法生成目录索引。 如果想要折叠目录,则需要使用一些插件,如Tocbot、jquery-tocify等。 例如,在使用Tocbot时,可以在Markdown文档中加入以下代码&…...
R语言【taxa】——as_taxon():转换为 taxon 对象
Package taxa version 0.4.2 Description 将其他对象转换为 taxon 向量。taxon 构造器可能将 基础向量转换为 taxon 向量。 Usage as_taxon(x, ...) Arguments 参数【x】:要转换为 taxon 向量的对象。 参数【...】:其余参数。 Examples x <- taxo…...
Android状态栏布局隐藏的方法
1.问题如下,安卓布局很不协调 2.先将ActionBar设置为NoActionBar 先打开styles.xml 3.使用工具类 package com.afison.newfault.utils;import android.annotation.TargetApi; import android.app.Activity; import android.content.Context; import android.graph…...
idea创建公用依赖包项目
创建parent项目 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/…...
设计模式之装饰器模式
面向对象设计原则 接口隔离原则:面向对象设计之接口隔离原则-CSDN博客 设计模式 工厂模式 : 设计模式之工厂模式-CSDN博客 迭代器模式:设计模式之迭代器模式-CSDN博客 适配器模式:设计模式之适配器模式-CSDN博客 过滤器模式&#…...
【Java万花筒】缓存与存储:Java应用中的数据处理利器
激发性能之源:深度剖析Java开发中的五大数据缓存与存储方案 前言 在现代软件开发中,高效地处理和存储数据是至关重要的任务。本文将介绍一系列在Java应用中广泛使用的数据缓存与存储库,涵盖了Ehcache、Redisson、Apache Cassandra、Hazelca…...
解决nodejs报错内存泄漏问题,项目无法运行
解决方法一 一、使用 increase-memory-limit npm install increase-memory-limit //本项目中使用// 或 npm install -g increase-memory-limit //全局安装二、安装 npm install --save cross-env 配置package.json文件 LINMIT大小 81928g "scripts": {"f…...
计算机网络-物理层基本概念(接口特性 相关概念)
文章目录 总览物理层接口特性星火模型给出的相关概念解释(仅供参考) 总览 求极限传输速率:奈氏准则,香农定理(背景环境不一样) 编码:数据变成数字信号 调制:数字信号变成模拟信号 信…...
从规则到神经网络:机器翻译技术的演化之路
文章目录 从规则到神经网络:机器翻译技术的演化之路一、概述1. 机器翻译的历史与发展2. 神经机器翻译的兴起3. 技术对现代社会的影响 二、机器翻译的核心技术1. 规则基础的机器翻译(Rule-Based Machine Translation, RBMT)2. 统计机器翻译&am…...
python 面经
关于自身特点 1. 介绍下自己,讲一下在公司做的项目 2. 说一下熟悉的框架,大致讲下其特点 python 基础 1.可变与不可变类型区别 2.请解释join函数 3.请解释*args和**kwargs的含义,为什么使用* args,** kwargs? 4.解释…...
Ubuntu (Linux) 下创建软链接(即符号链接,相当于windows下的快捷方式)方法
Ubuntu (Linux) 下创建软链接(即符号链接,相当于windows下的快捷方式)方法 使用创建软链接的命令 #命令格式如下。注意:请使用绝对路径,否则链接可能失效 ln -s <源文件或目录的绝对路径> <符号链接文件&am…...
LeetCode.2765. 最长交替子数组
题目 2765. 最长交替子数组 分析 为了得到数组 nums 中的最长交替子数组的长度,需要分别计算以每个下标结尾的最长交替子数组的长度。为了方便处理,计算过程中需要考虑长度等于 1 的最长交替子数组,再返回结果时判断最长交替子数组的长度…...
Springboot日志框架logback与log4j2
目录 Springboot日志使用 Logback日志 日志格式 自定义日志格式 日志文件输出 Springboot启用log4j2日志框架 Springboot日志使用 Springboot底层是使用slf4jlogback的方式进行日志记录 Logback日志 trace:级别最低 debug:调试级别的,…...
浪花 - 用户信息展示+更新
1. 用户登录获取登录凭证 已登录的用户才能获取个人信息发送 Aixos 请求登录 const user ref();onMounted(async () > {const res await myAxios.get(/user/current);if (res.code 0) {console.log("获取用户信息成功");user.value res.data;} else {consol…...
xxe漏洞之scms靶场漏洞
xxe-scms 代码审核 (1)全局搜索simplexml_load_string simplexml_load_string--将XML字符串解释为对象 (2)查看源代码 ID1 $GLOBALS[HTTP_RAW_POST_DATA]就相当于file_get_contents("php://input"); 因此这里就存…...
Unity3d C#实现三维场景中图标根据相机距离动态缩放功能
前言 如题的需求,其实可以通过使用UI替代场景中的图标来实现,不过这样UI的处理稍微麻烦,而且需要在图标上添加粒子特效使用SpriteRender更方便快捷。这里就根据相机离图标的位置来计算图标的缩放大小即可。这样基本保持了图标的大小…...
Linux网络编程(二-套接字)
目录 一、背景知识 1.1 端口号 1.2 网络字节序 1.3 地址转换函数 二、Socket简介 三、套接字相关的函数 3.1 socket() 3.2 bind() 3.3 connect() 3.4 listen() 3.5 accept() 3.6 read()/recv()/recvfrom() 3.7 send()/sendto() 3.8 close() 四、UPD客服/服务端实…...
【DeepLearning-1】 注意力机制(Attention Mechanism)
1.1注意力机制的基本原理: 计算注意力权重: 注意力权重是通过计算输入数据中各个部分之间的相关性来得到的。这些权重表示在给定上下文下,数据的某个部分相对于其他部分的重要性。 加权求和: 使用这些注意力权重对输入数据进行加权…...
c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)
文章目录 1. 415. 字符串相加题目详情代码1思路1代码2思路2 2. 125. 验证回文串题目详情代码1(按照要求修改后放到新string里)思路1代码2(利用双指针/索引)思路2 3. 541. 反转字符串 II题目详情代码1思路1 4. 557. 反转字符串中的单词 III题目详情代码1&…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?
在现代前端开发中,Utility-First (功能优先) CSS 框架已经成为主流。其中,Tailwind CSS 无疑是市场的领导者和标杆。然而,一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...
接口 RESTful 中的超媒体:REST 架构的灵魂驱动
在 RESTful 架构中,** 超媒体(Hypermedia)** 是一个核心概念,它体现了 REST 的 “表述性状态转移(Representational State Transfer)” 的本质,也是区分 “真 RESTful API” 与 “伪 RESTful AP…...
uniapp获取当前位置和经纬度信息
1.1. 获取当前位置和经纬度信息(需要配置高的SDK) 调用uni-app官方API中的uni.chooseLocation(),即打开地图选择位置。 <button click"getAddress">获取定位</button> const getAddress () > {uni.chooseLocatio…...
【自然语言处理】大模型时代的数据标注(主动学习)
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构D 实验设计E 个人总结 A 论文出处 论文题目:FreeAL: Towards Human-Free Active Learning in the Era of Large Language Models发表情况:2023-EMNLP作者单位:浙江大…...
【免杀】C2免杀技术(十五)shellcode混淆uuid/ipv6/mac
针对 shellcode 混淆(Shellcode Obfuscation) 的实战手段还有很多,如下表所示: 类型举例目的编码 / 加密XOR、AES、RC4、Base64、Poly1305、UUID、IP/MAC改变字节特征,避开静态签名或 YARA结构伪装PE Stub、GIF/PNG 嵌入、RTF OLE、UUID、IP/MAC看起来像合法文件/数据,弱…...
Linux知识回顾总结----进程状态
本章将会介绍进程的一些概念:冯诺伊曼体系结构、进程是什么,怎么用、怎么表现得、进程空间地址、物理地址、虚拟地址、为什么存在进程空间地址、如何感性得去理解进程空间地址、环境变量是如何使用的。 目录 1. 冯诺伊曼体系结构 1.1 是什么 1.2 结论 …...
