[백준] 문자열

문제요약

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

아이디어

완전탐색으로 풀었다.
X가 Y와 겹쳐 위치할 수 있는 자리를 돌아다니며 각 경우마다 X와 Y가 겹치는 글자수+나머지는 내가 원하는대로 채움

소스코드

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

int ctr_same(string &a, string &b, int s) {
	int ret = 0;
	for (int i = s; i <= s+a.size()-1; i++) {
		if (a[i - s] == b[i]) {
			ret++;
		}
	}
	return ret;
}

int main() {
	string a, b;
	cin >> a >> b;
	int max_same = 0;
	for (int i = 0; i <= b.size()- a.size(); i++) {
		int same = ctr_same(a, b, i);
		same += i;
		same += b.size() - (i + a.size());
		max_same = max(max_same, same);
	}
	cout << b.size()-max_same << endl;
	
}