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

5-4 D. DS串应用—最长重复子串

题目描述

求串的最长重复子串长度(子串不重叠)。例如:abcaefabcabc的最长重复子串是串abca,长度为4。

输入

测试次数t

t个测试串

输入样例:

3
abcaefabcabc
szu0123szu
szuabcefg

输出

对每个测试串,输出最长重复子串长度,若没有重复子串,输出-1.

输出样例:

4
3
-1

思路

代码

#include <iostream>
using namespace std;int getNextMax(string s){s += " ";int len = s.length(), i=1, j=0;int next[len+1];next[1] = 0;while(i < len){if(j == 0 || s[i-1] == s[j-1]){i++;j++;next[i] = j;}else{j = next[j];}}int maxNum=1;for(int i = 1; i <= len; i++){if(next[i] > maxNum){maxNum = next[i];}}if(maxNum == 1){return -1;}else{return maxNum-1;}
}int main()
{int t;string s;cin >> t;while(t--){cin >> s;int res = getNextMax(s);cout << res << endl;}return 0;
}

相关文章:

5-4 D. DS串应用—最长重复子串

题目描述 求串的最长重复子串长度&#xff08;子串不重叠&#xff09;。例如&#xff1a;abcaefabcabc的最长重复子串是串abca&#xff0c;长度为4。 输入 测试次数t t个测试串 输入样例&#xff1a; 3 abcaefabcabc szu0123szu szuabcefg 输出 对每个测试串&#xff0c;输出最…...

C语言实现12种排序算法

1.冒泡排序 思路&#xff1a;比较相邻的两个数字&#xff0c;如果前一个数字大&#xff0c;那么就交换两个数字&#xff0c;直到有序。 时间复杂度&#xff1a;O(n^2)&#xff0c;稳定性&#xff1a;这是一种稳定的算法。 代码实现&#xff1a; void bubble_sort(int arr[],…...

C语言应用实例——贪吃蛇

&#xff08;图片由AI生成&#xff09; 0.贪吃蛇游戏背景 贪吃蛇游戏&#xff0c;最早可以追溯到1976年的“Blockade”游戏&#xff0c;是电子游戏历史上的一个经典。在这款游戏中&#xff0c;玩家操作一个不断增长的蛇&#xff0c;目标是吃掉出现在屏幕上的食物&#xff0c…...

Mac如何设置一位数密码?

一、问题 Mac如何设置一位数密码&#xff1f; 二、解答 1、打开终端 2、清除全局账户策略 sudo pwpolicy -clearaccountpolicies 输入开机密码&#xff0c;这里是看不见的&#xff0c;输入完回车即可 3、重新设置密码 &#xff08;1&#xff09;打开设置-->用户和群组…...

运动编辑学习笔记

目录 跳舞重建&#xff1a; 深度运动重定向 Motion Preprocessing Tool anim_utils MotionBuilder 跳舞重建&#xff1a; https://github.com/Shimingyi/MotioNet 深度运动重定向 https://github.com/DeepMotionEditing/deep-motion-editin 游锋生/deep-motion-editin…...

C#小结:ScottPlot 5.0在VS2022桌面开发的应用(以winform为例)

目录 一、官网文档地址 二、在VS2022中安装Scottplot 三、拖动Scottplot 四、使用Scottplot 五、效果图 一、官网文档地址 官网地址&#xff1a;ScottPlot 5.0 食谱 本文内容来自于官网&#xff0c;选取了官网的一些比较好用的功能展示&#xff0c;如需学习更多功能&a…...

Jmeter性能测试: Jmeter 5.6.3 分布式部署

目录 一、实验 1.环境 2.jmeter 配置 slave 代理压测机 3.jmeter配置master控制器压测机 4.启动slave从节点检查 5.启动master主节点检查 6.运行jmeter 7.观察jmeter-server主从节点变化 二、问题 1.jmeter 中间请求和响应乱码 一、实验 1.环境 &#xff08;1&#…...

跟着cherno手搓游戏引擎【15】DrawCall的封装

目标&#xff1a; Application.cpp:把渲染循环里的glad代码封装成自己的类&#xff1a; #include"ytpch.h" #include "Application.h"#include"Log.h" #include "YOTO/Renderer/Renderer.h" #include"Input.h"namespace YO…...

Qt实现窗口吸附屏幕边缘 自动收缩

先看效果&#xff1a; N年前的QQ就可以吸附到屏幕边缘&#xff0c;聊天时候非常方便&#xff0c;不用点击状态栏图标即可呼出QQ界面 自己尝试做了一个糙版的屏幕吸附效果。 关键代码&#xff1a; void Widget::mouseMoveEvent(QMouseEvent *e) {int dx e->globalX() - l…...

