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:
import difflib

S = input()
T = input()

A = len(S)
B = len(T)

moji = []

for i in range(A-B+1):
  moji.append(S[i:i+B])
  

cnt = 0
cnt_list = []
for i in range(len(moji)):
  for j in range(B):
    if moji[i][j] != T[j]:
      cnt += 1
  cnt_list.append(cnt)
  cnt = 0
  
print(min(cnt_list))

Submission status: Accepted

Solution code:
import sys
import math
S = str(input())
T = str(input())
 
 
d = 0
for i,o in enumerate(S):
        j = 0
        c = 0
        for l in S[i:i+len(T)]:
            if l == T[j]:
                c += 1
            j += 1
        d = max(d, c)
        if i > len(S) - len(T) - 1:
            break
print(len(T)-d)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
S = input()
T = input()
ans = float("INF")
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(ans,cnt)
print(ans)

Submission status: Accepted

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

min_cnt = 1005
len_t = len(t)
length = len(s)
for i in range(length-len_t+1):
  cnt = 0
  for j in range(len_t):
    if t[j] != s[i+j]:
      cnt += 1
  min_cnt = min(cnt, min_cnt)
    
print(min_cnt)

Submission status: Accepted

Solution code:
def resolve():
    s = input()
    t = input()
    ans = 10**4

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

resolve()

Submission status: Accepted

Solution code:
s = input()
t = input()
count = 0
def ans(s, t):
    max = pow(10,9)
    if len(s)==len(t):
        max = 0
        for i in range(len(s)):
            if s[i]!=t[i]:
                max+=1
        return max
    else:
        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
            if max > count:
                max = count
        return max
print(ans(s,t))

Submission status: Accepted

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

if len(S) == 1:
    if S == T:
        print(0)
    else:
        print(1)

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

    # print(l)
    if len(l) > 0:
        a = len(T) - max(l)
        print(a)
    else:
        a = 1
        print(a)

Submission status: Accepted

Solution code:
def hamming(s,t):
    d = 0
    for i in range(len(s)):
        if s[i]!=t[i]:
            d+=1
    return d

def main():
    s = input()
    t = input()

    candidates = []
    for i in range(len(s)-len(t)+1):
        candidates.append(hamming(t,s[i:i+len(t)]))

    print(min(candidates))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()
T = input()
k = 0
x = 0
for i in range(len(S)-len(T)+1):
    s = S[i:]
    for j in range(len(T)):
        if s[j] == T[j]:
            x += 1
    if k<=x:
        k = x
    x = 0
print(len(T)-k)

Submission status: Accepted

Solution code:
def solve():
    Ss = input().rstrip()
    Ts = input().rstrip()

    lenS, lenT = len(Ss), len(Ts)

    ans = lenS
    for i in range(lenS-lenT+1):
#        print('# Ss:', Ss[i:i+lenT], '/ Ts:', Ts)
        num = sum([S != T for S, T in zip(Ss[i:i+lenT], Ts)])
        if num < ans:
            ans = num

    print(ans)


solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()
t=input()
ans=len(t)
for i in range(len(s)-len(t)+1):
  cnt=len(t)
  for j in range(len(t)):
    if s[i+j]==t[j]:
      cnt-=1
  if cnt<ans:
    ans=cnt
print(ans)

Submission status: Accepted

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

res = 10000000000

for i in range(0, len(s)-len(t)+1):
    m = 0
    # print(s[i:], t)
    for j, k in zip(s[i:],t):
        # print(j,k)
        if j==k:
            m += 1
            
    res = min(res, len(t)-m)

if(res==10000000000):
    print(len(t))
else: 
    print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

s = list(input())
t = list(input())

ans = len(t)

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

print(ans)

Submission status: Accepted

