Problem:


Score : 200 points

Problem Statement

Given are two strings S and T.

Let us change some of the characters in S so that T will be a substring of S.

At least how many characters do we need to change?

Here, a substring is a consecutive subsequence. For example, xxx is a substring of yxxxy, but not a substring of xxyxx.

Constraints

The lengths of S and T are each at least 1 and at most 1000.

The length of T is at most that of S.

S and T consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

Print the minimum number of characters in S that need to be changed.

Sample Input 1

cabacc
abc

Sample Output 1

1

For example, changing the fourth character a in S to c will match the second through fourth characters in S to T.

Since S itself does not have T as its substring, this number of changes - one - is the minimum needed.

Sample Input 2

codeforces
atcoder

Sample Output 2

6



Sample input:
cabacc
abc


Sample output:
1

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())

s_num = len(s)
t_num = len(t)

max_count = 0
for i in range(s_num - t_num + 1):
    count = 0
    for j in range(t_num):
        if s[i + j] == t[j]:
            count += 1
    if count > max_count:
        max_count = count

print(t_num - max_count)

Submission status: Accepted

Solution code:
s = input()
t = input()
ans = len(t)

for i in range(len(s)-len(t)+1):
  ss = s[i:i+len(t)]
  count = 0
  for x,y in zip(t, ss):
    if x==y:
      count += 1
    ans = min(ans, len(t)-count)
  
print(ans)

Submission status: Accepted

Solution code:
parentalString = list(input())
childString = list(input())
numOfDiffs = []

for i in range(0,(len(parentalString) - len(childString))+1):
  count = 0
  for k in range(0,len(childString)):
    if childString[k] != parentalString[i+k]:
      count = count + 1
  numOfDiffs.append(count)

print(min(numOfDiffs))

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()

list_s1 = list(s1)
list_s2 = list(s2)

len_s1 = len(s1)
len_s2 = len(s2)

change_count_min = len_s2

for i in range(len_s1 - len_s2 + 1):
    change_count = len_s2
    for j in range(len_s2):
        if list_s1[j+i] == list_s2[j]:
            change_count -= 1

    if change_count < change_count_min:
        change_count_min = change_count
print(change_count_min)

Submission status: Accepted

Solution code:
S = str(input())
T = str(input())


ans = len(T)
for i in range(0,len(S)-len(T)+1):
  
  count = 0

  for j in range(0,len(T)):
    
    if S[i+j] == T[j]:
      count = count + 1
    else:
      count = count
  
  tmp = len(T)-count
  
  if ans > tmp:
    ans = tmp
  else:
    ans = ans

print(ans)

Submission status: Accepted

Solution code:
S = str(input())
T = str(input())
ans = 10000
for i in range(len(S)-len(T)+1):
    c = S[i:] 
    cnt = 0
    for j in range(len(T)):
        if str(T[j]) != str(c[j]):
            cnt += 1
    if cnt == 0:
        ans = cnt
    elif  ans > cnt:
        ans = cnt
print (ans)

Submission status: Accepted

Solution code:
S = input()
T = input()

min = len(T)

for index in range( len(S)-len(T)+1 ):
  temp = 0
  for index2 in range(len(T)):
    if T[index2] != S[index+index2]:
      temp += 1
  if temp < min:
    min = temp

print(min)

Submission status: Accepted

Solution code:
S = input()
T = input()

change_num = 1000000000
count = 0

for i in range(len(S)):
    if (len(T) + i) > len(S):
        break

    s = S[i:len(T) + i]
    for j, k in enumerate(s):
        if k != T[j]:
            count += 1

    if count < change_num:
        change_num = count

    count = 0


print(change_num)

Submission status: Accepted

Solution code:
S = input()
T = input()
value = 10000
score = 0

for x in range(len(S)):
  S_cut = S[x:x+len(T)]
  if len(S_cut) < len(T):
    break
  else:
    score = 0
    for y in range(len(T)):     
      if S_cut[y] != T[y]:
        score += 1
      else:
        continue
  if score < value:
        value = score
