文字列のサブ文字列が別の文字列と完全に一致するか、Pythonの1つの位置で異なるインデックスを見つけるようにプログラムします

2つの文字列が提供されているとします。最初の文字列の長さは2番目の文字列よりも長いため、最初の文字列の部分文字列が2番目の文字列と正確に一致するか、1つの位置が異なるかを確認する必要があります。最初の文字列のインデックスを返します。ここで、2番目の文字列と一致する可能性のあるサブ文字列が始まります。

したがって、入力がstring1 ='tpoint'、string2 ='pi'の場合、出力は12になります。

2番目の文字列と一致するか、インデックス1と2の1つの位置が異なる最初の文字列の部分文字列は、「po」と「oi」です。

これを解決するには、次の手順に従います-

• 関数search（）を定義します。これにはstring1、string2
  が必要です
  • str_cat：=string1 + string2
  • z_list：=0で初期化されたstr_catのサイズの新しいリスト
  • z_list [0]：=str_catのサイズ
  • 右：=0
  • 左：=0
  • 範囲1からstr_catのサイズのiの場合は、
    • i>が正しければ、
      • j：=0
      • j +i
      • j：=j + 1
    • z_list [i]：=j
    • j> 0の場合、
      • 左：=i
      • 右：=i + j-1
  • それ以外の場合、
    • k：=i-左
    • r_len：=right --i + 1
    • z_list [k]
    • z_list [i]：=z_list [k]
  • それ以外の場合、
    • m：=右+ 1
    • m
    • m：=m + 1
    • z_list [i]：=m-i
    • 左：=i
    • 右：=m-1

例

理解を深めるために、次の実装を見てみましょう-

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