Solution code:
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91U=IKQ00000KmY&$000007%l(+0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000X%hed00000X%hed00000001BW000000RR911^@s6ARPbz00000ARQn800000ARQn800000_yPa`00000U<CjG00000001BW000000ssI21^@s6I2`~000000I2|AW00000I2|AW000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4kP!d?00000kP!d?00000kP!d?00000L;wH)00000L;wH)000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4ARPbz00000ARQn800000ARQn800000-~s>u00000-~s>u000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$_uOv>YUhfou9RsuqgUX}B}n#;0ssI2761SM0RR911^@s6000mI0RRL5761SM000006qpP{bCw4J000000000000000000000000000000-~a#s5&!@I00000000000000000000E&>1mA^-pY00000000000000000000eE<Le5&!@I00000000000000000000RR9105&!@I00000000000000000000#Q^{S5&!@I00000000000000000000CjtNf5&!@I000000000000000000008Ug?S5&!@I00000000000000000000*#H0l5&!@I000000000000000000007XbhO5&!@I000000000000000000002?78B5&!@I00000000000000000000VgUdE5&!@I00000000000000000000H30ws5&!@I000000000000000000009RUCU5&!@I000000000000000000000s#O35&!@I00000000000000000000a{vGU5&!@I000000000000000000009{>OVAOHXW00000000000000000000@Bsh-5&!@I00000000000000000000Jpup#5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000!2kdN5&!@I00000000000000000000SOEY45dawgKp-Fh000005CH%H00000xBvhE5dawgU?Cs?000007y$qP000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^DbTTksUvy}4Z+Bm8Wo~D5XkTS=a&K}_OJe|ET251MY;#3v0AE^DbTnmdWNb-eQ*<#gV`yP=UvzR|X>@Z*V?{+$Q*<#iVqtS>V_$D`baG{3ZAnyLR4`vfQ#M}!Us_XiGh=CP0AE^8Q*=0KZ*yN_VRL0PNp5L$L@`Bn0AE^UY*2OpUs_I6bU0~mb6;X%b7e6#b9ruKUw3JAXkT-5WNB|jVgO%XXLxvDaAk6HZ*F01X>@sCb}#^6T5fl30AE^8Q*=0KZ*yN_VRL0PNp5L$Lor2m0AE^DbTTwwUvy}4Z+BmBb#z~EW?yn)Zf9j*W^Hs(OJjNfUs_XiG-GddbO2vkQ*?53Nn=xVF)?FkVRBz|a$#w7b4g=GQ(;MCMMY9mbTKnxVRLC?Uuko6a%Ev{NmO4{FkeMeH(ydtQ*<|9Ut@T9F)=YRVqtS>V_$Q0a%pa7NmDdmQ#D^yF<(VR0AE^DbTK(!Uvy}4Z+Bm8Z)a&^UuAM~Z*oveV*qSvVrOGxUvn;VZ!R$aUsY~*X>Md+Qe|^>ZDjy#X<}n8b8jv-0AF8obYWv_Ut?%%UuI!xYye+hV|Za-VRU79X><T>Wo=_{c>rHuV|Za-W@&C=Y-xIB0AF8hX<}nvb97;HbYE>@X>I^VLqlIPE-(N`Oi4mRUotK<07pzoLPK9NE-^F!M@&gVLtip3GA=a$Ls(crLP=jSE;9f}Oi4mRSXf^(E;KGOFaSqPNkT(dSYI<PG%hkR07pzoLPJ<sUo$Q=000000ssR50ssO40ssU60{{X50ssX71^@>D0ssgA0ssI22>=5C000000ssO40ssI20RRC2;sF2v5C8xGAOHXWP$qc`000R9PXYh{000000RRI4{{a915C8xGKmY&$6lrM<000F5R{{V45C8xGl#!MO000C4VFCaE5C8xGbsA|200093YytoP000000RRL50RR915C8xG00000)30j<000O8cme<b5C8xGaQK%3000L7g8~2m5C8xGarl=4000I6k^%q#5C8xGbSaVu00062p#lH^00000ARQn8000002mk;800000U=RQR00000C><aG000002mk;800000Fb@C#00000FdZNO000002mk;800000AP@im000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s60ssI20000000000*dHJO000001^@s65C8xG0000000000;2$6W000001^@s65&!@I0000000000=pP^e000001^@s66951J0000000000@E;%m000001^@s66aWAK0000000000_#Yqu000001^@s66#xJL00000000005Fj7`000000RR914gdfE0000000000Kp-Fh000001poj5761SM0000000000U?Cs?000001poj57XSbN0000000000U>_g=000002LJ#70RR910000000000XdfT|000002LJ#70{{R30000000000a33H5000002LJ#71ONa40000000000cpo4D000002LJ#71poj50000000000fFB?L000002LJ#71^@s60000000000h#w#T000002LJ#72LJ#70000000000kRKob000002LJ#72mk;80000000000m>(bj000002LJ#72><{90000000000pdTOr000002LJ#73IG5A0000000000s2?Bz000002LJ#73jhEB0000000000upb}*000002LJ#73;+NC0000000000xE~+@000002LJ#74FCWD0000000000z#kw0000002LJ#74*&oF0000000000$R8j8000002LJ#75dZ)H0000000000NQ3MMNQ(u<6d(Xdg}`(I|IkQ-#0bLx|1}yEAOQa*926h`4<A4P|0Nm}AOL6p0002#;Q#;s|0NO>AOL6q0002#(EtDc|0N0(AOL6r0002#!2kdM|0MzxAOL6s0002#u>b%6|0VhpAOL6t0002#p#T5>|0VJhAOL6u0002#kpKVx|0U`ZAOL6v0002#fdBvh|0UuRAOL6w0002#aR2}R|0UWJAOL6x0002#VE_OB|0U8BAOL6y0002#Q2+n`|0T*3AOL6z0002#K>z>$|0Ti`AOL6!0002#F#rGm|0TK;AOL6#0002#ApigW|0S{$AOL6$0002#5dZ)G|0SvuAOL2N0000000000L03UmG5<kTK~z;!NP+B_0001FNQ(p|C;$KeNQs0bhyVZpF~I2M{{R0-jdUa+NR3=1KuC=}^b{ZfNXG@y6(9fr0000;$3!G300000NR37iNQrbL7{){-FaSu2TqF=k$3!GZ00000NQp!wAV`fv5XM9#Pyk4YL?l4y9RL6SNQvG^iO1*>|Ns9;i(DiqNQ*=yNQvHwL?i?$#))(!2oH#E0RR9@i)<tyOk?;=jdUbnOgZ~WjaCpz4@cijiS9@N-bjg5Bw%z2O@-|bgy8@H06~ewgXjUh0RR91i9{p}4<Cd800000NQ3(i4~NzO002mfR3u<XgZlwUiO>&(`~Uy|NQK)Eh1UQ80E<K<1W1WoBxuG28URR(d?a9nzz>dL0RRAtbR-N+i$o+qF~Bj>NQ1@!K@YYJ05}W>50$}4gTMg~w#fm?NIAxJ=Shu55J5TAL=R8mNIA!J1?U3)|Nl8`BnS_Tr~m)}NQ+z~C`dWo4~G!}002yjY$PB^DeFm%Mi5AeL?mEI0qsmV`$-Q+-%N?<NQ1=zNCDUngg^iP|4oJM4}~`W|NlshJ#Pa50O)%C|Nmw#4<Cd800000NQK)Eh!g<;07#8{0qCCn|NlsdL?mEHiCiRbNQv4^iS9^=$LLo5|NlsfR3u>O5&!@H4<A4PK@YY?0Ehxei&P|F>HPlx|3Qhw4<A4PNR2(|5g-6WiRS2`{r~?+iO1;a{Qv(*i$o+4NQ-<VKuCkY5J)-4bOq=k{r~?+i$o+CNQ-<VAV`D25J)-4bOq=M{r~?lz(|X<B!~b20AxrrG$kki004D;NP)zd00016T|rzyT|r(!U&CgQG1BS6{{R0-jWs3$002mhJyQYz07!}1NQvq(!07(`|Nlsd!$^xnBoIi8d?Y|fgTN3-ImdJb=%f7q|455OBp67Gd?X-9gTN3-ImdJb=!^XS|4517==1#l|45BJ<pBTy=r{cT|LBtZ|Nmx?NR2&06CeOcgX{?Cu>Al3NQ*tO5Fh|ZjTO2OAOJ{>H6#-t07!$x2<bBX|Nmx?G3`l-(OyW2;z)z!@K97tjRk4}002mh4f6m107#8Jto;A~{}omcAOQ3aA4C8ENR2&#5Fh|mNR0(~5Fh|ZIrvD4<#ZWHiv=nWAOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2%~5Fh|ZjWs$DAOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(vW4<G<Yg}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIU$XAOHY$FGzzupAR4a098nd<#Y^4i#^H@AOPsy`~UywNdN!;#sw)7AOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8EL03UmNr~4%RY6otjU}E8AOKZJjV-1OAOKTAiTz25_Dm_|NQ3MMNWuLB=y&@6|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF3VqtS>V_$Q0a%pa7Iy!T8VsmtI0AgWtX=7h=baH8KXF57xO<!YjWnpw>0000000000C389;Ute%<b08>pXlY|;AZc?TC3<x!AU+^;XlZjTK67b$Whf~iD0gUSV`w00b08&pbtwP<VqtS>V_$Q0a%pa7IyzrXUt@1>b98cbV{{;Hb!==PZf|rTc42I3WB>pF000000UHB5L;wH)2LJ#7p!xs*kN^Mxkoy1sxBvhEp!)y+@Bjb+p#A^<L;(N*(Eb1aU;qFB;Qs&rU;zLCQ2+n`r~v=~000006aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|SX#M~HD*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|S2>Jj2@Bjb+01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)(E0!W2mk;800000000008~^|S000000eVnOQUC#X5C@x`4Ils;8w>{skO2SyPyhe`Bme*asQLf@{sI611it_P074EBj{-st7>)x(4j_#LLJla51wjrlh6X_nID-dA4$uJuZ~_VrI6)3DK@KQF4j@7f7(xyZLJkN+3jhEB7ytkO&;S4cRQ&({E&u=k080)KUJeKV00000L;wH)>;M1&c>VwXWdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGGywnrp#A^<0ssI20000000000|Nj9MCItWhf3pO#1pw#;1pol_1qHGN00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000U=RQR00000Fb@C#00000AP@im000000RR91000000RR91000000RR9100000;sF2v000000RR9100000{{a91000003;+NC000007z+RZ000004FCWD00000<PZP=0000082|tP00000ARQn8000008vp<R000005C8xG000008UO$Q00000FdZNO000008~^|S000002mk;800000_5S~F00000m;wL*000001poj50000000jU5000001^@s600000zybgO000003IG5A00000tpWf5000003jhEB000007ytkO000006#xJL0000000000000000{{R300000NFN{o000000ssI200000Pyqk{000006aWAK000002LJ#7000007XSbN00000$O!-d000002LJ#700000kO%+(000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000;0FKz00000|NsAQ000000{{R300000@c;jB00000t_J`B00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I2|AW0000000000000000000000000MhgG{00000Rto?C00000W(xoS00000b_)Oi00000h6?}y00000mJ0v?00000rV9W700000whI6N00000#tQ%d00000)(Zdt00000<_iD-00000_6q<2000001`GfI0000077PFY0000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j900jU5000000000000000000000{{mAt_J`B000000000000000000000{{pB;0FKz000000000000000000000{{sCkO%+(000000000000000000000{{vD$O!-d000000000000000000000{{yE7z+RZ000000000000000000000{{#FFbe<x000000000000000000000{{&GAPfKi000000000000000000000{{*HFbn_y000000000000000000000{{;I<PZP=000000000000000000000{{>J@DKn1000000000000000000000{{^KkP!d?000000000000000000000{{{L*bx8#000000000000000000000{{~MP!j+E000000000000000000000{|2NARQn8000000000000000000000{|5OFdZNO000000000000000000000{|8PI2|AW000000000000000000000{|BQNFN{o000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000005dZ)H0ssyGFb@C#00000E&u=k00000B>(^b0RR~Qc_JVH000000RR9100000Gynhq1OV~>00000000000000000000KL7v#0ssyGkPiR=000000000000000K>z>%0ssyG&<_9r000000000000000Q~&?~0ssyGAP@im000000000000000Y5)KL0RR~Qcp@MG000000RR9100000c>n+a0RR;MFdZNO000000000000000pa1{>0ssyGU=RQR000000000000000tN;K20RR*LARQn8000000000000000Gynhq1OV~>00000000000000000000%K!iX0RR#JOcMYA000000000000000000001OV~>00000000000000000000*#H0l000pHkP!d?000000000000000>;M1&0RR>NI2|AW000000000000000^#A|>000yKFdZNO0000000000000001_1y7000yKARQn8000000000000000836zQ0RR^ONFN{o000000000000000F984m5C9ke7$6`3000000000000000UIPFCAOIKu03aX$000000000000000HUR(t5daVX@DKn1000001ONa400000MF9W+5&!@I00000000000000000000bO8VWA^-pY00000000000000000000AOHXW5&#YWFbn_y00000{sI6100000kO2Sy5&!@I00000000000000000000*Z}|l5&!@I000000000000000000000|Ed55ds(h2p}K;0000000000000005CQ-IAp#fx5Fj7`000002mk;800000ECK)k5&!@I00000000000000000000Qv?725&#bX<PZP=000000000000000RssM35&!@I00000000000000000000X#xNM5&!@I00000000000000000000g8~2m5&!@I00000000000000000000VgmpG5&#YWU=IKQ00000D*ylh00000mjVC)5&!@I00000000000000000000ssaE25&!@I00000000000000000000*8>0m5&#PT7z+RZ000000000000000#sUBU5ds(h7$6`3000000000000000(gFYg5&!@I00000000000000000000MFRi;5dawgKp-Fh000005CH%H00000Tmt|A5C9ke03aX$0000000000000000RaF25C9nffFd9O000000000000000X#)TN5C9nf7$6`3000000000000000bprqZ5&!@I00000000000000000000r~?215&!@I00000000000000000000%>w`c5&#YWa1a0h00000WdHyG00000-2(ss5&!@I00000000000000000000{sRC25&!@I000000000000000000006$AhPAOHXW00000000000000000000F$4er5&!@I00000000000000000000Ndy1@5&#YW;1B=+000000ssI200000Sp)z85dawgU?Cs?000007y$qP00000Zv+4U5&!@I00000000000000000000jsySzAOHXW00000000000000000000odf^?AOHXW00000000000000000000w*&wH5&!@I000000000000000000000773=bz*aLa%pa7E@N<T0AEK;PeMUVUte=|VqZyLZDDC{0AE^DbWAv3Uukb?ZfSG?V{&wJbaiHCE@J>>WpZU_X>)XCa$j_9Ut?@<Ze?=-UteTzUuSG@Vqt7wWOQ$Gb6;U~cmQK>ZE$R5bY)~NH#Rvq0AF8ZZ(nC@Z(?C=Uu1M|a&uo{b$DN9X>Ms>VRCX|d0%C2baHtBW^!R|WnW}<ZEbk~UteZ&VQpn!WOZ$Ad0%O6X>?y<a&lpLUuAA|a(Mt>Uq(_vO+{ZtPDEc{0AF86PE}t;NMA-$K}|(pNJLTqUqo3>K}|_R0AF8eZfSI1VRCX|d0%C2WB^}ZX>MtBUtw}`VR>J3bYXII0AEK;PeMUVUr$CxQ$<u?R6#;aMPC44Wn^J=VE|uAPhWF%WNB_+b#rB80AE^8Q*=0KZ*yN_VRL0MHFJ4xV_$b^bZB35bYy97MPfieM@&gVLs(c}GcGg$UteQ*VP9rxZeeU`dSyUBM@&gVLtip3GA=a$Us_XiG-YmNY)NBNbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeWzMM@&gVLs(c}GcGg$Us_XiGB96XbZByKcVBE}ZfA68UuAM~Z*oveV?aPhOi4mRSXf^(E;ImNUu1J{Uua=&WNc*sL{~0yWo9m4UuSrDUvOn|b8l{8Y-x0PUv@A6Us_XiF*#pfbZByKcVBF8XK7<!WpZ+Fa!^ZSKtM-KNkT(dSYI<PGyrX7ZDVkGKtM-KNkT(kGA=PR0AF8Ycwt{*bY*yHbU;8yOi4mRUotK-E;RsOT4Zccc0fQ!Oi4mRSXf^(E;ImNT5fl3KtM-KNkT(dSYI<PGyq>;b97;2YhPn%YhPwzX>341M@&gVLtip3Gyq>;R82!)MNULtUjScPQ*?53Nn=xVF)?FkVRBz|a$#w7b4g=GQ(;MCMMY9mbTKnxVRLC?Uuko6a%Ev{NmO4{FkeMeH(ydtQ*<|9Ut@T9F)=YRVqtS>V_$Q0a%pa7NmDdmQ#D^yF<(VRKtM-KNkT(dSYI<PG%hkR0AE^DbTngcb#y>LM@&gVLs(c}GcGg$UteTlbYWj}bYXII0AF8Xb8}yFbYXII0AE^DbTTwwUvy}4Z+BmBb#z~EW?yn)Zf9j*W^Hs(OJjOKKu1hTLPJ<sUo$Q=E;29xUs_I6bU0~mb6;X%b7eG1ZfSHwF-3MjKu1hTLPJ<sUo$Q=0AF8hX<}nvV{>(1X>MtB0AF8ccz9oMWpZ<GZeeU`ba`KPFhD><SXe<qNnbH8GXP&&PE&7eb46)DKu1hTLPJ<sUo$Q=0AEQ|O<!bXa%E>}b97~LR82!{Z*FB&VPb4$0AE#ZcWG{9Us7drb!}xpKu1GEUo$Q+0AF8hX<}nvV{>(1W@&C|0AE^DbTeaVZa_dsOi4mRSXf^(E;ImNUu<b&V_$Q0VRCd|ZDDC{KtM-KNkT(kGA=SMH2_~<XKin8UvqR}a&%u`0AEQ|O<!_lXK8bEWpY$aLu_wuWmI8eY-IpnT251RIB9QlUt(c%Wi&}{X>>#}MRq_yM@&gVLs(c}GcGg$04{TRZFFH`04{TMa&%#004{TAb98caVPXI-X>N37a&Q1HZf|sDE<r*`Ep%aL04{ECbY(7QZgnnVb!lv5Eoo!`E@y6aE@)wMXaFu`d2VxgZ2&H0d2VxbasV!8ZgnnpWpZ<AZ*BlCXKr;ac4cyNX>V>{asV!JWo%(CWO;4?E^=jTVJ>iNbO0`CZfSG?E^usgE@y9a04{W8cys_RW@&C|04{QGWMOn+04`-{UuJS)ZDn6*WO4v5WoTb!a$#*{04`@^V_#)>V`Xr3Uvyz&Y-Ip0X>MtBUtw}`VR-;9W@&C|Utw}`VR-;9WO;63ZE0fwE@WYJVE`^-b8`SLV{dJ3Wo~o;00000000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO00000Kmq^&000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI20000000jU50000000jU500000tpWf50000000000000000RR91000000000000000UH||9|NsAQ0ssI200000t_J`B00000t_J`B00000FaQ7m000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000;0FKz00000;0FKz00000umAu6000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000kO%+(00000kO%+(00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000$O!-d00000$O!-d00000Pyqk{000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s6000007z+RZ000007z+RZ000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000Fbe<x00000Fbe<x00000@Bjb+0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000APfKi00000APfKi000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000Fbn_y00000Fbn_y00000vIGDC0000000000000005C8xG000000000000000qW}N^0RR911^@s600000<PZP=00000<PZP=000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000@DKn100000@DKn100000pa1{>0000000000000002mk;8000000000000000u>b%70RR910ssI200000kP!d?00000kP!d?00000L;wH)0000000000000001ONa4000000000000000zW@LL0RR910ssI200000*bx8#00000*bx8#00000cmV(a0000000000000002mk;8000000000000000$p8QV0RR910ssI200000P!j+E00000P!j+E0000082|tP0000000000000000RR91000000000000000+W-In4gdfE0{{R300000ARQn800000ARPbz000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000FdZNO00000FdYB@000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000I2|AW00000I2`~0000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000NFN{o00000NFM+I00000xBvhE0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000Kp-Fh000007$5)u00000Kmq^&000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000;0FKz000008~^|SE&u=k2mk;8000007ytkO000002><{90{{R300000000000000000000C@25`00000+ynps0000000000000000RR910000000000000005dZ)H0{{R3000000000000000000001T6pn000005CH%H0000000000000000RR91000000000000000"

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
try:
    s=input()
    t=input()
    ls=len(s)
    lt=len(t)
    ans=float('inf')
    for i in range(ls-lt+1):
        s2=s[i:i+lt]
        m=0
        #print(s2)
        for j in range(lt):
            if s2[j]!=t[j]:
                m+=1
        ans=min(ans,m)
    print(ans)
