用 Python 编写程序，查找某个字符串的子字符串与另一个字符串完全匹配或在一个位置上不同的索引

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

假设，我们有两个字符串。第一个字符串的长度大于第二个字符串，我们必须检查第一个字符串中的子字符串是否与第二个字符串完全匹配或在一个位置上不同。我们返回第一个字符串的索引，其中可以与第二个字符串匹配的子字符串从该索引开始。

因此，如果输入为 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
    - if j > 0, then
      - 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，则
  - 在结尾处插入 i 的字符串表示形式idx
如果 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'))