白駿1120号:文字列

5193 ワード
白駿 アルゴリズム#アルゴリズム# テキストリンク
リンク:https://www.acmicpc.net/problem/1120

問題を読む


なんてことだ.イヤホンを持っていません.しかし、私は屈服しません.今日はすぐにあなたに近づきます.
長さは等しく、文字列の違いを知る必要があります.2つの文字列XとYの違いはX[i]≠Y[i]のiの個数であるため、インデックスでのアクセスがより速くなる可能性がある.アレイまたはベクトル.ここでAとBの長さはせいぜい50なので、並べて近づけるのも難しくありません.ゲートを通る探索が正しいからです.
Aの長さはBの長さ以下であるため、Bの長さが長ければAとの差を減算する.->邪族になる.
AとBの長さが異なる場合は、演算前後でAにアルファベットを追加できます.もちろんやるべきことはBと同じだ邪族になる.

コード#コード#

#include<iostream>
#include<string>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string A, B;
	cin >> A >> B;
	int Asz = A.size();
	int Bsz = B.size();
	int wrong = Bsz; 
	//A와 B의 길이는 같은 상태
	for (int i = 0; i <= (Bsz-Asz); i++) {
		int tmp = 0;
		for (int j = 0; j < Asz; j++) {
			if (A[j] != B[i + j])
				tmp++;
		}
		wrong = (tmp > wrong) ? wrong : tmp;
	}
	cout << (wrong);
	return 0;
}

ぶんせき


実は貪欲な探求で行うこともできます.いずれにしても前後にアルファベットを貼って、なるべくBに貼って、真ん中は変わらないので、真ん中の差が一番小さいところを見つけるのが一番簡単な方法です.
Dev Log#2-6月29日
[白俊/DP]9095