백준[1120] 문자열

문제 설명

문제 링크

http://icpc.me/1120

풀이

A를 B의 부분 문자열과 비교할 때 A와 B의 부분 문자열 사이에 다른 개수를 세면 된다.

A와 길이가 같은 B의 부분 문자열과 비교를 하여 다른 부분을 구한다면, A의 나머지 추가하는 부분은 모두 B와 동일하게 앞뒤에 추가를 하면 되기 때문에 이렇게 풀 수 있다.

구현은 N이 50으로 매우 작기 때문에 전탐색 하면 된다.

코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string s1, s2; 
int ans = 1e9;

int main() {
    cin >> s1 >> s2;
    for (int i = 0; i <= s2.length() - s1.length(); i++) {
        int cnt = 0;
        for (int j = i, k = 0; j < i + s1.length(); ) {
            if (s1[k++] != s2[j++]) cnt++;
        }
        ans = min(ans, cnt);
    }    
    printf("%d", ans);
}