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]] 的字符串表示形式
- 如果 s[i] 不在 dict 中,则
- 返回 fp 的整数形式
- 从主方法中,执行以下操作:
- 如果 s 的大小 > 10,则
- 对于 i 从 0 到 s 的大小 - 10,执行以下操作:
- x := calc_fingerprint(s[从索引 i 到 i+9])
- 将 x 插入 fp 的末尾
- 对于 i 从 0 到 s 的大小 - 10,执行以下操作:
- 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]
- 如果 s1[i] 在 dict 的值中,则
- 如果 dict[s2[i]] 与 s1[i] 不相同,则
- 退出循环
- 如果 s2[i] 不在 dict 中,则
- 否则,
- k := k + 1
- 如果 b-a > 9 且 fp[a-1] 与 fp[i] 不相同,则
- 将 k 插入 ret 的末尾
- 返回 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))
输入
"hjhhbcbk", [(1,2), (2,4)]
Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.
输出
[6, 1]
广告