except EOFError as e:
    print(e)

Submission status: Accepted

Solution code:
s = input()
t = input()
ans = 10**9
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
    ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
import sys                                                                                                                               
                                                                                                                                         
S = input()                                                                                                                              
T = input()                                                                                                                              
                                                                                                                                         
##print(S)                                                                                                                               
##print(T)                                                                                                                               
                                                                                                                                         
flag = 0                                                                                                                                 
count = 0                                                                                                                                
                                                                                                                                         
##print(len(T))                                                                                                                          
s_len = len(S)                                                                                                                           
t_len = len(T)                                                                                                                           
                                                                                                                                         
start = 0                                                                                                                                
min = t_len                                                                                                                              
                                                                                                                                         
for start in range(0, s_len - t_len + 1):                                                                                                
    diff = 0                                                                                                                             
    for i in range(0, t_len):                                                                                                            
        if T[i] != S[start + i]:                                                                                                         
            diff = diff + 1                                                                                                              
                                                                                                                                         
    if min > diff:                                                                                                                       
        min = diff                                                                                                                       
                                                                                                                                         
                                                                                                                                         
print(min)

Submission status: Accepted

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

def matchcount(x, y):
    ret = 0
    for i in range(len(x)):
        if x[i] == y[i]: ret += 1
    return ret

