在Python中找出相等子字符串对的数量

假设我们有两个仅由小写字母组成的字符串。我们需要找出满足以下条件的四元组（p，q，r，s）的数量 −

0<= p <= q<=第一个字符串的长度。
0<= r<= s<=第二个字符串的长度。
第一个字符串从索引p开始，以索引q结尾的子字符串必须等于第二个字符串从索引r开始，以索引s结尾的子字符串。
q-r必须是满足上述条件的所有四元组中最小的值。

我们需要找出这样的四元组的数量。

因此，如果输入如下：firstString = ‘hgfn’，secondString = ‘gfrt’，则输出将为2。

有两个满足条件且具有最小值q-r的4元组（1、1、0、0）和（2、2、1、1）。

为解决此问题，我们将执行以下步骤−

定义一个函数ord()。这将取出ch
- 将ch的unicode值返回
在主方法中执行以下操作 –
左侧：一个大小为26的新列表，包含无限大的值
右侧：一个大小为26的新列表，包含值为-1
结果：0
mi：无限大
对于firstString中的每个索引i和字符ch，执行以下操作 –
- left [ord(ch)- ord(‘a’)] ：=（left [ord(ch) – ord(‘a’)]，i）的最小值
对于secondString中的每个索引i和字符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 inrange(26):
      if left[i] != float('inf') and right[i] != -1:
         if left[i] - right[i] == mi:
            res += 1
   return res

print(solve('hgfn', 'gfrt'))