無效字串示例： AA、 AB AA、 ABAC AA、ABACABAC、 ABAC ABAB
有效字串示例：AB、ABC、ABA、ABACABADAB、ABACABCACBABCABACABCACBACAB
每次向字串添加新字符時，我都會呼叫此函式。因此，函式永遠不會檢查像 ABABC 這樣的字串，因為一旦添加了第二個 B，該字串就已經無效了。
我需要絕對最快的方法來檢查這個函式。
到目前為止，我已經提出了 2 個相對較慢的函式：
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 中會不會有明顯的性能提升？
uj5u.com熱心網友回復：
O(nlogn)Main 和 Lorentz有一個相當有效的演算法來搜索串聯重復。
此代碼的Python 翻譯僅回傳重復的事實。
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
uj5u.com熱心網友回復：
一種方法是使用正則運算式：
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"嘗試匹配一組一個或多個字符后跟同一個組。
uj5u.com熱心網友回復：
在構建字串時使用 Okkonen 演算法。當一個活動邊被接合時，只要邊的初始長度加倍，就會出現一個重復的相鄰子串。有一個漂亮的可視化效果，您可以在此處進行試驗。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/329315.html