Python程序：查找字符串子串完全匹配或仅有一位差异的索引

假设，我们有两个字符串。第一个字符串的长度大于第二个字符串，我们需要检查第一个字符串的子串是否与第二个字符串完全匹配或仅有一位不同。我们返回第一个字符串中子串可能与第二个字符串匹配的起始索引。

因此，如果输入类似于 string1 = 'tpoint'，string2 = 'pi'，则输出将是 1 2。

第一个字符串中与第二个字符串匹配或仅有一位不同的子串（索引为 1 和 2）是 'po' 和 'oi'。

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

  • 定义一个函数 search()。它将接收 string1 和 string2 作为参数。
    • str_cat := string1 + string2
    • z_list := 一个新的列表，大小与 str_cat 相同，并初始化为 0。
    • z_list[0] := str_cat 的大小。
    • right := 0
    • left := 0
    • 对于 i 从 1 到 str_cat 的大小，执行以下操作：
      • 如果 i > right，则：
        • j := 0
        • 当 j + i < str_cat 的大小，并且 str_cat[j] 与 str_cat[j+i] 相同，执行以下操作：
          • j := j + 1
        • z_list[i] := j
        • 如果 j > 0，则：
          • left := i
          • right := i + j - 1
      • 否则：
        • k := i - left
        • r_len := right - i + 1
        • 如果 z_list[k] < r_len 且不为零，则：
          • z_list[i] := z_list[k]
        • 否则：
          • m := right + 1
          • 当 m < str_cat 的大小，并且 str_cat[m] 与 str_cat[m - i] 相同，执行以下操作：
            • m := m + 1
            • z_list[i] := m - i
            • left := i
            • right := m - 1
      • z_list[i] := string1 的大小和 z_list[i] 中的最小值。
    • 返回 z_list（从索引 string1 的大小到结尾）。
  • fwd := search(str2, str1)
  • bwrd := search(str2（从索引 0 到结尾），str1（从索引 0 到结尾）)
  • 反转列表 bwrd。
  • idx := 一个新的列表。
  • 对于 i 从 0 到 str1 的大小 - (str2 的大小 + 1)，执行以下操作：
    • 如果 fwd[i] + bwrd[i + (str2 的大小 - 1)] >= str2 的大小 - 1，则：
      • 在 idx 的末尾插入 i 的字符串表示形式。
  • 如果 idx 的大小为 0，则：
    • 返回 False。
  • 否则：
    • idx 的字符串表示形式。

示例

让我们看看以下实现以更好地理解：

def search(string1, string2):
   str_cat = string1 + string2
   z_list = [0] * len(str_cat)
   z_list[0] = len(str_cat)
   right = 0
   left = 0
   for i in range(1, len(str_cat)):
      if i > right:
         j = 0
         while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
            j += 1
         z_list[i] = j
         if j > 0:
            left = i
            right = i + j - 1
      else:
         k = i - left
         r_len = right - i + 1
         if z_list[k] < r_len:
            z_list[i] = z_list[k]
         else:
            m = right + 1
            while m < len(str_cat) and str_cat[m] == str_cat[m -i]:
               m += 1
            z_list[i] = m - i
            left = i
            right = m - 1
      z_list[i] = min(len(string1), z_list[i])
   return z_list[len(string1):]

def solve(str1, str2):
   fwd = search(str2, str1)
   bwrd = search(str2[::-1], str1[::-1])
   bwrd.reverse()
   idx = []
   for i in range(len(str1) - len(str2)+1):
      if fwd[i] + bwrd[i+len(str2)-1] >= len(str2)-1:
         idx.append(str(i))
   if len(idx) == 0:
      return False
   else:
      return (" ".join(idx))

print(solve('tpoint', 'pi'))

输入

'tpoint', 'pi'

输出

1 2

更新于: 2021年10月11日

164 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告