python - 是否有一种快速算法可以删除字符串中重复的子字符串？

Question

有一个类似的字符串

"dxabcabcyyyydxycxcxz"

我想把它合并到

"dxabcydxycxz"

其他例子:“ddxddx”->“dxdx”，“abbab”->“abab”。

规则是:

if (adjacent and same): merge

# Such as 'abc', they are same, so delete one of them
# Although 'dx' is same as 'dx', they are nonadjacent, so do not delete any of them
# If one character has been deleted, don't delete any substring, include it

我用 Python 做过，但是应用于长字符串时速度很慢。

# Original string
mystr = "dxabcabcyyyydxycxcxz"
str_len = len(mystr)
vis = [1] * str_len  # Use a list to mark which char is deleted

# Enumerate the size of substring
for i in range(1,str_len):
    # Enumerate the begin of the substring
    for j in range(0, str_len):
        offset = 2 #the size of sub-str + 1
        current_sub_str = mystr[j:j+i]
        s_begin = j+i*(offset-1)
        s_end = j+(i*offset)
        # Delete all of the same char
        while((j+(i*offset) <= str_len) and current_sub_str == mystr[s_begin:s_end]
              and 0  not in vis[s_begin:s_end] and 0  not in vis[j:j+i]):
            vis[s_begin:s_end] = [0] * (s_end - s_begin)  # If it was deleted, mark it as 0
            offset += 1
            s_begin = j + i * (offset - 1)
            s_end = j + (i * offset)

res = []
for i in range(0,str_len):
    if(vis[i]!=0): res.append(mystr[i])

print "".join(res)
   

有没有更快的方法解决？

Update April 29, 2017

抱歉，这似乎是一个 XY 问题。另一方面，也许不是。这是我为网络蜘蛛编码的内容，得到了很多像这样的“标签路径”:

ul/li/a
ul/li/div/div/div/a/span
ul/li/div/div/div/a/span 
ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a
ul/li/ul/li/a

如您所见，一些“标签路径”是相同的，所以我想折叠它们以找出是否有任何其他具有相同结构的“标签路径”。

折叠后，我得到了这样的'tag-path'。

ul/li/a
ul/li/div/div/div/a/span
ul/li/a
ul/li/ul/li/a
ul/li/a
ul/li/ul/li/a
ul/li/a
ul/li/ul/li/a

这只是我的想法，我不知道这样做是否合适。 (经过尝试，我选择了另一种方式)。

但是有一个有趣的问题，比如 ACM 问题。

因此，我将一个“标记路径”简化为一个字符并寻求帮助。因为我没有自己做一个快速的方法。实际上，这个问题有很多我不介意的极端情况，感谢大家帮助我完成它。

谢谢大家。

---

Answer 1

看看正则表达式的力量:

>>> import re

>>> re.sub(r"(.+?)\1+", r"\1", "dxabcabcyyyydxycxcxz")
'dxabcydxycxz'

>>> re.sub(r"(.+?)\1+", r"\1", "ddxddx")
'dxdx'

>>> re.sub(r"(.+?)\1+", r"\1", "abbab")
'abab'

这将查找 1 个或多个任意字符 (.+?) 的序列(作为非贪婪匹配，因此它首先尝试较短的序列)，然后是 1 次或多次重复匹配的序列 \1+，并将其全部替换为匹配的序列 \1。