print(value)

Submission status: Accepted

Solution code:
S = input()
T = input()
res = len(T)
for i in range(len(S) - len(T) + 1):
    cnt = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            cnt = cnt + 1
    res = min(res, cnt)
print(res)

Submission status: Accepted

Solution code:
S = input()
T = input()

cntMIN = float("inf")
for s in range(len(S)):
    if s + len(T) - 1 > len(S) - 1:
        break

    cnt = 0
    for i in range(len(T)):
        if S[s + i] != T[i]:
            cnt += 1
    
    cntMIN = min(cnt, cntMIN)

print(cntMIN)

Submission status: Accepted

Solution code:
s = input()
t = input()

l_s = len(s)
l_t = len(t)

res = l_t
for i in range(l_s - l_t + 1):
    cnt = 0
    for j in range(l_t):
        if t[j] != s[i+j]:
            cnt+=1
    if res > cnt:
        res = cnt
print(res)

Submission status: Accepted

Solution code:
S=input()
T=input()
ans=0
if S==T: print(0); exit()
for i in range(len(S)-len(T)+1):
    tmp = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            tmp += 1
    ans = max(ans, tmp)
if not len(S) == ans:
  ans = len(T) - ans
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

S = input()
T = input()

m = len(T)

for i in range(len(S) - len(T) + 1):
    c = 0

    for j in range(len(T)):
        if (S[i + j] != T[j]):
            c += 1

    m = min(c, m)

