查找重複字符的最長的子字符串中的

Question

（這是this codeforces problem的基礎）

我儘量不要與codeforces問題的幫助，除非我真的，真的，卡住，這恰好現在是。

你的第一個任務是找到火星數據庫的密碼。爲此，您的最佳祕密特工已經發現以下事實： 密碼是給定字符串的子字符串，由一系列非遞減數字組成 密碼儘可能長 密碼總是迴文 迴文是一個向後讀取相同的字符串。賽車，鮑勃和中午是着名的例子。 鑑於這些事實，你能找到數據庫的所有可能的密碼嗎？ 輸入 第一行包含n，即輸入字符串的長度（1≤n≤105）。 下一行包含一個長度爲n的字符串。這個字符串的每個字符都是一個數字。 字符串中的數字以非遞減順序排列。 輸出 在第一行上，輸出可能的密碼數量k。 在接下來的k行中，按字母順序打印可能的密碼。

我的意見是：

1. 在一個非遞減串迴文是簡單地重複字符的上字符i的字符串（例如， 「4444」 或 「11」。）

2. ，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) 

不幸的是，這種解決方案是錯誤的，實際上並未能四號測試用例。我不明白代碼有什麼問題，所以我無法修復它。有人可以幫忙嗎？

感謝您的閱讀！

Answer 1

你的程序將無法在：

4 
0011 

它將只返回11。

的問題是，str(int('00'))的長度是從程序移除int和str電話（即節省了答案爲字符串，而不是整數）等於1

您可以修復它。

Answer 2

Peter de Rivaz似乎已經識別出您的代碼存在問題，但是，如果您有興趣以不同方式解決此問題，請考慮使用正則表達式。

import sys 
import re 

next(sys.stdin)    # length not needed in Python  
s = next(sys.stdin) 

repeats = r'(.)\1+' 
for match in re.finditer(repeats, s): 
    print(match.group()) 

模式(.)\1+將找到重複數字的所有子字符串。對於輸入

 
10 
3445556788 

輸出將是：

 
44 
555 
88 

如果re.finditer()發現不存在重複的數字那麼無論是字符串是空的，或者它是由增加的非重複的數字的序列構成。由於n必須大於0，所以排除第一種情況。對於第二種情況，輸入已按字母順序排序，因此只輸出長度和每個數字。

將其組合在一起給出了這樣的代碼：

import sys 
import re 

next(sys.stdin)     # length not needed in Python 
s = next(sys.stdin).strip() 

repeats = r'(.)\1+' 
passwords = sorted((m.group() for m in re.finditer(repeats, s)), 
        key=len, reverse=True) 

passwords = [s for s in passwords if len(s) == len(passwords[0])] 

if len(passwords) == 0: 
    passwords = list(s) 

print(len(passwords)) 
print(*passwords, sep='\n') 

注意，匹配子串從match對象提取，然後通過長度降序排序。該代碼依賴於輸入中的數字不能減少的事實，因此不需要第二個按字母順序排列的候選密碼。