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

（這是this codeforces problem的基礎）查找重複字符的最長的子字符串中的

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

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

我的意見是：

在一個非遞減串迴文是簡單地重複字符的上字符i的字符串（例如，「4444」或「11」。）
，i的最後一個實例 - i +1的第一個實例=重複字符的長度
跟蹤最大密碼長度，然後過濾掉每一個比最大密碼長度保證了輸出的密碼最大長度的

我基於這些觀察結果的解決方案是：

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)

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

感謝您的閱讀！

來源

2017-07-30 notcompletelyrational

它是失敗的B/C它會產生錯誤的答案，或B/C它需要太長時間？ –

您的問題基本上可以簡化爲查找長度大於1的給定字符串中存在的迴文總數。如果我錯了，請糾正我，如果可以，請給我一個反例。 – CodeHunter

它失敗了，因爲它產生了錯誤的答案。此外，它並不意味着長度> 1的給定字符串中的迴文，這意味着長度> =最長的迴文。例如，如果我找到一個迴文「44」，然後我找到另一個「77777」，我必須放棄「44」和任何其他較短的迴文，因爲它不再是最大長度。 **幸運的是，彼得·德里瓦斯善意地指出，問題在於將答案存儲爲整數而不是字符串！** – notcompletelyrational

你的程序將無法在：

4 
0011

它將只返回11。

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

您可以修復它。

來源

2017-07-30 08:09:45

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

輸出將是：

如果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對象提取，然後通過長度降序排序。該代碼依賴於輸入中的數字不能減少的事實，因此不需要第二個按字母順序排列的候選密碼。

來源

2017-07-30 22:47:55 mhawke

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

回答

相關問題