print(m)
exit()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    import sys
    input = sys.stdin.readline

    S = input()
    T = input()

    len_S = len(S)-1
    len_T = len(T)-1
    # print(len_S)
    # print(len_T)
    # print(S)
    # print(T)
    ans = 0
    for i in range(len_S - len_T +1):
        cnt = len_T
        for j in range(len_T):
            # print("i:{} j:{}".format(i,j))
            # print(S[i+j])
            # print(T[j])
            if(S[i+j] != T[j]):
                cnt -= 1
        # print(cnt)
        # print(ans)
        ans = max(ans, cnt)
    print(len_T-ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    ans = 10000
    s = input().rstrip('\n')
    t = input().rstrip('\n')
    lent = len(t)
    lens = len(s)
    tmp = 0
    for i in range(lens-lent+1):
        tmp = 0
        for j in range(lent):
            if s[i:i+lent][j] != t[j]:
                tmp += 1
        ans = min(ans, tmp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
s = input()
t = input()

if (t in s):
    print(0)
    sys.exit()

ans = 1000
for i in range(len(s)-len(t)+1):
    diff = 0
    for j in range(len(t)):
        if (s[i+j] == t[j]):
            pass
        else:
            diff += 1
    
    ans = min(ans, diff)

print(ans)

Submission status: Accepted

Solution code:
#ABC177 B
S = list(input())
T = list(input())
min0 = len(T)
min = len(T)

for i in range(len(S) - len(T) + 1):
  c = 0
  for j in range(len(T)):
    if S[i + j] == T[j]:
      c += 1
  if (min0 - c) < min:
    min = min0 - c

print(min)

Submission status: Accepted

Solution code:
s=str(input())
t=str(input())
n=len(s)-len(t)
cl=[]
for i in range(n+1):
    cnt=0
    for j in range(len(t)):
        if s[j+i]==t[j]:
            cnt+=1
    cl.append(cnt)
print(len(t)-max(cl))

Submission status: Accepted

Solution code:
s = input()
t = input()

def count_ans(a,b):
    ans = 0
    for c1,c2 in zip(a, b):
        if c1 == c2:
            ans += 1
    return ans

ans = 0
for i in range(len(s)-len(t)+1):
    ans_ = count_ans(s[i:i+len(t)],t)
    if ans < ans_:
        ans = ans_

print(len(t)-ans)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S = _in[0]  # type:str
    T = _in[1]  # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = float('inf')
    S_ = list(S)
    T_ = list(T)

    for i in range(len(S_)-len(T_)+1):
        s_ = S_[i:i+len(T_)]
        cnt = 0
        for a,b in zip(s_, T_):
            if a == b:
                pass
            else:
                cnt += 1
        ans = min(ans, cnt)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s=input()
t=input()
a=len(s)
b=len(t)
C=0
for i in range(a-b+1):
    count=0
    for j in range(b):
        if s[i+j]==t[j]:
            count+=1
    C=max(C,count)
print(b-C)

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
mx = 0
for i in range(ls -lt + 1):
#  print(s[i])
  c = 0
  for j in range(lt):
#    print(i,j,s[i+j], t[j])
    if s[i+j] == t[j]:
      c+= 1
  if c > mx:
    mx = c
print(lt - mx)

Submission status: Accepted

Solution code:
from sys import stdin

s = stdin.readline().strip()
t = stdin.readline().strip()

def lev(t1, t2):
  cnt = 0
  for i in range(len(t1)):
    if t1[i] == t2[i]:
      cnt += 1
  return len(t1) - cnt

min_val = 9999
for i in range(len(s)-len(t)+1): # 始点
  l = lev(t, s[i:i+len(t)])
  if l < min_val:
    min_val = l

print(min_val)

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
l = list()
wake = len(s)-(len(t)-1)

for i in range(wake):
  l.append(s[i:i+len(t)])
gokei = len(t)
for i in l:
  sco = len(t)
  q = 0
  for j in i:
    if j == t[q]:
      sco -= 1
    q += 1
  if gokei > sco:
    gokei = sco
    
print(gokei)

Submission status: Accepted

Solution code:
S = str(input())
T = str(input())

max_len = 0
for i in range(len(S) - len(T) + 1):
    tmpS = S[i: i + len(T)]
    tmp_cnt = 0
    for j in range(len(T)):
        if tmpS[j] == T[j]:
            tmp_cnt += 1
    max_len = max(tmp_cnt, max_len)

print(len(T) - max_len)

Submission status: Accepted

Solution code:

s=input()
t=input()
ans=10000
lt=len(t)
ls=(len(s))
start,last=0,lt
while last<=ls:
    count=0
    j=0
    for i in range (start,last):
        if s[i]!=t[j]:
            count+=1
        j+=1
    ans=min(ans,count)
    start+=1
    last+=1


print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
N = len(s)
n = len(t)
m = 0
T = list(t)
S = list(s)
if N == n:
    for i in range(n):
        if T[i] == S[i]:
            m += 1
else:
    for i in range(N-n):
        cnt = 0
        for j in range(n):
            if S[i+j] == T[j]:
                cnt += 1
        if m < cnt:
            m = cnt
print(n-m)

Submission status: Accepted

Solution code:
import sys
def main():
    S = list(input())
    T = list(input())

    substrings = []
    for i in range(0, len(S) - len(T) + 1):
        substrings.append(S[i:i+(len(T))])

    ans = sys.maxsize
    for string in substrings:
        count = 0
        for i in range(len(T)):

            if string[i] == T[i]:
                count += 1

        # print(string, T, count)

        ans = min(len(T)-count, ans)

    print(ans)



main()

Submission status: Accepted

Solution code:
s = input()
t = input()

ls = len(s)
lt = len(t)

ans = 9999999
for i in range(ls-lt+1):

    tmp = 0
    for j in range(lt):
        if(s[i+j] != t[j]):tmp+=1
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
s=input()
t=input()
lens=len(s)
lent=len(t)

mxcnt=0
for i in range(lens-lent+1):
  cnt=0
  for j in range(lent):
    if  s[i+j]==t[j]:
      cnt+=1
      mxcnt=max(mxcnt,cnt)
print(lent-mxcnt)

Submission status: Accepted

Solution code:
S = input()
T = input()
s = len(S)
t = len(T)

count = 0
max = 0

for i in range(s-t+1):
  for j in range(t):
    if S[i+j] == T[j]:
      count += 1
  if count > max:
    max = count
    count = 0
  else:
    count = 0

print(t-max)

Submission status: Accepted

Solution code:
def solve():
    s = input()
    t = input()
    s_l, t_l = len(s), len(t)
    e = [s[i:i+s_l] for i in range(0, s_l-t_l+1)]
    ans = min([sum(i != j for i, j in zip(k, t)) for k in e])
    print(ans)


def main():
    t = 1
    while t > 0:
        solve()
        t -= 1


main()

Submission status: Accepted

Solution code:
s = input()
t = input()

num = len(s) - len(t) + 1

ans = []
for i in range(num):
  counter = 0
  for j in range(len(t)):
    if t[j] == s[j+i]:
      counter += 1
  ans.append(counter)
  
print(len(t) - max(ans))

Submission status: Accepted

Solution code:
s=input()
t=input()

l_s=len(s)
l_t=len(t)

m=[]

for i in range(0,l_s-l_t+1):
    s_b=s[i:i+l_t]
    x=0
    for j in range(0,l_t):
        if t[j]!=s_b[j]:
            x+=1
        else:
            continue
    m.append(x)
    
print(min(m))

Submission status: Accepted

Solution code:
S = input()
T = input()

n = len(T)
m = len(S)
L = []
R = []
for i in range(m-n+1):
    L.append(S[i:i+n:1])
count = 0
for word in L:
    for i in range(len(word)):
        if word[i] == T[i]:
            count += 1
    R.append(count)
    count = 0
print(n - max(R))

Submission status: Accepted

Solution code:
s = input()
t = input()


o = []
for i in range(0, (len(s) - len(t) + 1)):
    num = 0
    for j in range(len(t)):
        # print(i, j+i)
        if t[j] != s[i + j]:
            num += 1
    o.append(num)

# print(o)
o = min(o)
print(o)

Submission status: Accepted

Solution code:
s = input()
t = input()
if len(s) == len(t):
  a = 0
  for i in range(len(t)):
    if s[i] == t[i]:
      a+=1
  print(len(s)-a)
  exit(0)
g = []
for i in range(len(s)-len(t)):
  n = 0
  for j in range(len(t)):
    if s[i+j]==t[j]:
      n+=1
  g.append(len(t)-n)
print(min(g))

Submission status: Accepted

Solution code:
S=input()
T=input()
ans=len(T)

if len(T)!=len(S):
    for j in range(len(S)-len(T)+1):
        total=0
        for i in range(len(T)):
            if S[i+j]!=T[i]:
                total+=1
        if ans>=total:
            ans=total
else:
    ans=0
    for j in range(len(T)):
        if T[j]!=S[j]:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
S = input()
T = input()
B = np.zeros(len(S) - len(T) + 1)
for i in range(len(S) - len(T) + 1):
  a = 0
  for j in range(len(T)):
    if S[i + j] != T[j]:
      a +=1
  B[i] = a
print(int(min(B)))

Submission status: Accepted

Solution code:

def solve():
    s=input()
    t=input()
    ans=len(t)
    for i in range(0,len(s)-len(t)+1) :
        diff=0
        for j in range(0,len(t)) :
            diff+= 1 if s[i+j]!=t[j] else 0
            if diff>ans :
                break
        ans=min(ans,diff)
    return ans

print(solve())

Submission status: Accepted

Solution code:
import sys 

string1 = str(input())
string2 = str(input())

n, m = len(string2), len(string1) 

ans = sys.maxsize 
for i in range(m - n + 1): 
    minRemovedChar = 0 
    for j in range(n): 
        if (string2[j] != string1[i + j]): 
            minRemovedChar += 1
    ans = min(minRemovedChar, ans) 

print(ans)

Submission status: Accepted

Solution code:
# vim: fileencoding=utf-8


def main():
    s = input()
    t = input()
    lt = len(t)
    ans = lt
    for i in range(0, len(s) - lt + 1):
        sub = s[i : i + lt]
        c = 0
        for j in range(0, lt):
            if sub[j] != t[j]:
                c += 1
        if ans > c:
            ans = c
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()
T = input()

values = [[] for a in range(len(T))]
for i, s in enumerate(S):
    for n, v in enumerate(T):
        if v == s:
            values[n].append(i)

maxR = 0
for ni, val in enumerate(values):
    current_i = 1 + ni
    for i in val:
        if i < ni or len(S) - (i+1) < len(T) - (ni+1):
            continue
        current = 1
        for j in range(len(T) - current_i):
            s_index = i + j + 1
            if s_index >= len(S):
                break
            if S[s_index] == T[j+current_i]:
                current += 1
        maxR = max(current, maxR)

print(len(T) - maxR)

Submission status: Accepted

Solution code:
def main():
    import copy
    S = str(input())
    T = str(input())
    ans = 0
    temp = 0

    for i in range(len(S)) :
        #print("S=",S[i])
        ans = 0
        for j in range(len(T)):
            #print("S=", S[i+j])
            #print("T=", T[j])
            if i+j >= len(S) :
                ans = 0
                break
            #print("T=", T[j])
            #print("S=", S[i+j])
            if T[j] in S[i+j] :
                ans += 1
                #print(ans)
        temp = max(ans, temp)

    ans = len(T) - temp
    #if len(S) == 1 and len(T) == 1 and S == T :
    #    ans = 0
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

s = S()
t = S()

ls = len(s)
lt = len(t)
n_try = ls - lt + 1

ans = lt

for i in range(n_try):
    st = s[i:lt+i]
    buf = 0
    for j in range(lt):
        if st[j] !=  t[j]:
            buf += 1
    ans = min(ans, buf)

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()

if t in s:
    print(0)
else:
    s = list(s)
    t = list(t)

    l_t = len(t)
    l_s = len(s)
    count = [0] * (l_s - l_t + 1)
    for i in range(l_s - l_t + 1):
        s_list = s[i:i+l_t]
        for j in range(len(t)):
            if t[j] == s_list[j]:
                count[i] += 1
    
    # print(count)
    print(len(t) - max(count))

Submission status: Accepted

Solution code:
def kazu(S,T):
  s = len(S)
  t = len(T)
  anss = []
  for j in range(s - t + 1):
    ans = 0
    U = S[j:j+t]
    for k in range(t):
      if U[k] == T[k]:
        ans += 1
    anss.append(ans)
  print(t-max(anss))
  

S = input()
T = input()
kazu(S,T)

Submission status: Accepted

Solution code:
S = input()
T = input()
mm = 0
for i in range(len(S)-len(T)+1):
    a = S[i:i+len(T)]
    mm_now = sum([x == y for x,y in [*zip(a,T)]])
    mm = max(mm_now, mm)
print(len(T) - mm)

Submission status: Accepted

Solution code:
S = list(input())
T = list(input())
sl = len(S)
tl = len(T)

list1 = []
for i in range(sl-tl+1):
  count = 0
  x = list(zip (T,S[i:(i+tl)]))
 
  for j in range(tl):
    if x[j][0] == x[j][1]:
      count += 1
    list1.append(count)

print(tl - max(list1))

Submission status: Accepted

Solution code:
s = input()
t = input()
ans = 0
A = []
for i in range(len(s)-len(t)+1):
    s_i = s[i:i+len(t)+1]
    count = 0
    for j in range(len(t)):
        if s_i[j] == t[j]:
            count += 1
    A.append(count)

ans = len(t) - max(A)
print(ans)

Submission status: Accepted

Solution code:
s=input()
t = input()
min =(len(t))
for i in range(len(s)-len(t)+1):
    count = 0
    for ii in range(len(t)):
        if s[i+ii]!=t[ii]:
            count +=1
    if count <min:
        min = count
print(min)

Submission status: Accepted

Solution code:
s = input()
t = input()
ans=1000
for i in range(len(s) - len(t)+1):
    c = 0
    f = 0
    for j in range(i, i + len(t)):
        if s[j] != t[f]:
            c += 1
        f += 1
    ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    S = input()
    T = input()

    i = 0
    ans = INF
    while i < len(S)-len(T)+1:
        j, cnt = i, 0
        for t in T:
            s = S[j]
            if t == s:
                cnt += 1
            j += 1
        if cnt == len(T):
            # matched
            print(0)
            exit()
        ans = min(ans, len(T)-cnt)
        i += 1
    print(ans)

Submission status: Accepted

Solution code:
def solve(a,b):
    cnt=0
    for x in range(len(a)):
        if a[x]!=b[x]:
            cnt+=1
    return cnt        
s=input()
t=input()
k=len(t)
ans=k
for x in range(len(s)-len(t)+1):
    ans=min(ans,solve(s[x:x+k],t))
print(ans)

Submission status: Accepted

Solution code:
S,T = input(),input()
ans = len(T)

for i in range(len(S)-len(T)+1):
    sum = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:sum+=1
        # print(i,j,sum,S[i+j],T[i])
    ans = min(ans,len(T)-sum)
print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
min_num = len(t)
tbd = 0
for i in range(0,len(s)-len(t)+1):
    for j in range(len(t)):
        if s[i:i+len(t)][j] != t[j]:
            tbd += 1
    if tbd <= min_num:
        min_num = tbd
    tbd = 0

print(min_num)

Submission status: Accepted

Solution code:
S=input()
T=input()
a=[]
for i in range(len(S)-len(T)+1) :
  count=0
  for j in range(len(T)) :
    if S[i:i+len(T)][j]==T[j] :
      count+=1
  a.append(count)
print(len(T)-max(a))

Submission status: Accepted

Solution code:
def match_num(s, part_s):
    match = 0
    for (s_char, part_s_char) in zip(s, part_s):
        if s_char == part_s_char:
            match += 1

    return match


s = input()
t = input()

max_match = 0

for i in range(len(s)):
    if i+len(t) > len(s):
        break
    part_s = s[i:i+len(t)]
    match = match_num(t, part_s)
    if match > max_match:
        max_match = match

print(len(t)-max_match)

Submission status: Accepted

Solution code:
S = input()
T = input()

count = []
for i in range(len(S) - len(T) + 1):
    match_count = 0
    for s, t in zip(S[i:i+len(T)], T):
        if s in t:
            match_count += 1
    count.append(match_count)

print(len(T) - max(count))

Submission status: Accepted

Solution code:
S = input()
T = input() #部分文字列

# print(S, T)

# S をTの長さ - 1番地から初めてSの最後の番地までループさせ、１文字づつ一致を検索しカウントする
start_idx = 0
fix_words = 0
for i in range(len(T) - 1, len(S)):
  part = S[start_idx:i + 1]
  # print(part)
  
  tmp_fix_words = 0
  for q in range(len(part)):
    if part[q] == T[q]:
      tmp_fix_words += 1
  
  fix_words = max(tmp_fix_words, fix_words)
  # print(fix_words)
  
  start_idx += 1
  
print(len(T) - fix_words)

Submission status: Accepted

Solution code:
def main():
    S = input()
    T = input()
    minv = len(T)
    cnt = 0
    if T in S:
        print(0)
        exit()
    else:
        for i in range(len(S)-len(T)+1):
            for s, t in zip(S[i:len(T)+i], T):
                if s != t:
                    cnt += 1
            minv = min(minv, cnt)
            cnt = 0
    print(minv)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
T = input()

res = len(T)

for i in range(len(S)-len(T)+1):
    count = 0
    for j, t in enumerate(T):
        if S[i+j] != t:
            count += 1
    if count < res:
        res = count

print(res)

Submission status: Accepted

Solution code:
s = input()
t = input()

ans = 10000000000000
for i in range(len(s) - len(t) + 1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]: cnt += 1
    ans = min(cnt, ans)

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()

s_length = len(s)
t_length = len(t)

ans = 1000

if s_length != t_length:
  for i in range(s_length - t_length):
    diff = 0
    parts = s[i:t_length+i]
    for j in range(t_length):
      if parts[j] != t[j]:
        diff += 1
    if ans > diff:
      ans = diff
else:
  ans = 0
  for j in range(t_length):
    if s[j] != t[j]:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
S = input()
T = input() #s>t
ans = 1000
d = len(S) - len(T)
for i in range(d+1):
    s = S[i:i + len(T)]
    t = T
    a = 0
    #print(s,t)
    for j in range(len(T)):
        if not(s[j] == t[j]):
            a+=1
    if  a <ans:
        ans = a
print(ans)

Submission status: Accepted

Solution code:
import sys

def main():

	S = input()
	T = input()
	
	max = 0
	count = 0
	for i in range(len(S) - len(T)+1):
		count = 0
		for j in range(len(T)):
			if S[i+j] == T[j]:
				count = count +1
		if max < count:
			max = count
	
	print(len(T) - max)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()
T = input()
assert 1 <= len(S) and len(S) <= 1000
assert 1 <= len(T) and len(T) <= 1000
assert len(T) <= len(S)
for s in S:
    assert s.islower()
for t in T:
    assert t.islower()
len_T = len(T)
max_count = 0
for i in range(len(S)-len_T+1):
    count = 0
    for j in range(len_T):
        count += int(T[j] == S[i+j]) 
    max_count = max(count, max_count)
print(len_T - max_count)

Submission status: Accepted

Solution code:
S = input()
T = input()

if len(S)==len(T):
    count=0
    for i in range(len(T)):
        if T[i] != S[i]:
            count+=1
    print(count)

else:
    countbox=[]
    for n in range(len(S)-len(T)+1):
        count =0
        for i in range(len(T)):
            if T[i] != S[i+n]:
                count+=1
        countbox.append(count)
    print(min(countbox))

Submission status: Accepted

Solution code:
S = input()
T = input()

l = []
if len(S) != len(T):
  for i in range(len(S) - len(T)):
    cnt = 0
    for j in range(len(T)):
      if T[j] != S[i+j]:
        cnt += 1
    l.append(cnt)
  print(min(l))
else:
  cnt = 0
  for i in range(len(S)):
    if T[i] != S[i]:
      cnt += 1
  print(cnt)

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())

max_same = 0
ans = 0

for i in range(0,len(s)-len(t)+1):
        for j in range(0,len(t)):
                if s[i+j] == t[j] :
                            max_same += 1
        ans = max(ans, max_same)
        max_same = 0

print(len(t)-ans)

Submission status: Accepted

Solution code:
S = input()
T = input()
lens = len(S)
lent = len(T)
result = lent
cnt = 0

for i in range(0,lens-lent+1):
    for j in range(0,lent):
        if S[i+j] != T[j]:
            cnt = cnt + 1
    if result > cnt:
        result = cnt
    cnt = 0

print(result)

Submission status: Accepted

Solution code:
t = input()
s = input()

mxscore = -1
beststr = ''
for i in range(len(s),len(t)+1):
    check = t[i-len(s):i]
    now = 0
    for j in range(len(check)):
        if s[j] == check[j]:
            now += 1
    if now > mxscore:
        mxscore = now

print(len(s)-mxscore)

Submission status: Accepted

Solution code:
S = input()
T = input()
a = []
for i in range(len(S)-len(T)+1):
    count = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            count += 1
    a.append(count)
print(min(a))