最长重复子串

[编程题]最长重复子串

热度指数：19306 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

定义重复字符串是由两个相同的字符串首尾拼接而成。例如："abcabc" 是一个长度为 6 的重复字符串，因为它由两个 "abc" 串拼接而成；"abcba" 不是重复字符串，因为它不能由两个相同的字符串拼接而成。

给定一个字符串，请返回其最长重复子串的长度。

若不存在任何重复字符子串，则返回 0。

本题中子串的定义是字符串中一段连续的区间。

数据范围：字符串长度不大于 $10^3$ ，保证字符串一定由小写字母构成。

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n^2)$

示例1

输入

"ababc"

输出

说明

abab为最长的重复字符子串，长度为4

示例2

输入

"abcab"

输出

说明

该字符串没有重复字符子串

算法知识视频讲解

changed.

发表于 2021-07-26 20:17:41

题意整理：本题题意较为简单，实际上就是在给定字符串中找到是否存在一个子串，该子串能够表示为一个字符串的重复拼接。也既从字符串 a 中，找到字符串 s， s能够表示为的形式（其中竖线只是表示分割）。例如字符串 fabcabcd 中，存在子串 abcabc，能够表示为，此处 s = abca 展开全文

LifelongCode

发表于 2021-02-03 22:15:08

可以将两个字符串想像成两个连续的滑动窗口，并假设这个滑动窗口最大是字符串长度的一半，通过比较两个窗口的内容是否相同，不相同的时候不断从左向右平移，完了之后，还是不相同，这时候就将窗口的大小调小一点，直到找到一个相同的，这个时候窗口的长度×2就是最大字符串的大小 public int solv 展开全文

ROCK丶丶

发表于 2021-08-31 14:20:57

货拉拉考过利用双指针 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param a string字符串待计算字符串展开全文

Front-endCoder

发表于 2021-01-05 11:41:11

二分思想 function solve( a ) { // write code here // 二分思想，如果存在重复子串m的话 2 * m < = a.length // 逐步递减 m 直到0 let maxLen = Math.floor(a.lengt 展开全文

空中转体一周半

发表于 2022-05-23 22:38:56

既然题目要求时间复杂度为O(n^2),那么直接套用双重循环：外层循环i为假定起始重复子串的初始位置，内层循环的j为假定重复子串的结束位置。注意，如果j-i为奇数，那么不可能是重复子串，因此，每次把j的下标增加2。由于我们是假定从i到j的子串为重复子串，因此我们需要去验证，验证很简单，就是从中间截断，展开全文