首页 > 试题广场 >

最长重复子串

[编程题]最长重复子串

热度指数：19728 时间限制：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"

输出

说明

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

算法知识视频讲解

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)

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)

Java

破防了的猪猪很会编程

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)

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)

Java

惠灵顿靖

// 六刷
//可以将两个字符串想像成两个连续的滑动窗口，并假设这个滑动窗口最大是字符串长度的一半，
// 通过比较两个窗口的内容是否相同，不相同的时候不断从左向右平移，完了之后，还是不相同，
// 这时候就将窗口的大小调小一点，直到找到一个相同的，这个时候窗口的长度×2就是最大字符串的大小
import java.util.*;
public class Solution {
    public int solve (String a) {
        // write code here
        if (a == null || a.length() <= 1) return 0;
        char[] chars = a.toCharArray();
        int len = chars.length;
        int maxLen = chars.length / 2;
        for (int i = maxLen; i >= 1;i--){
            for (int j = 0; j < len - 2 * i;j++){
                if (check(chars, j, i)) 
                    return 2 * i;
            }
        }
        return 0;
    }
    public boolean check(char[] chars, int start, int len){
        for (int i = start;i < start + len;i++){
            if (chars[i] != chars[i +len]) 
                  return false;
        }
        return true;
    }
}

发表于 2021-10-01 21:23:53 回复(1)

Java

bloodycoder

千万不要用substring函数. 自己写一个就过了

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param a string字符串 待计算字符串
     * @return int整型
     */
    public boolean subStringCompare(String a, int before1, int before2, int strlen){
        for(int i=0;i<strlen;i++){
            if(a.charAt(before1+i) != a.charAt(before2+i))
                return false;
        }
        return true;
    }
    public int solve (String a) {
        // write code here
        int ans = 0;
        int[]chCount = new int[26];
        int[]ptr = new int[26];
        int[][]showIndex = new int[26][];
        for(int i=0;i<a.length();i++)
            chCount[a.charAt(i)-'a']++;
        for(int i=0;i<a.length();i++){
            if(ptr[a.charAt(i)-'a'] == 0){
                showIndex[a.charAt(i) - 'a'] = new int[chCount[a.charAt(i)- 'a']];
            }
            showIndex[a.charAt(i)-'a'][ptr[a.charAt(i)-'a']] = i;
            ptr[a.charAt(i)-'a']++;
        }
        for(int i=0;i<a.length();i++){
            char ch = a.charAt(i);
            for(int j=0;j<showIndex[ch-'a'].length;j++){
                int beforeIndex = showIndex[ch-'a'][j];
                int strlen = i-beforeIndex;
                if(beforeIndex>=i || strlen*2<ans)
                    break;
                if(beforeIndex+1-strlen<0)
                    continue;
                if(subStringCompare(a, beforeIndex+1, beforeIndex+1-strlen, strlen)){
                    ans = strlen*2;
                }
            }
        }
        return ans;
    }
}

发表于 2021-09-26 15:57:08 回复(0)

Java

QinGL_ZYW

public int solve (String a) {
    int n = a.length();
    int max = 0;
    for (int i = 0; i < n; i++) {
        for (int len = 1; len <= n/2; len++) {
            if(i + 2*len -1 >= n){
                break;
            }
            int l = 0;
            while(l < len){
                if(a.charAt(i+l) == a.charAt(i+len+l)){
                    l++;
                    max = Math.max(max, l);
                }else{
                    break;
                }
            }
        }
    }
    return 2*max;
}

发表于 2021-09-25 12:06:54 回复(0)

Java

花落梦里

    public int solve (String a) {
        //计算以i和j开头的字串所能到达的最长重复字串
        int n=a.length();
        for(int l=n/2;l>0;l--){//一段重复字串的长度
            Loop:for(int i=0;i+2*l<=n;i++){//第一段起始位置
                for(int j=i;j<i+l;j++){//相当于手动写了substring(i,i+l)和substring(i+l,i+2*l)
                    if(a.charAt(j)!=a.charAt(j+l))//只要这段子串中有一个字符不匹配，以i开头且长度为l的就不是重复子串
                        continue Loop;
                }
                return l*2;//先匹配的就是最长的
            }
        }
        return 0;
    }

发表于 2021-03-28 16:20:29 回复(1)