计算 Python 中每个查询的相似子串数量的程序

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

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

输入

"hjhhbcbk", [(1,2), (2,4)]

[6, 1]

以上是 计算 Python 中每个查询的相似子串数量的程序 的全部内容， 来源链接： utcz.com/z/331635.html