用于在 Python 中为不同查询查找字符串的不同子字符串数量的程序
假设我们有一个长度为n的字符串s。我们还有一个查询列表Q，其中Q[i]包含一对(l,r)。对于每个查询，我们必须在l和r之间的包含范围内计算s的不同子字符串的数量。
因此，如果输入类似于s="ppqpp"Q=[(1,1),(1,4),(1,1),(0,2)]，那么输出将是[1,8,1,5]因为
对于查询(1,1)唯一的子字符串是'p'所以输出是1
对于查询(1,4)，子串是'p'、'q'、'pq'、'qp'、'pp'、'pqp'、'qpp'和'pqpp'，所以输出是8
再次查询(1,1)唯一的子字符串是'p'所以输出是1
对于查询(0,2)，子串是'p'、'q'、'pp'、'pq'、'ppq'，所以输出是8。
示例
让我们看看以下实现以获得更好的理解-
def kasai (s, suff, n):
lcp = [0] * n
inv = [0] * n
for i in range (n):
inv [suff [i]] = i
k = 0
for i in range (n):
if inv [i] == n-1:
k = 0
continue
j = suff [inv [i] + 1]
while i + k <n and j + k <n and s [i + k] == s [j + k]:
k += 1
lcp [inv [i]] = k
if k> 0:
k -= 1
return lcp
def solve(s, Q):
res = []
for i in range (len(Q)):
left, right = Q[i]
sub = s [left: right + 1]
length = right-left + 1
suffix = [[i, sub [i:]] for i in range (length)]
suffix.sort(key = lambda x: x [1])
suff, suffix = [list (t) for t in zip (* suffix)]
lcp = kasai (sub, suff, length)
count = len (suffix [0])
for i in range (length-1):
count += len (suffix [i + 1]) - lcp [i]
res.append(count)
return res
s = "pptpp"
Q = [(1,1),(1,4),(1,1),(0,2)]
print(solve(s, Q))输入
"pptpp", [(1,1),(1,4),(1,1),(0,2)]输出结果
[1, 8, 1, 5]