[BOJ] 백준 1120 문자열

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

Approach

문자열을 일일이 비교해서 차이를 최대로 하는 구간을 찾는 문제입니다.

주어지는 문자열 A <= B이며, 문자열 A에 앞,뒤로 임의의 문자를 추가할 수 있습니다.

그렇기에 처음 A가 B의 어떤 부분에서 불일치하는 문자가 최소가 되는지 찾으면 됩니다.

[문자열] KMP 알고리즘 

[문자열] KMP 알고리즘

 

A = abc,  B = xxbzzz

A 문자열을 우측으로 한칸씩 이동하며 일일이 비교

A = xabczz 가 되었을 때 만족.

---

import java.util.Scanner;
 
public class Main {    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        char A[] = sc.next().toCharArray();
        char B[] = sc.next().toCharArray();
         
        int answer = Integer.MAX_VALUE;
        // 문자열 길이 A <= B
        for(int i=0; i<=B.length - A.length; i++) {
            int cnt = 0;
            int k = i;
            for(int j=0; j<A.length; j++) {
                if(A[j] != B[k+j]) cnt++;
            }
            answer = Math.min(cnt, answer);
        }
        System.out.println(answer);
    }
}