문자열 최소 차이

면접 대비

시간 제한2초메모리 제한128 MB

요약

짧은 문자열 A를 B의 부분 구간에 맞춰 가능한 모든 위치로 옮겨보며 문자가 다른 위치 개수의 최솟값을 구하는 문제입니다.

문제

길이가 같은 두 문자열 X와 Y의 차이는 같은 위치에서 서로 다른 문자의 개수이다.

두 문자열 A와 B가 주어진다. A의 길이는 B의 길이보다 작거나 같다. 두 문자열의 길이가 같아질 때까지 A의 앞이나 뒤에 임의의 알파벳 소문자를 추가할 수 있다.

추가한 문자는 원하는 대로 고를 수 있으므로, 이는 B 안에서 A와 길이가 같은 연속 부분 문자열 하나를 골라 A와 맞추는 것과 같다. 가장 잘 맞추었을 때 가능한 최소 차이를 구하라.

첫째 줄에 A와 B가 주어진다.

두 문자열은 알파벳 소문자로만 이루어져 있다. 각 문자열의 길이는 최대 50이며, |A| <= |B|이다.

A와 B의 길이를 같게 만들었을 때 가능한 최소 차이를 출력한다.