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