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.