shell脚本之免交互

目录 一、Here Document 免交互 1、交互与免交互的概念 2、 Here Document 概述 二、Here Document 应用 1、使用cat命令多行重定向 2、使用tee命令多行重定向 3、使用read命令多行重定向 4、使用wc -l统计行数 5、使用passwd命令用户修改密码 6、Here Document 变量…...

Ajax入门与使用

目录 ◆ AJAX 概念和 axios 使用 什么是 AJAX&#xff1f; 怎么发送 AJAX 请求&#xff1f; 如何使用axios axios 函数的基本结构 axios 函数的使用场景 1 没有参数的情况 2 使用params参数传参的情况 3 使用data参数来处理请求体的数据 4 上传图片等二进制的情况…...

蓝桥杯备战——11.NE555测频

1.分析原理图 我们可以看到&#xff0c;上图就是一个NE555构建的方波发生电路&#xff0c;输出方波频率1.44/2(R8Rb3)C,如果有不懂NE555内部结构&#xff0c;工作原理的&#xff0c;可以到B站学习。实在不懂仿真也行&#xff0c;比如我下面就是仿真结果&#xff1a; 然后就是下…...

代码随想录算法训练营第三十三天|509. 斐波那契数 ,● 70. 爬楼梯 , 746. 使用最小花费爬楼梯

确定dp数组&#xff08;dp table&#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 代码随想录 视频&#xff1a;从此再也不怕动态规划了&#xff0c;动态规划解题方法论大曝光 &#xff01;| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩…...

Node.js 文件系统操作指南

文章目录 Node.js 文件系统操作完全指南一、引言二、基本文件操作2.1 读取文件2.2 写入文件2.3 追加内容到文件 三、文件与目录的创建与删除3.1 创建文件3.2 创建目录3.3 删除文件3.4 删除目录 四、文件与目录的信息查询4.1 检查文件或目录是否存在4.2 获取文件信息4.3 获取目录…...

Kotlin 协程1:深入理解withContext

Kotlin 协程1&#xff1a;深入理解withContext 引言 在现代编程中&#xff0c;异步编程已经变得非常重要。在 Kotlin 中&#xff0c;协程提供了一种优雅和高效的方式来处理异步编程和并发。在这篇文章中&#xff0c;我们将深入探讨 Kotlin 协程中的一个重要函数&#xff1a;wi…...

(自用)learnOpenGL学习总结-高级OpenGL-几何着色器

在顶点着色器和片段着色器中间还有一个几何着色器。 几何着色器的输入是一个图元的一组顶点&#xff0c;在几何着色器中进行任意变换之后再给片段着色器&#xff0c;可以变成完全不一样的图元、可以生成更多的顶点。 #version 330 core layout (points) in; layout (line_str…...

坚持刷题 | 完全二叉树的节点个数

Hello&#xff0c;大家好&#xff0c;我是阿月&#xff01;坚持刷题&#xff0c;老年痴呆追不上我&#xff0c;今天刷&#xff1a;完全二叉树的节点个数 题目 222.完全二叉树的节点个数 代码实现 class TreeNode {int val;TreeNode left, right;public TreeNode(int val) …...

K8S网络

一、介绍 k8s不提供网络通信&#xff0c;提供了CNI接口(Container Network Interface&#xff0c;容器网络接口)&#xff0c;由CNI插件实现完成。 1.1 Pod通信 1.1.1 同一节点Pod通信 Pod通过虚拟Ethernet接口对&#xff08;Veth Pair&#xff09;与外部通信&#xff0c;Veth…...

【蓝桥杯51单片机入门记录】LED

目录 一、基础 &#xff08;1&#xff09;新建工程 &#xff08;2&#xff09;编写前准备 二、LED &#xff08;1&#xff09;点亮LED灯 &#xff08;2&#xff09;LED闪烁 延时函数的生成&#xff08;stc-isp中生成&#xff09; 实现 &#xff08;3&#xff09;流水灯…...

轻松使用python将PDF转换为图片(成功)

使用PyMuPDF&#xff08;fitz&#xff09;将PDF转换为图片 在处理PDF文件时&#xff0c;我们经常需要将PDF页面转换为图片格式&#xff0c;以便于在网页、文档或应用程序中显示。Python提供了多种方式来实现这一需求&#xff0c;本文将介绍如何使用PyMuPDF&#xff08;也称为f…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...