通过检测模式来减少字符串

Question

给定一个字符串，我想检测重复的子串，然后将abab缩减为(ab)².

例如，ababababacdecdecdeababab 会减少到 (ab)⁴a(cde)³(ab)³。该字符串连续两次没有相同的字符。所以，aaab 是一个无效的字符串。

这是我写的Python：

def superscript(n):
    return "".join(["⁰¹²³⁴⁵⁶⁷⁸⁹"[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 标记重复子字符串的开始和结束。我还通过保留 list 来标记已处理字符的索引，以避免替换 (ab)⁴通过 (abab)² （因为后者将覆盖字典中的开始索引）。

The example string I work with is hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb which should output (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)⁴cbfb.

但是，我得到了这个输出： (高清)⁴(dcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdh)⁵(cg)⁴(ea) ²(dh)⁴(hd)²(cg)⁴

我不知道这是否是一个众所周知的问题，但我找不到任何资源。我不介意算法的时间复杂度。我哪里弄错了？

我尝试描述的算法如下所示：
首先，找到长度为 2、3、4、... 的重复子串，直到输入字符串的长度。
然后，做同样的操作，直到完全没有重复。

分步示例如下所示：

abcabcefefefghabcdabcdefefefghabcabcefefefghabcdabcdefefefgh
abcabc(ef)²ghabcdabcd(ef)²ghabcabc(ef)²ghabcdabcd(ef)²gh
(abc)³(ef)²ghabcdabcd(ef)²gh(abc)³(ef)²ghabcdabcd(ef)²gh
(abc)³(ef)²gh(abcd)²(ef)²gh(abc)³(ef)²gh(abcd)²(ef)²gh
((abc)³(ef)²gh(abcd)²(ef)²gh)²

Answer 1

您可以使用 re.sub 来匹配任何重复的两个字符，然后传递一个格式化您想要的模式的替换函数

import re

def superscript(n):
    return "".join(["⁰¹²³⁴⁵⁶⁷⁸⁹"[ord(c)-ord('0')] for c in str(n)])

s = 'hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb'

max_length = 5

result = re.sub(
    rf'(\w{{2,{max_length}}}?)(+)', # Omit the second number in the repetition to match any number of repeating chars (\w{2,}?)(+)
    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

Answer 2

当您将重复模式列表放在一起时，您的代码就会出现问题。当您合并长度为 2 的模式和长度为 3 的模式时，您使用的是彼此不兼容的模式。

hdhdhdhd = (hd)⁴ 从索引 0 开始到索引 7（包括在内）结束。
(dcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdh)⁵，这是字符串中的正确模式，从索引 7（包括在内）开始。

这意味着当您合并这两个模式时，您会得到不正确的最终结果，因为索引 7 处的字母是共享的。

这个问题源于这样一个事实，一个模式的长度是偶数，而另一个是奇数，并且它们的界限没有对齐。因此，它们甚至不会在 d 中相互覆盖，您最终会得到结果。

我认为您尝试使用以起始索引为键并使用 processed 列表的字典 d 来解决这个问题，但仍然存在一些问题。

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))) 开始的模式，因此单个字母不属于任何模式，例如 (hd)⁴(cg) 中的 c ⁴c(bf)⁴ 永远不会出现在字典中，因此您仍然会重叠在这些位置具有不同长度的图案。

通过检测模式来减少字符串

Reducing a string by detecting patterns

python

string

algorithm