Python에서 한 문자가 다른 부분 문자열을 계산하는 프로그램

<시간/>

두 개의 문자열 s와 t가 있다고 가정하면 s의 비어 있지 않은 부분 문자열을 선택하고 결과 부분 문자열이 t의 부분 문자열 중 하나가 되도록 단일 문자를 다른 문자로 대체할 수 있는 방법의 수를 찾아야 합니다. 위의 조건을 만족하는 부분 문자열의 수를 찾아야 합니다.

따라서 입력이 s ="sts" t ="tsts"와 같으면 출력은 6이 됩니다. 다음은 1 문자가 다른 s와 t의 부분 문자열 쌍이기 때문입니다. -

("sts", "tsts"),
("sts", "tsts"),
("sts", "tsts"),
("sts", "tsts"),
("sts", "tsts"),
("sts", "tsts")

굵은 문자 부분은 두 개의 문자열 s와 t에서 선택된 부분 문자열입니다.

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

n1 :=s의 크기
n2 :=t의 크기
ans :=0
s의 각 인덱스 i1과 문자 c1에 대해 다음을 수행합니다.
- 각 인덱스 i2 및 t의 문자 c2에 대해 do
  - i :=i1, j :=i2
  - i
  - i :=i + 1, j :=j + 1
- i
- :=i + 1, j :=j + 1
- ans :=ans + 1
- i
- i :=i + 1, j :=j + 1
- ans :=ans + 1

반환

예

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

def solve(s, t):
   n1 = len(s)
   n2 = len(t)
   ans = 0

   for i1, c1 in enumerate(s):
      for i2, c2 in enumerate(t):
         i = i1
         j = i2

         while i < n1 and j < n2 and s[i] == t[j]:
            i += 1
            j += 1

         if i < n1 and j < n2 and s[i] != t[j]:
            i += 1
            j += 1
            ans += 1
            while i < n1 and j < n2 and s[i] == t[j]:
               i += 1
               j += 1
               ans += 1

   return ans

s = "sts"
t = "tsts"
print(solve(s, t))

입력

"sts", "tsts"