[1120] 문자열

https://www.acmicpc.net/problem/1120

1120번: 문자열

<문제>

남는 자리는 그리디적으로 Y와 같은 문자로 채워준다고 가정하면,

채워주지 않고 X의 문자를 그대로 사용하는 구간만 탐색하면 된다.

문자열의 길이를 각각 A, B라 하면 하나는 항상 [0, A)까지 비교하고,

다른 문자열에서 [0, B-A]를 시작점으로 갖는 길이 A의 두 문자열을 비교하면 된다. 

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

string a, b;

int ans = 54321;

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> a >> b;

    int i, j, A = a.length(), B = b.length();

    for (i = 0; i <= B - A; i++) {

        int cnt = 0;

        for (j = 0; j < A; j++) cnt += (a[j] != b[i + j]);

        ans = min(cnt, ans);

    }

    cout << ans;

    return 0;

}