rec = len(T)
for i in range(len(S)-len(T)+1):
    subst = S[i:i+len(T)]
#    print(subst, matchcount(subst, T))
    rec = min(rec, len(T) - matchcount(subst, T))

print(rec)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S=str(input())
T=str(input())
L=len(T)
result=1000
for i in range(0,len(S)-len(T)+1):
  count=0
  for j in range(len(T)):
    if S[i+j]!=T[j]:
      count+=1
  if result>count:
    result=count
print(result)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
S=input()
T=input()
ls=len(S)
lt=len(T)
ans=lt
for i in range(ls-lt+1):
    temp=lt
    for j in range(lt):
        if T[j]==S[i+j]:
            temp-=1
    if temp<ans:
        ans=temp
print(ans)

Submission status: Accepted

Solution code:
def main():
    S = input()
    T = input()
    # Sのi文字目をTの先頭として，それらの文字列の一致度を見る．

    st = set()
    for i in range(len(S)-len(T)+1):
        cnt = 0
        for s, t in zip(S[i:i+len(T)], T):
            cnt += s == t
        st.add(cnt)
    print(len(T) - max(st))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
S = input()
T = input()
c =0
C = [0]
for i in range(len(S)):
  c = 0
  for j in range(len(T)):
    if S[i] == T[j] and i-j >= 0 and len(S)-i -1 >= len(T)-j -1:
      
      c = 1
      if not(i == len(S)-1 and j == len(T)-1):
        for k in range(len(T) - j-1):
          if S[i + k + 1] == T[j + k +1]:
            c += 1
        C.append(c)
        c = 0
      else:
        C.append(c)
