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

假设我们有两个字符串s和查询Q的集合。其中Q [i]包含一对（l，r），对于s中从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：新列表
定义函数calc_fingerprint（）托管s
dict：新字典，并最初插入键值对（s [0]，0）
fp：“0”
j = 1
对于i在范围1到s-1的大小范围内，执行
- 如果s [i]不在dict中，则
  - dict [s [i]]：= j
  - j = j + 1
- fp：= fp + dict [s [i]]的字符串表示形式
返回fp的整数形式
从主方法中执行以下操作−
如果s的大小> 10，则
- 对于i在范围0到s-10的大小范围内，执行
  - x：= calc_fingerprint（s [从索引i到i + 9]）
  - 将x插入fp的末尾
ret：新列表
对于i在范围0到Q大小-1的大小范围内，执行
- （a，b）：= Q [i]
- s1：= s中从索引a-1到b-1的子字符串
- k = 0
- 对于i在范围0到s-（b-a）的大小内，执行
  - 如果b-a> 9且fp [a-1]与fp [i]不同，则
  - 进入下一个迭代
  - dict：=新的空映射
  - s2：= s中从索引i到i +（b-a）的子字符串
  - 对于i在范围0到b-a的范围内，执行
  - 如果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]不在dict中:
          dict [s [i]]，j = j，j + 1
      fp + = str（dict [s [i]]）
   return int（fp）

def solve（s，Q）：
   如果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））：
          如果b-a> 9 and fp [a-1]！= fp [i]：
              继续
          dict = {}
          s2 = s [i：i +（b-a）+ 1]
          for i in range（b-a+1）：
              如果s2 [i]不在dict中：
                 如果s1 [i]在dict的值中：break
                 dict [s2 [i]] = s1 [i]
              如果dict [s2 [i]]！= s1 [i]：break
          else:
              k + = 1
      ret.append（k）

   返回ret

s =“hjhhbcbk”
Q = [(1,2)，（2,4）]
print（solve（s，Q））