计算 Python 中每个查询的相似子串数量的程序
假设我们有两个字符串s和一组查询Q。其中Q[i]包含对(l,r)，对于s从l到r的每个子串，我们必须找到从x到y的子串s的数量是相似的。如果遵循这些规则，两个字符串s和t是相似的-
它们的长度相同
对于每对索引(i,j)，如果s[i]与s[j]相同，那么它必须满足t[i]=t[j]，同样如果s[i]与s不同[j]，那么t[i]和t[j]必须不同。
所以，如果输入像s="hjhhbcbk"Q=[(1,2),(2,4)]，那么输出将是[6,1]因为
对于第一次查询，相似的子串是“hj”、“jh”、“hb”、“bc”、“cb”和“bk”。
对于第一次查询，类似的子字符串是“jhh”
示例
让我们看看以下实现以获得更好的理解-
fp = []
def calc_fingerprint(s):
dict = {s[0]: 0}
fp = "0"
j = 1
for i in range(1, len(s)):
if s[i] not in dict:
dict[s[i]], j = j, j+1
fp += str(dict[s[i]])
return int(fp)
def solve(s, Q):
if len(s) > 10:
for i in range(0, len(s)-10):
fp.append(calc_fingerprint(s[i: i+10]))
ret = []
for i in range(len(Q)):
a, b = Q[i]
s1 = s[a-1:b]
k = 0
for i in range(len(s)-(b-a)):
if b-a > 9 and fp[a-1] != fp[i]:
continue
dict = {}
s2 = s[i:i+(b-a)+1]
for i in range(b-a+1):
if s2[i] not in dict:
if s1[i] in dict.values(): break
dict[s2[i]] = s1[i]
if dict[s2[i]] != s1[i]: break
else:
k += 1
ret.append(k)
return ret
s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))输入
"hjhhbcbk", [(1,2), (2,4)]输出结果
[6, 1]