最长重复子串

[编程题]最长重复子串

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

Python3

定格201904231817512

class Solution:
def solve(self, a ):
# write code here
mid=len(a)//2
for i in range(mid, -1, -1):
for j in range(len(a)-2*i):
is_same=True
for k in range(i):
if a[j+k]!=a[i+j+k]:
is_same=False
break
if is_same:
return 2*i
return 0

发表于 2021-09-06 16:45:24 回复(0)