18806번 - 와일드 카드

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

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

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

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

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

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

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

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