print(len(T)-max(C))

Submission status: Accepted

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

    ans = len(t)
    for v in range(len(s) - len(t) + 1):
        a = [t[i] != x for i, x in enumerate(s[v:len(t)+v])]
        if sum(a) < ans:
            ans = sum(a)
    print(ans)


if __name__ == '__main__':
    Qb()

Submission status: Accepted

Solution code:

import random, string
S = input()
T = input()
l = len(T)
L = len(S)
max_ans = -1
for i in range(L):
   ans = 0
   if i + l > L:
      continue
   for j in range(l):
      if T[j] == S[i + j]:
            ans += 1
   max_ans = max(max_ans, ans)
print(l - max_ans)

Submission status: Accepted

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

ans=len(S)
for start in range(len(S)-len(T)+1):
    dif=0
    for i in range(len(T)):
        if(T[i]!=S[start+i]):
            dif+=1
    ans=min(ans,dif)

print(ans)

Submission status: Accepted

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

stri = []
for i in range(len(s)-len(t)+1):
    j = i+ len(t)
    stri.append(s[i:j])
maxcount = 0
for i in range(len(stri)):
    count = 0
    for j in range(len(t)):
        if(stri[i][j] ==t[j]):
            count+= 1
    maxcount = max(maxcount,count) 
print(len(t)-maxcount)