用 Python 编写程序来计算每个查询的相似子字符串的数量

pythonserver side programmingprogramming更新于 2025/12/17 9:48:17

假设我们有两个字符串 s 和一组查询 Q。其中 Q[i] 包含对 (l, r)，对于从 l 到 r 的 s 的每个子字符串，我们必须找到从 x 到 y 的相似子字符串的数量。如果两个字符串 s 和 t 遵循这些规则 −，则它们相似。

它们的长度相同
对于每对索引 (i, j)，如果 s[i] 与 s[j] 相同，则必须满足 t[i] = t[j]，同样，如果 s[i] 与 s[j] 不同，则 t[i] 和 t[j] 必须不同。

因此，如果输入为 s = "hjhhbcbk" Q = [(1,2), (2,4)]，则输出将为 [6, 1]，因为

对于第一个查询，相似的子字符串是"hj"、"jh"、"hb"、"bc"、"cb"和"bk"。
对于第一个查询，相似的子字符串是"jhh"

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

fp := a new list
定义一个函数 calc_fingerprint() 。这将采用 s
dict := 一个新的字典，并首先插入键值对 (s[0], 0)
fp := "0"
j := 1
对于范围从 1 到 s 的大小 - 1 的 i，执行
- 如果 s[i] 不在 dict 中，则
  - dict[s[i]] := j
  - j = j+1
- fp := fp + dict[s[i]] 的字符串表示形式
返回 fp 的整数形式
从 main 方法中，执行以下操作 −
如果 s 的大小 > 10，然后
- 对于范围从 0 到 s 的大小 - 10 的 i，执行
  - x := calc_fingerprint(s[从索引 i 到 i+9])
  - 在 fp 末尾插入 x
ret := 一个新列表
对于范围从 0 到 Q 的大小 - 1 的 i，执行
- (a, b) := Q[i]
- s1 := s 的子字符串，从索引 a-1 到 b-1
- k := 0
- 对于范围从 0 到 s 的大小 - (b-a) 的 i，执行
  - 如果 b-a > 9 且 fp[a-1] 与 fp[i] 不同，则
    - 进行下一次迭代
  - dict := 一个新的空映射
  - s2 := s 的子字符串，从索引 i 到 i+(b-a)
  - 对于范围为 0 到 b-a 的 i，执行
    - 如果 s2[i] 不在 dict 中，则
      - 如果 s1[i] 在 dict 的值中，则
        
        退出循环
      - dict[s2[i]] := s1[i]
    - 如果 dict[s2[i]] 与 s1[i] 不同，则
      - 退出循环
  - 否则，
    - k := k + 1
- 在 ret 末尾插入 k
返回 ret

示例

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


fp = []

def calc_fingerprint(s):
   dict = {s[0]: 0}
   fp = "0"
   j = 1
   for i in range(1, len(s)):
      if s[i] not in dict:
         dict[s[i]], j = j, j+1
      fp += str(dict[s[i]])
   return int(fp)

def solve(s, Q):
   if len(s) > 10:
      for i in range(0, len(s)-10):
         fp.append(calc_fingerprint(s[i: i+10]))

   ret = []
   for i in range(len(Q)):
      a, b = Q[i]
      s1 = s[a-1:b]
      k = 0
      for i in range(len(s)-(b-a)):
         if b-a > 9 and fp[a-1] != fp[i]:
            continue
         dict = {}
         s2 = s[i:i+(b-a)+1]
         for i in range(b-a+1):
            if s2[i] not in dict:
               if s1[i] in dict.values(): break
               dict[s2[i]] = s1[i]
            if dict[s2[i]] != s1[i]: break
         else:
            k += 1
      ret.append(k)

   return ret

s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))