用于在 Python 中为不同查询查找字符串的不同子字符串数量的程序

Z时代
2024-01-10
分类：综合

假设我们有一个长度为 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))