用于查找字符串的子字符串与另一个字符串完全匹配或在 python 中的一个位置不同的索引的程序

Z时代
2024-01-10
分类：综合

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

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

第一个字符串中与第二个字符串匹配或在索引 1 和 2 的一个位置不同的子字符串是“po”和“oi”。

示例

让我们看看以下实现以获得更好的理解 -

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