首页 > 试题广场 >

最长重复子串

[编程题]最长重复子串

热度指数：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"

输出

说明

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

算法知识视频讲解

Python3

牛客343459580号

# @param a string字符串 待计算字符串
# @return int整型
#
class Solution:
    def solve(self , a: str) -> int:
        # write code here
        length = len(a)//2
        flag = False
        while(not flag and length != 0):
            for i in range(0,len(a)-length):
                if(a[i:i+length] == a[i+length:i+2*length]):
                    flag = True
                    return 2*length
            length -= 1
        return 0

发表于 2022-02-15 21:21:30 回复(0)

Python3

牛客366813654号

class Solution:
def solve(self , a ):
# write code here
def cf(s):
l=len(s)
mid=l//2
if l % 2==1:
return 0
elif s[:mid]==s[mid:]:
return l
else:
return 0
max=0
lena=len(a)
for i in range(lena):
for j in range(i,lena):
if max<cf(a[i:j]):
max=cf(a[i:j])
return max

发表于 2021-10-09 14:25:34 回复(0)

牛客69143547号

打扰了

发表于 2021-01-29 16:12:48 回复(1)

牛客883262237号

这个题如果输入‘aaaaa’,那么输出不应该是5吗，为啥那些通过的代码输出是4啊。子串应该是包括本身的吧？要不然为什么‘aaaaaa’的输出又是6呢？

发表于 2021-01-29 15:50:50 回复(5)

斗志昂扬的喜牛牛

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a string字符串 待计算字符串
     * @return int整型
     */
    public int solve (String a) {
        // write code here
        int l=a.length()/2;
        for(;l>0;l--){
             Loop:for(int i=0;i+2*l<=a.length();i++){
                /*if(a.charAt(i)==a.charAt(i+l)){
                    if(a.substring(i,i+l).equals(a.substring(i+l,i+2*l))){
                        return l*2;
                    }
                }*/
                
                for(int j=i;j<i+l;j++){
                    if(a.charAt(j)!=a.charAt(j+l)){
                        continue Loop;
                    }
                }
                return l*2;
            }
        }
        return 0;
    }
}

设置窗口大小l,初始值为字符串长度的一半，逐渐减小窗口长度；

从字符串头部开始滑动窗口，直到匹配成功。

在两个子串匹配时，如果生成子串对象，发现只通过80%CASE。

后来直接挨个比较字符，虽然需要显式for循环，代码复杂了一些，但不用创建子串对象，节省了时间和空间通过100%CASE.

发表于 2020-11-13 16:05:44 回复(0)

Java

YajieC

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a string字符串 待计算字符串
     * @return int整型
     */
    public int solve (String a) {
        // write code here
        int maxLen = 0;
        for(int i = 0; i < a.length(); i++){
            for(int j = i + 2; j < a.length() + 1; j+=2){ // 求字串的时候字串长度依次加2 因为重复的一定是偶数长度
                StringBuilder sb = new StringBuilder(a.substring(i,j));
                    int halfIndex = sb.length() / 2;
                    if(sb.substring(0,halfIndex).equals(sb.substring(halfIndex,sb.length())) && sb.length() > maxLen){
                        maxLen = sb.length();
                    }
            }
        }
        return maxLen;
    }
}

发表于 2021-12-23 12:17:21 回复(0)

卷卷更健康

通过的代码很多都是错的，最基本的case "aaa" 就过不了

发表于 2021-07-01 15:33:02 回复(1)

C/C++

duerduer冲啊

class Solution {
public:
    //分字符串长度奇偶性讨论，模拟两个滑动窗口，一开始的最大长度是字符串的一半，从左往右滑动比较
    //右端窗口滑到字符串末尾后，两个窗口长度同时减一，并从字符串左端从头开始扫描
    //只要扫描过程中第一次匹配到两个窗口内的字符串相同，那么答案就是2*窗口长度
    int solve(string a) {
        if(a.size()%2==0){//字符串长度是偶数
            int l1(0),r1(a.size()/2-1);
            int l2(a.size()/2),r2(a.size()-1);
            while(l1<=r1&&l2<=r2&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
                int wlen = r1-l1;//窗口缩小1格
                l1=0,r1=l1+wlen-1,l2=r1+1,r2=l2+wlen-1;
                while(r2<a.size()&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
                    l1++,r1++;
                    l2++,r2++;
                }
                if(a.substr(l1,r1-l1+1)==a.substr(l2,r2-l2+1)) return 2*(r1-l1+1);
            }
            return 2*(r1-l1+1);
        }
        else{//字符串长度是奇数
            int l1(0),r1(a.size()/2-1);
            int l2(a.size()/2),r2(a.size()-2);
            while(l1<=r1&&l2<=r2&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
                while(r2<a.size()&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
                    l1++,r1++;
                    l2++,r2++;
                }
                if(a.substr(l1,r1-l1+1)==a.substr(l2,r2-l2+1)) return 2*(r1-l1+1);
                int wlen = r1-l1;//窗口缩小1格
                l1=0,r1=l1+wlen-1,l2=r1+1,r2=l2+wlen-1;
            }
            return 2*(r1-l1+1);
        }
        return 0;
    }
};

