Python에서 동일한 부분 문자열의 쌍 수를 찾는 프로그램

소문자 알파벳으로 구성된 두 개의 문자열이 제공된다고 가정합니다. 주어진 조건을 만족하는 쿼드러플(p, q, r, s)의 수를 찾아야 합니다. -

• 0 <=p <=q <=첫 번째 문자열의 길이.

• 0 <=r <=s <=두 번째 문자열의 길이.

• 첫 번째 문자열의 인덱스 p에서 시작하여 첫 번째 문자열의 인덱스 q에서 끝나는 부분 문자열은 두 번째 문자열의 인덱스 q에서 시작하여 두 번째 문자열의 인덱스 r에서 끝나는 부분 문자열과 같아야 합니다.

• q - r은 위의 조건을 만족하는 모든 quadruples 내에서 가능한 최소값이어야 합니다.

그런 4배의 수를 알아내야 합니다.

따라서 입력이 firstString ='hgfn', secondString ='gfrt'와 같으면 출력은 2가 됩니다.

조건을 만족하고 q - r에 대한 최소값을 갖는 두 개의 쿼드러플(1, 1, 0, 0) 및 (2, 2, 1, 1)이 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ord() 함수를 정의합니다. 이것은 ch
  이 걸릴 것입니다
  • ch의 유니코드 값 반환
• 메인 방법에서 다음을 수행하십시오 -
• left :=무한대 값을 포함하는 크기 26의 새 목록
• right :=값 -1을 포함하는 크기 26의 새 목록
• res :=0
• mi :=무한대
• 각 인덱스 i와 firstString의 문자 ch에 대해 do
  • left[ord(ch) - ord('a') ] :=(left[ord(ch) - ord('a') ], i)의 최소값
• 각 인덱스 i 및 secondString의 문자 ch에 대해 do
  • 오른쪽[ord(ch) - ord('a') ] :=오른쪽의 최대값[ord(ch) - ord('a') ], i
• 0에서 25 사이의 i에 대해
  • left[i]가 -1과 같지 않으면
    • mi :=(mi, left[i] - right[i])의 최소값
• 0에서 25 사이의 i에 대해
  • left[i]가 무한대와 같지 않고 right[i]가 -1과 같지 않으면
    • 왼쪽[i] - 오른쪽[i]이 mi와 같으면
      • res :=res + 1
• 반환 결과

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(firstString, secondString):
   left = [float('inf')] * 26
   right = [-1] * 26
   res = 0
   mi = float('inf')
   for i, ch in enumerate(firstString):
      left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
   for i, ch in enumerate(secondString):
      right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
   for i in range(26):
      if left[i] != -1:
         mi = min(mi, left[i] - right[i])
   for i in range(26):
      if left[i] != float('inf') and right[i] != -1:
         if left[i] - right[i] == mi:
            res += 1
   return res

print(solve('hgfn', 'gfrt'))

입력

'hgfn', 'gfrt'

출력

2