두 개의 문자열 s와 t가 있다고 가정합니다(둘 다 소문자 영어 문자 포함). 우리는 크기가 3인 쌍의 목록을 찾아야 합니다. 여기서 각 쌍은 (l, k) 형식입니다. 여기서 k는 문자열이고 l은 길이입니다. 이제 이 세 쌍 중 첫 번째는 이 두 문자열의 가장 긴 공통 접두사 p인 s와 t의 부분 문자열을 포함하고 s의 나머지 부분은 s'이고 t의 나머지 부분은 t'입니다. 따라서 최종 목록은 [(length of p, p), (length of s', s'), (length of t', t')]와 같습니다.
따라서 입력이 s ="science" t ="school"과 같으면 출력은 [(2, 'sc'), (5, 'ience'), (4, 'hool')]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- lcp :=빈 문자열
- 0에서 s 크기 또는 t 크기의 최소값 범위에 있는 i에 대해
- s[i]가 t[i]와 같으면
- lcp :=lcp + s[i]
- s[i]가 t[i]와 같으면
- s_rem :=인덱스(lcp 크기)에서 끝까지 s의 부분 문자열
- t_rem :=인덱스(lcp 크기)에서 끝까지 t의 부분 문자열
- 세 쌍의 목록을 반환 [(size of lcp , lcp) ,(size of s_rem , s_rem) ,(size of t_rem , t_rem)]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(s, t): lcp = '' for i in range(min(len(s), len(t))): if s[i] == t[i]: lcp += s[i] s_rem = s[len(lcp):] t_rem = t[len(lcp):] return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)] s = "science" t = "school" print(solve(s, t))
입력
"science", "school"
출력
[(2, 'sc'), (5, 'ience'), (4, 'hool')]