首页 > 试题广场 >

重复词

[编程题]重复词

热度指数：1904 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于两个字符串B和C，我们定义BC为将C接在B的后面形成的新串。一个字符串P是串A的前缀，当且仅当存在B使得A＝PB，当然B可以为空串。若P!=A,则我们称P为A的真前缀。现在定义重复词。串Q是串A的重复词当且仅当Q是A的真前缀，且A是QQ的前缀。而A的最长重复词则是A的重复词中最长的一个，或者空串（当A没有任何重复串时）。如ababab的最长重复词是abab;abc的最长重复词是空串。

给定一个串s(由字母组成)，及它的长度n(1≤n≤100000)，请返回s的所有前缀的最长重复词的长度之和(空串长度为0)。

测试样例：

8,"babababa"

返回：24

算法知识视频讲解

Python

新鲜菜鸡🐔

Python通过
# -*- coding:utf-8 -*-
import collections
class Periods:
    def getLongest(self, n, s):
        ans = [0 for i in range(n)]
        start_c = s[0]
        start_index = []
        for i in range(1,n):
            if s[i]==start_c:
                start_index.append(i)
        for index in start_index[::-1]:
            ans[index] = index
            ans_temp = index
            temp = 1
            index+=1
            while index<n and (temp+1)*2<=(index+1) and s[index]==s[temp]:
                ans[index] = max(ans[index],ans_temp)
                index+=1
                temp+=1
        return sum(ans)

发表于 2018-06-29 11:11:45 回复(0)