发表于 2021-02-11 23:30:07 回复(0)

牛客613375853号

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

发表于 2020-11-12 07:41:21 回复(0)

唐氏综合征

提供三种解法，如有雷同，仅供参考：

① 高时间复杂度，使用双指针，从左往右遍历，找到相同的字符时，就判断中间不同的部分和未来的部分是否相等，记录满足条件的最大长度，然后直接跳到右指针最后一个字符，继续寻找（最后一个例子不通过，你知道什么原因吗？）

 public int solve(String a) {
        // write code here

        int MAX_LEN = 0, left = 0;
        while (left < a.length()) {

            for (int right = left + 1; right < a.length(); right++) {

                if (a.charAt(left) == a.charAt(right)) {
                    int leftTmp = left, rightTmp = right;

                    while (rightTmp < a.length() && leftTmp <= right
                            && a.charAt(leftTmp) == a.charAt(rightTmp)) {
                        leftTmp++;
                        if (leftTmp == right) {
                            MAX_LEN = Math.max(MAX_LEN, leftTmp - left);
                            left = rightTmp;
                        }
                        rightTmp++;

                    }
                }
            }
            left++;
        }

        return MAX_LEN * 2;
    }

② 动态规划，O（n^2）复杂度，使用二维 dp[]i[j] 记录 0 ~ i 和 i+1 ~ j 的公共后缀长度，最后直接根据 dp[i][j] 是否等于间距判断是否为 j-i, 如果是，则说明重复部分是刚好可以收尾相连的：

 public int solve (String a) {
        // write code here
        int len = a.length(), maxLen = 0;
        if (len == 0 ) return 0;
 
        // dp[i][j] 表示 0 ~ i 和 i+1 ~ j 的公共后缀长度
        int[][] dp = new int[len][len];
 
        // 填充dp
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                // 如果两个字符相同，则判断 i ~ j 之间的 和 j 之后的是否完全一样
                if (a.charAt(i) == a.charAt(j)) {
                    // dp[i-1][j-1] 已经计算过了，这就是动态规划的优势
                    // i == 0  时特殊处理
                    dp[i][j] = i == 0 ? 1 : dp[i - 1][j - 1] + 1;
                    // 当 j-i 之间的间隙填满时，则是有效的，
                    if (dp[i][j] ==  j - i)  maxLen = Math.max(maxLen, j - i);
                };
            }
        }
 
        return maxLen * 2;
 
    }

③ 使用贪心算法，直接从中间值开始往后遍历，并与从0开始到中间值遍历，看是否都相同，如果都相同，且 res == i 则说明重复部分是可以首位相连的，需要注意的是，重复字符串并非一定是第一个字符开头的，因此当字符不相同时不能直接 break ，并且左边搜寻的范围是 j < a.length() - i 而不是 j < i, 这点非常重要，继续寻找，直到重复的部分能够首位相连，代码如下：

 public int solve (String a) {
        // write code here
        if (a.length() == 0) return 0;
        int mid = a.length() / 2;
        for (int i = mid; i >= 0; i--) {
            int res = 0;
            for (int j = 0; j < a.length() - i; j++) {
                if (a.charAt(j) == a.charAt(j + i)) {
                    res++;
                    if (res == i) return res * 2;
                } else res = 0;
            }
        }
        return 0;
    }

总结： DP 的解法最直观最易理解，也最容易想到

发表于 2024-07-03 10:56:47 回复(0)

Java

牛客148901号

import java.util.*;
public class Solution {
    public int solve (String a) {
        int n = a.length();
        int temp = 0;
        for (int len = n / 2; len >= 1; len--) {
            for (int startIndex = 0; startIndex < n - len; startIndex++) {
                if (a.charAt(startIndex) == a.charAt(startIndex + len)) {
                    temp++;
                } else {
                    temp = 0;
                }
                if (temp == len) {
                    return len * 2;
                }
            }
        }
        return 0;
    }
}

发表于 2024-05-19 20:58:58 回复(0)

Java

牛客839384289号

public int solve (String a) {
    // write code here
    int len=a.length() ,mid=len/2;
    while(mid>0){ // 按最大长度递减
        for(int i=0;i+mid*2<=len;i++){ // 卡mid长度的两个字符串进行比较，找到即返回
            if(a.substring(i,i+mid).equals(a.substring(i+mid,i+mid*2))){
                return mid*2;
            }
        }
        mid--;
    }
    return 0;
}

编辑于 2024-03-17 16:08:47 回复(0)

Java

