有没有快速的算法来删除字符串中的重复子串？

有一个类似的字符串

"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)
   

有没有更快的方法可以解决呢？

2017 年 4 月 29 日更新

抱歉，这似乎是一个 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

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

崩溃后，我得到这样的“标签路径”。

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 问题。

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

谢谢大家。

看看正则表达式的威力：

>>> 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.