백준 1120번: 문자열

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

1. 문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이 때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이 때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

2. 알고리즘

키워드 - 문자열 처리

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
/*
* @memory  - 1198 kb
* @time    - 0 ms
*/
int main() {
 
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    string str1, str2;
    cin >> str1 >> str2;
    int sol = 987654321;
    for (int i = 0; i <= str2.size() - str1.size(); ++i) {
        int cand = 0;
        for (int j = 0; j < str1.size(); ++j) {
            if (str1[j] != str2[j + i])
                cand++;
        }
        sol = min(sol, cand);
    }
    cout << sol;
 
    return 0;
}