用 Python 编写程序找出相等子字符串对的数量

pythonserver side programmingprogramming更新于 2025/12/12 18:52:17

假设我们有两个字符串，均由小写字母组成。我们必须找出满足给定条件 − 的四元组 (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 的最小值。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 ord() 。这将获取 ch
- 返回 ch 的 unicode 值
从 main 方法执行以下操作 −
left := 一个大小为 26 的新列表，包含值 infinity
right := 一个大小为 26 的新列表，包含值 -1
res := 0
mi := infinity
对于每个索引 i 和 firstString 中的字符 ch，执行
- left[ord(ch) - ord('a') ] := minimum of (left[ord(ch) - ord('a') ], i)
对于每个索引 i 和 secondString 中的字符 ch，执行
- right[ord(ch) - ord('a') ] := right[ord(ch) - ord('a') ], i 的最大值
对于 0 到 25 范围内的 i，执行
- 如果 left[i] 不等于 -1，则
  - mi := (mi, left[i] - right[i]) 的最小值
对于 0 到 25 范围内的 i，执行
- 如果 left[i] 不等于无穷大且 right[i] 不等于 -1，则
  - 如果 left[i] - right[i] 与 mi 相同，则
    - res := res + 1
返回 res

示例

让我们看看下面的实现以便更好地理解 −


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'))