시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 256 MB 102 10 5 6.410%

문제

알파벳 소문자와 '?''*' 로 이루어진 두 문자열 S, T가 주어진다.

'?''*'는 와일드 카드 문자로 '?'는 임의의 알파벳 소문자로 대체할 수 있고, '*'는 임의의 알파벳 소문자로 이루어진 문자열로 대체할 수 있다. 단, 대체하는 문자열의 길이는 0일수도 있다.

와일드 카드를 포함한 두 문자열에서 각각의 와일드 카드 문자를 적절히 대체했을 때 두 문자열을 같게 만들 수 있다면 두 문자열이 유사하다고 하자.

당신은 두 문자열 S, T를 유사하게 만들기 위해서 S또는 T에 다음과 같은 연산을 할 수 있다.

  • 문자열의 임의의 위치에 문자 하나를 삽입한다. 이 때 삽입하는 문자는 알파벳 소문자 또는 '?' 또는 '*' 여야 한다.
  • 문자열의 임의의 위치에 있는 문자 하나를 삭제한다.
  • 문자열의 임의의 위치에 있는 문자 하나를 다른 문자로 치환한다. 이 때 치환되어 새로 생기는 문자는 알파벳 소문자 또는 '?' 또는 '*' 여야 한다.

이러한 연산을 최소 몇 번 시행해야 두 문자열 S, T를 유사하게 만들 수 있는지 구하여라.

입력

첫째 줄에 문자열 S가, 둘째 줄에 문자열 T가 주어진다. (1 ≤ |S|, |T| ≤ 250,000)

출력

첫째 줄에 S와 T를 유사하게 만들기 위해 필요한 연산의 최소 횟수를 출력한다.

예제 입력 1

ab?a
bba

예제 출력 1

1

S의 첫 번째 문자를 삭제하여 S="b?a", T="bba"로 만들면 1번의 연산으로 두 문자열을 유사하게 만들 수 있다.

혹은 T의 맨 앞에 'a'를 삽입하여 S="ab?a", T="abba"로 만들 수도 있다.

물론 이외에도 다양한 방법이 존재한다.

예제 입력 2

aaaaaaa
c

예제 출력 2

1

T의 첫 번째 문자를 '*'로 치환하면 S="aaaaaaa", T="*"으로 두 문자열을 유사하게 만들 수 있다.

예제 입력 3

??ab*
ababcd

예제 출력 3

0

출처

High School > 서울과학고등학교 > 2020 SciOI #1 I번