백준 1120번 문자열(python)

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

1120번: 문자열

문제

길이가 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의 차이를 최소로 하는 프로그램을 작성하시오.

 

해설

문자열 B중에서 A와 가장 같은 부분이 많은 A길이의 연속된 구간을 찾은 후 나머지 부분의 원소들은 똑같이 A에 추가하면 되므로 B의 인덱스를 A와 B의 길이 차이 만큼 1씩 옮겨가면 각 경우에 두 문자열의 차이를 구하여 가장 작은 값을 출력한다.

 

PYTHON

A, B = input().split()
min=len(A)
for j in range(len(B)-len(A)+1):
    count=0
    for i in range(len(A)):
        if A[i] != B[i+j]:
            count+=1
    if count < min:
        min =count
print(min)