gpt4 book ai didi

python - 查找字符串中重复字符的最长子串

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:40:36 26 4
gpt4 key购买 nike

(这是 this codeforces problem 的基础)

我尽量不寻求 codeforces 问题的帮助,除非我真的、真的、被困住了,而这恰好是现在。

Your first mission is to find the password of the Martian database. To achieve this, your best secret agents have already discovered the following facts:The password is a substring of a given string composed of a sequence of non-decreasing digitsThe password is as long as possibleThe password is always a palindromeA palindrome is a string that reads the same backwards. racecar, bob, and noon are famous examples.Given those facts, can you find all possible passwords of the database?InputThe first line contains n, the length of the input string (1 ≤ n ≤ 105).The next line contains a string of length n. Every character of this string is a digit.The digits in the string are in non-decreasing order.OutputOn the first line, print the number of possible passwords, k.On the next k lines, print the possible passwords in alphabetical order.

我的观察是:

  1. 非递减字符串中的回文只是一串重复字符(例如“4444”或“11”)

  2. 在字符 i 上,i 的最后一个实例 - i 的第一个实例 +1 = 重复字符的长度

  3. 跟踪最大密码长度,然后过滤掉比最大密码长度短的每一项,保证输出的密码是最大长度

我基于这些观察的解决方案是:

n,s = [input() for i in range(2)]#input

maxlength = 0

results = []


for i in s:
length = (s.rfind(i)-s.find(i))+1

if int(i*(length)) not in results and length>=maxlength:

results.append(int(i*(length)))

maxlength = length



#filer everything lower than the max password length out
results = [i for i in results if len(str(i))>=maxlength]


#output
print(len(results))

for y in results:
print(y)

不幸的是,这个解决方案实际上是错误的,并且在第 4 个测试用例上失败了。我不明白代码有什么问题,所以我无法修复它。有人可以帮忙吗?

感谢阅读!

最佳答案

您的程序将在以下时间失败:

4
0011

它只会返回 11

问题是 str(int('00')) 的长度等于 1。

您可以通过从程序中删除 intstr 调用来修复它(即将答案保存为字符串而不是整数)。

关于python - 查找字符串中重复字符的最长子串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45395325/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com