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: Runtime Error

Solution code:
s=input()
l=input()
len_s=len(s)
len_l=len(l)
a=len_s-len_l
ans=1001
for i in range(len_s-a):
    cnt=0
    for j in range(len_s):
        if l[j]==s[i+j]:
            cnt+=1
    ans=min(ans,len_l-cnt)

print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
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: Runtime Error

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

ln = len(s)
lt = len(t)
n = ls - lt + 1
l = []

cnt = 0
for i in range(n):
    for j in range(lt):
        if t[j] != s[i + j]:
            cnt += 1
    l.append(cnt)
    cnt = 0
    
print(min(l))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using namespace std;
using ll = long long;
const ll mod = (ll)1e9 + 7;

int main() {
  string s, t;
  cin >> s >> t;
  int ans = INT_MAX;
  rep(i, t.size()) {
    for (int j = i; j < s.size() && t.size() - i <= s.size() - j; j++) {
      if (t[i] != s[j]) continue;
      int cnt = 0;
      rep(k, t.size()) if (t[k] != s[j - i + k]) cnt++;
      ans = min(cnt, ans);
    }
  }
  cout << ans << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
s = input()
t = input()
min_count = 1000
for i in range(len(s) - len(t) + ):
    count = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            count += 1
    min_count = min(count, min_count)
    if min_count == 0:
        break
print(min_count)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
q = []

for i in range(1,len(t)):
    if t[:i] in s: q.append(i)
if len(q) == 0:
    for j in t:
        if j in s: q.append(len(t)-1)
    
print(min(q))

Submission status: Runtime Error

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

l = len(T)

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

Submission status: Runtime Error

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

S = len(s)
T = len(t)
cnt=0
max=0

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

print(T-max)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

s = input()
t = input()

errors = []
for i in range(len(s)-len(t)+1):
    error = 0 
    for j in range(len(t)):
        if s[i+j] != t[j]:
            error += 1
    errors.append(error)
print(min(errors)

Submission status: Runtime Error

Solution code:
# B

S=input()
T=input()

def check(i,T):
    ns=S[i:i+len(T)]
    res=0
    for i in range(len(T)):
        if ns[i]!=T[i]:
            res+=1
    return res

print(min([check(i,T) for i in range(len(S)-len(T))]))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import bisect
import sys,io
import math
from collections import deque
from heapq import heappush, heappop

input = sys.stdin.buffer.readline

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    S= sRaw()
    T =sRaw()
    ans = 10*10
    for sidx in range(0,len(S)-len(T)+1):
        score = sum([1 for idx in range(len(T)) if S[sidx+idx]!=T[idx]])
        ans=min(score,ans)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
S = input()
T = input()
score_list = []
for i in range(0, len(S)-len(T)):
  s = S[i:i+len(T)]
  score = sum([1 if s[i]==T[i] else 0 for i in range(len(s))])
  score_list.append(score)
print(len(T) - max(score_list))

Submission status: Runtime Error

Solution code:
# abc177_b.py
S = input()
T = input()
for i in range(1,len(T)):
    if T[0:i] in S:
        continue
    else:
        ans = i
        break
print(len(T)-i)

Submission status: Runtime Error

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

def diff(a, b):
    return sum(aa != bb for aa, bb in zip(a, b))

answer = min( diff(S[i: i+len(T)], T) for i in range(len(S)-len(T)) )
print(answer)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(S, T):
    buf = []
    for i in range(len(S) - len(T)):
        diff = 0
        for j in range(len(T)):
            if S[i + j] != T[j]:
                diff += 1
        buf.append(diff)
    return min(buf)


def main():
    # parse input
    S = input().strip()
    T = input().strip()
    print(solve(S, T))


# tests
T1 = """
cabacc
abc
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
codeforces
atcoder
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
d,t,s = map(int,input().split())
if d <= s * t:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

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

Submission status: Runtime Error

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

anses = []
for i in range(len(s) - len(t)):
  cnt = 0
  for c, d in zip(s[i:i + len(t)], t):
    if c != d:
      cnt += 1
  anses.append(cnt)

print(min(anses))

Submission status: Runtime Error

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