最长重复子串

[编程题]最长重复子串

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

输出

说明

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

算法知识视频讲解

小谷围做题家

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)

bigkai

package main

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

    return 0
}

发表于 2021-08-14 10:47:44 回复(0)