首页 > 试题广场 >

最长重复子串

[编程题]最长重复子串
  • 热度指数:18585 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
定义重复字符串是由两个相同的字符串首尾拼接而成。例如:"abcabc" 是一个长度为 6 的重复字符串,因为它由两个 "abc" 串拼接而成;"abcba" 不是重复字符串,因为它不能由两个相同的字符串拼接而成。

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

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

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

数据范围:字符串长度不大于 10^3,保证字符串一定由小写字母构成。
进阶:空间复杂度 ,时间复杂度
示例1

输入

"ababc"

输出

4

说明

abab为最长的重复字符子串,长度为4     
示例2

输入

"abcab"

输出

0

说明

该字符串没有重复字符子串     
# @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)
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)
打扰了
发表于 2021-01-29 16:12:48 回复(1)
这个题如果输入‘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)
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)
<p>可以将两个字符串想像成两个连续的滑动窗口,并假设这个滑动窗口最大是字符串长度的一半,通过比较两个窗口的内容是否相同,不相同的时候不断从左向右平移,完了之后,还是不相同,这时候就将窗口的大小调小一点,直到找到一个相同的,这个时候窗口的长度×2就是最大字符串的大小。</p>
发表于 2020-11-12 07:41:21 回复(0)
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)
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)
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)
为啥你们都搞这么复杂呀,直接两个游标就可以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)
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)
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)
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)
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)
class Solution:
    def solve(self , a: str) -> int:
        # write code here
        size=len(a)//2
        max_len=0
        while size>0:
            for i in range(len(a)-2*size+1):
                if a[i:i+size]==a[i+size:i+2*size]:
                    max_len=max(max_len,2*size)
                    break
            size-=1
        return max_len

发表于 2022-01-23 07:19:23 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param a string字符串 待计算字符串
     * @return int整型
     */
    public int solve (String a) {
        // write code here
        int cr=0;//centerRight
        int max=0;
        int len=a.length();//中心字母的取值范围
        boolean flag = false;
        for (cr = 1; cr < len; cr++) {
            if(cr<len-cr){
                //前面短
                for (int i = 0; i < cr; i++) {
                    flag = a.substring(i, cr).equals(a.substring(cr, cr+cr-i));
                    if(flag){
                        max = max>cr-i ? max:cr-i;
                        break;
                    }
                }
            }else{
                //后面短
                for (int i = len ; i > cr; i--) {
                    flag = a.substring(cr, i).equals(a.substring(cr+cr-i, cr));
                    if(flag){
                        max = max>i-cr?max:i-cr;
                        break;
                    }
                }
            }
        }
        return max*2;
    }
}
移动对称中心来确定最大长度
发表于 2021-12-26 01:24:21 回复(0)