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
- for i in range 1 to size of str_cat，执行以下操作
  - 如果i>right，则
  - j: = 0
  - while 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]
    - z_list [i]: = z_list [k]
  - 否则，
    - m：= right + 1
    - while m
    - 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[from index 0 to end]，str1[from index 0 to end]）
反转列表bwrd
idx：=新列表
for i in range 0 to size of str1-(size of str2+1)，do
- 如果fwd [i]+bwrd [i+ (size of str2-1)]> = size of 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'))