梁山教父

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a string字符串 待计算字符串
     * @return int整型
     */
    public int solve (String str) {
        // write code here
        //思路：使用字符串截取来匹配
        int len=str.length();
        //直接来最大长度匹配，不匹配就依次减少长度
        int size=len-1;
        while(size>=0){
            for(int i=0;i<len-size;i++){
                //如果从截取位置开始，后面的字符串包含截取的字符串并且是相邻的就是最大的
                if(str.substring(i+size).contains(str.substring(i,i+size))&&str.substring(i+size).length()>=size&&str.substring(i+size,i+size*2).contains(str.substring(i,i+size))){
                    return size*2;
                }
            }
            size--;
        }
        return 0;
    }
}

发表于 2023-05-26 09:44:53 回复(0)

小谷围做题家

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param a string字符串 待计算字符串
 * @return int整型
*/
func solve( a string ) int {
    ans:=0
    for i:=0;i<len(a);i++{
        for j:=i+1;j<=len(a);j++{
            tmp:=a[i:j]
            if len(tmp)%2==0&&check(tmp){
                if len(tmp)>ans{
                    ans=len(tmp)
                }
            }
        }
    }
    return ans
}

func check(s string)bool{
    return s[:len(s)/2]==s[len(s)/2:]
}

发表于 2023-03-14 17:38:08 回复(0)

C++

秋月的私语

为啥你们都搞这么复杂呀，直接两个游标就可以100%通过呀，下面是代码：

   int solve(string a) {
        // write code here
        int len = a.length();
         
         int nMaxlen = 0;
        for (int i = 0; i < len; ++i)
        {
            for (int j = len; j > 0; --j)
            {
                string sub = a.substr(i, j);
                 
                if (IsDub(sub))
                {
                    if (sub.length() > nMaxlen)
                    {
                        nMaxlen = sub.length();
                    }
                }
            }
        }
         
        return nMaxlen;
    }
     
    bool IsDub(string s)
    {
        int len = s.length();
        if (len < 2 || len % 2 != 0)
        {
            return false;
        }
         
        int half = len / 2;
         
        string s1 = s.substr(0, half);
        string s2 = s.substr(half);
         
        return s1 == s2;
    }

编辑于 2023-03-08 21:20:49 回复(0)

ultima

public int solve(String a)
{
    char[] c = a.toCharArray();
    int j;
    int max = 0;
    for (int i = 0; i < c.length - 1; i++)
    {
        j = i + 1;
        while (j < c.length)
        {
            if (c[i] == c[j] && (2 * j - i) <= c.length
                && a.substring(i, j).equals(a.substring(j, 2 * j - i)))
            {
                max = Math.max(2 * (j - i), max);
            }
            j++;
        }
    }
    return max;
}

通过全部用例运行时间54ms 占用内存13308KB

发表于 2023-02-21 19:13:16 回复(0)

QNBZ

class Solution {
public:
    int solve(string a) {
        // write code here
        int length = a.size();
        int ans = 0;
        for(int i = 0; i < length ; i ++) {
            for(int j = 1; i + j < length ; j ++) {
                  string str = a.substr(i,j);
                  if(str == a.substr(i + j , str.size())) {
                      int s = str.size();
                      ans = max(ans, s);
                  } else continue;
            }
        }
        return ans * 2;
    }
};

发表于 2022-09-18 08:06:00 回复(0)

Python 3

牛客607605057号

class Solution:
def solve(self , a: str) -> int:
# write code here
n = len(a)//2
while n>0:
for i in range(len(a)-2*n+1):
if a[i:i+n] == a[i+n:i+2*n]:
return 2*n
n-=1
return 0

发表于 2022-06-16 22:10:28 回复(0)

闵小

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a string字符串 待计算字符串
# @return int整型
#
class Solution:
    def solve(self , a: str) -> int:
        # write code here
        size = int(len(a) / 2);
        while size:
            for i in range(len(a) - 2 * size + 1):
                if a[i:i+size] == a[i+size:i+2*size]:
                    return size*2
            size-=1
        return size

发表于 2022-03-18 00:30:12 回复(0)

Java

FriskKiddo

abbbb合乎题意吗，没看明白？否则的话时候可以next数组来做？

    public int solve (String a) {
        // write code here
        if (a == null || a.length() < 2) {
            return 0;
        }
        //next数组
        int[] next = getNext(a);
        int max = 0;
        for (int i = 1; i < a.length(); i += 2) {
            if ((i + 1) / 2 <= next[i]) {
                max = Math.max(max, i + 1);
            }
        }
        return max;
    }

但是不对。。。

发表于 2022-02-21 10:00:16 回复(0)

提交观点

问题信息

字符串

难度：

42条回答 349收藏 12822浏览

通过挑战的用户

查看代码

雷雷雷子

2023-03-07 20:27:03
牛客58186...

2023-03-04 13:58:00
牛客13368...

2023-02-10 16:10:03
dstone

2022-12-03 21:00:52
正在卷的伊登很讲文明

2022-10-22 16:16:23

最长重复子串

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题