用 Python 编写程序，针对不同的查询查找字符串中不同子字符串的数量

pythonserver side programmingprogramming更新于 2025/12/17 11:56:17

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

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 kasai() 。这将需要 s、suff、n
lcp := 一个大小为 n 的数组并用 0 填充
inv := 一个大小为 n 的数组并用 0 填充
对于范围在 0 到 n - 1 内的 i，执行
- inv[suff [i]] := i
k := 0
对于范围在 0 到 n - 1 内的 i，执行
- 如果 inv [i] 与 n-1 相同，则
  - k := 0
  - 进行下一次迭代
- j := suff[inv [i] + 1]
- 当 i + k < n 且 j + k < n 且 s[i + k] 与 s[j + k] 相同，则
  - k := k + 1
- lcp[inv [i]] := k
- 如果 k > 0，则
  - k := k - 1
返回 lcp
从 main 方法，执行以下操作 −
res := 一个新列表
对于范围从 0 到 Q - 1 大小的 i，执行
- (left, right) := Q[i]
- sub := s 的子字符串，从索引左到右
- length := right-left + 1
- suffix := 一个对列表 (i，从索引 i 到末尾的 sub 的子字符串)，每个 i 的范围从 0 到长度 - 1
- 根据对的第二项对后缀进行排序子字符串
(suff, suffix) = 后缀中的索引和对应子字符串对
- lcp := kasai(sub, suff, length)
- count := size of suffix[0]
- 对于范围为 0 到 length-2 的 i，执行
  - count := count + size of suffix[i + 1] - lcp[i]
- 在 res 末尾插入 count
返回 res

示例

让我们看看下面的实现以便更好地理解 −


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))