每次构建一个字符串，检查它是否包含相邻的重复子字符串

Question

无效字符串示例:AAAA、AB, ABACAA,ABACABAC, ABACABAB

有效字符串示例:AB, ABC, ABA, abacababab, ABACABCACBABCABACABCACBACAB

每次向字符串中添加一个新字符时都调用这个函数。因此，像ABABC这样的字符串将永远不会被函数检查，因为一旦添加第二个B，字符串就已经无效了。

我需要绝对最快的这是在函数中检查的方法。

到目前为止，我已经想出了两个相对较慢的函数:

def is_valid(s):
if len(s) < 2:
return True
# Are last two chars the same
if s[-1] == s[len(s)-2]:
return False
# Get array of indexes where last char appears and reverse it
indexes = [m.start() for m in re.finditer(s[-1], s[:-1])]
indexes = indexes[::-1]
for index in indexes:
a = s[index+1:]
if index - len(a) + 1 < 0:
return True
b = s[index-len(a)+1 : index+1]
if a == b: 
return False
return True

和

def is_valid(s):
# Reverse string
s = s[::-1]
substring = ""
for i in range(len(s)):
substring += s[i]
if len(s) >= i+1+len(substring) and s[i+1 : i+1+len(substring)] == substring:
return False
return True

如果这里没有太多需要改进的地方，那么c++/c#或Java的性能会有明显的提高吗?

Answer 1

Main和Lorentz用O(nlogn)算法搜索串联重复是相当有效的。

这段代码的Python翻译只返回repeat的事实。

def z_function(s):
n = len(s)
z = [0]*n
l = 0
r = 0
for i in range(1, n):
if (i <= r):
z[i] = min (r-i+1, z[i-l])
while (i+z[i] < n) and (s[z[i]] == s[i+z[i]]):
z[i] += 1
if (i+z[i]-1 > r):
l = i
r = i+z[i]-1
return z
def get_z(z, i):
return z[i] if 0<=i<len(z) else 0
def find_tandems(s, shift = 0):
n =  len(s)
if (n == 1):
return False
nu = n//2
nv = n-nu
u = s[:nu]
v = s[nu:]
ru = u[::-1]
rv = v[::-1]
if find_tandems (u, shift):
return True
if find_tandems (v, shift + nu):
return True
z1 = z_function (ru)
z2 = z_function (v + '#' + u)
z3 = z_function (ru + '#' + rv)
z4 = z_function (v)
for cntr in range(n):
if (cntr < nu):
l = nu - cntr
k1 = get_z (z1, nu-cntr)
k2 = get_z (z2, nv+1+cntr)
else:
l = cntr - nu + 1
k1 = get_z (z3, nu+1 + nv-1-(cntr-nu))
k2 = get_z (z4, (cntr-nu)+1)
if (k1 + k2 >= l):
return True
return False
print(find_tandems("ABACABAC"))
print(find_tandems("ABACABADAB"))
>> True
>> False

增加大小写:

def is_valid(s):
s = s[::-1]
z = z_function(s)
for i in range(1,len(z)):
if z[i]>=i:
return False
return True

Answer 2

一种方法是使用正则表达式:

import re

def is_valid(string):
return re.search(r"(.+)1", string) is None

invalids = ["AA", "ABAA", "ABACAA", "ABACABAC", "ABACABAB"]
print("All invalids are invalid", not any(is_valid(invalid) for invalid in invalids))
valids = ["AB", "ABC", "ABA", "ABACABADAB", "ABACABCACBABCABACABCACBACAB"]
print("All valids are valid", all(is_valid(valid) for valid in valids))

All invalids are invalid True
All valids are valid True

模式"(.+)1"尝试匹配由一个或多个字符组成的组，后面跟着相同的组。

Answer 3

在构建字符串时使用Okkonen算法。当一个活动边被占用时，只要边的初始长度加倍，就会出现一个重复的相邻子串。这里有一个漂亮的视觉效果，你可以在这里进行实验。