문자열의 부분 문자열이 다른 문자열과 완전히 일치하거나 파이썬에서 한 위치에서 다른 인덱스를 찾는 프로그램

두 개의 문자열이 제공된다고 가정합니다. 첫 번째 문자열은 두 번째 문자열보다 길이가 더 길고 첫 번째 문자열의 부분 문자열이 두 번째 문자열과 정확히 일치하는지 아니면 한 위치에서 다른지 확인해야 합니다. 두 번째 문자열과 일치할 수 있는 부분 문자열이 시작되는 첫 번째 문자열의 인덱스를 반환합니다.

따라서 입력이 string1 ='tpoint', string2 ='pi'와 같으면 출력은 1 2가 됩니다.

두 번째 문자열과 일치하거나 인덱스 1과 2에서 한 위치가 다른 첫 번째 문자열의 부분 문자열은 '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에 대해
    • 내가> 맞다면
      • j :=0
      • j + i
      • j :=j + 1
    • z_list[i] :=j
    • j> 0이면
      • 왼쪽 :=나
      • 오른쪽 :=i + j - 1
  • 그렇지 않으면
    • k :=i - 왼쪽
    • r_len :=오른쪽 - i + 1
    • z_list[k]
    • z_list[i] :=z_list[k]
  • 그렇지 않으면
    • m :=오른쪽 + 1
    • m
    • m :=m + 1
    • z_list[i] :=m - 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