給定一個字串，我想檢測重復的子字串，然后將abab減少到(ab) 2。
例如，ababababacdecdecdeababab將簡化為(ab) 4 a(cde) 3 (ab) 3。該字串沒有連續兩次具有相同的字符。所以，aaab是一個無效的字串。
這是我寫的 Python：
def superscript(n):
return "".join(["?123??????"[ord(c)-ord('0')] for c in str(n)])
signature = 'hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb'
d = {}
processed = []
for k in range(2, len(signature)):
i = 0
j = i k
while j <= len(signature):
repeat_count = 0
while signature[i:i k] == signature[j:j k]:
repeat_count = 1
j = k
if repeat_count > 0 and i not in processed:
d[i] = [i k, repeat_count 1]
for j in range(i, (i k)*repeat_count 1):
processed.append(j)
i = j
j = i k
else:
i = 1
j = i k
od = collections.OrderedDict(sorted(d.items()))
output = ''
for k,v in od.items():
print(k, v)
output = '(' signature[k:v[0]] ')' superscript(v[1])
其目的是檢測長度為 2、3、4 等的重復子串。我使用 . 標記重復子字串的開始和結束dict。我還通過保留一個串列來標記已處理字符的索引，以避免將(ab) 4替換為(abab) 2（因為后者將覆寫字典中的開始索引）。
The example string I work with is hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb which should output (hd) 4 (cg) 4 c(bf) 4 b(ae) 4 a(dh) 4 d(cg) 4 c(bf) 4 b(ae) 4 a (dh) 4 d(cg) 4 c(bf) 4 b(ae) 4 a(dh) 4 d(cg) 4 cbfb。
但是，我得到這個輸出： (hd) 4 (dcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdh) 5 (cg) 4 (ea) 2 (dh) 4 (hd) 2 (cg) 4
我不知道這是否是一個眾所周知的問題，但我找不到任何資源。我不介意演算法的時間復雜度。我在哪里做錯了？
我嘗試描述的演算法如下所示：
首先，找到長度為 2、3、4、...的重復子字串，直到輸入字串的長度。
然后，做同樣的操作，直到完全沒有重復。
分步示例如下所示：
abcabcefefefghabcdabcdefefefghabcabcefefefghabcdabcdefefefgh
abcabc(ef)2ghabcdabcd(ef)2ghabcabc(ef)2ghabcdabcd(ef)2gh
(abc)3(ef)2ghabcdabcd(ef)2gh(abc)3(ef)2ghabcdabcd(ef)2gh
(abc)3(ef)2gh(abcd)2(ef)2gh(abc)3(ef)2gh(abcd)2(ef)2gh
((abc)3(ef)2gh(abcd)2(ef)2gh)2
uj5u.com熱心網友回復：
您可以使用re.sub匹配任何重復的兩個字符，然后傳遞一個替換函式來格式化您想要的模式
import re
def superscript(n):
return "".join(["?123??????"[ord(c)-ord('0')] for c in str(n)])
s = 'hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb'
max_length = 5
result = re.sub(
rf'(\w{{2,{max_length}}}?)(\1 )', # Omit the second number in the repetition to match any number of repeating chars (\w{2,}?)(\1 )
lambda m: f'({m.group(1)}){superscript(len(m.group(0))//len(m.group(1)))}',
s
)
print(result) # (hd)?(cg)?c(bf)?b(ae)?a(dh)?d(cg)?c(bf)?b(ae)?a(dh)?d(cg)?c(bf)?b(ae)?a(dh)?d(cg)?c(bf)?b(ae)?a(dh)?d(cg)?c(bf)?b(ae)?a(dh)?d(cg)?cbfb
uj5u.com熱心網友回復：
當您將重復模式串列放在一起時，代碼中的問題就會發生。當您合并長度為 2 的模式和長度為 3 的模式時，您正在使用彼此不兼容的模式。
- hdhdhdhd = (hd) 4從索引 0 開始，到索引 7 結束（包括在內）。
- (dcgcgcgcgcbfbfbfbfbaeaeaeaeaaddhdhdhdh) 5是字串中的正確模式，從索引 7（包括）開始。
這意味著當您合并這兩個模式時，您會得到一個不正確的最終結果，因為索引 7 處的字母是共享的。
這個問題源于這樣一個事實，即一個模式的長度是偶數，而另一個是奇數，并且它們的限制沒有對齊。因此，它們甚至不會相互覆寫，d而您最終會得到結果。
我認為您嘗試使用d以起始索引為鍵并使用processed串列的字典來解決此問題，但仍然存在一些問題。
for j in range(i, (i k)*repeat_count 1):應該是for l in range(i, j)，否則您將跳過模式 (j) 的最后一個索引。另外，我將回圈索引更改為l因為j已使用。這解決了我上面描述的問題。- 即使解決了這個問題，仍然存在問題。您檢查從長度 2 (
for k in range(2, len(signature))) 開始的模式，因此不屬于任何模式的單個字母，例如cin (hd) 4 (cg) 4 c (bf) 4永遠不會出現在字典中，因此您仍然會有重疊在這些位置具有不同長度的圖案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478426.html