Python中求相等子串对数的程序
假设我们有两个字符串，都由小写字母组成。我们必须找出满足给定条件的四元组 (p, q, r, s) 的数量 -
0 <= p <= q <= 第一个字符串的长度。
0 <= r <= s <= 第二个字符串的长度。
从第一个字符串的索引 p 开始到第一个字符串的索引 q 结束的子字符串必须等于从第二个字符串的索引 q 开始到第二个字符串的索引 r 结束的子字符串。
q - r 必须是满足上述条件的所有四元组中的最小可能值。
我们必须找出这样的四元组的数量。
因此，如果输入类似于 firstString = 'hgfn', secondString = 'gfrt'，那么输出将为 2。
有两个四元组 (1, 1, 0, 0) 和 (2, 2, 1, 1) 满足条件并具有 q - r 的最小值。
示例
让我们看看以下实现以获得更好的理解 -
def solve(firstString, secondString):left = [float('inf')] * 26
right = [-1] * 26
res = 0
mi = float('inf')
for i, ch in enumerate(firstString):
left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
for i, ch in enumerate(secondString):
right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
for i in range(26):
if left[i] != -1:
mi = min(mi, left[i] - right[i])
for i in range(26):
if left[i] != float('inf') and right[i] != -1:
if left[i] - right[i] == mi:
res += 1
return res
print(solve('hgfn', 'gfrt'))
输入
'hgfn', 'gfrt'输出结果
2
以上是 Python中求相等子串对数的程序 的全部内容， 来源链接： utcz.com/z/361409.html
