Python程序：查找字符串不同子字符串的数量（针对多个查询）

假设我们有一个长度为n的字符串s。我们还有一个查询列表Q，其中Q[i]包含一对(l, r)。对于每个查询，我们必须计算s在l和r（包含）之间的范围内不同子字符串的数量。

因此，如果输入类似于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'，所以输出为5。

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

  • 定义一个函数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
  • 从主方法中，执行以下操作：
  • res：一个新的列表
  • 对于范围0到Q大小-1的i，执行以下操作：
    • (left, right) := Q[i]
    • sub：从索引left到right的s的子字符串
    • length := right-left + 1
    • suffix：一个包含(i, 从索引i到末尾的sub的子字符串)对的列表，对于范围0到length - 1的每个i
    • 基于对中子字符串的第二个元素对suffix进行排序
  • (suff, suffix) = 从suffix获取索引和对应子字符串的对
    • lcp := kasai(sub, suff, length)
    • count := suffix[0]的大小
    • 对于范围0到length-2的i，执行以下操作：
      • count := count + 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))

输入

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

输出

[1, 8, 1, 5]

更新于： 2021年10月11日

226 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告

© . All rights reserved.