Problem:


Score : 500 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.

Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').

Notes

A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

Constraints

1 \leq |s| \leq 10^5

1 \leq |t| \leq 10^5

s and t consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If there exists an integer i satisfying the following condition, print the minimum such i; otherwise, print -1.

Sample Input 1

contest
son

Sample Output 1

10

t = son is a subsequence of the string contestcon (the first 10 characters in s' = contestcontestcontest...), so i = 10 satisfies the condition.

On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s'), so i = 9 does not satisfy the condition.

Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10.

Sample Input 2

contest
programming

Sample Output 2

-1

t = programming is not a substring of s' = contestcontestcontest.... Thus, there is no integer i satisfying the condition.

Sample Input 3

contest
sentence

Sample Output 3

33

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.



Sample input:
contest
son


Sample output:
10

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import deque
import bisect
import sys

# 準備
idx = 0
charcode_mapper = {}
for ch in "abcdefghijklmnopqrstuvwxyz":
    charcode_mapper[ch] = idx
    idx += 1

s = input().strip()  # e.g., "contest"
t = input().strip()  # e.g., "son"
# s = "contest"
# t = "son"
# t = "programming"
# t = "sentence"

# s 中の文字の出現順序を保持する (本当は一行でできそう)
# こういうリストを作る (イメージ)
# [
#     [x, y],  # a の出現位置
#     [z],     # b の出現位置
#     ...,
#     [i, j]   # z の出現位置
# ]
char_idx = 0
char_positions = [[] for _ in range(26)]  # 26文字分


def extend_char_positions():
    global char_idx
    for ch in s:
        char_positions[charcode_mapper[ch]].append(char_idx)
        char_idx += 1


extend_char_positions()
extend_char_positions()

# print(charcode_mapper)
# print(char_positions)

# idx を 0 とする
# t の文字をなめていき、char_positions の idx より先にその文字が存在するかどうか確認する
#   あれば)
#     idx をそこまで進める
#     `(len(s)  - idx) < len(t)` であれば char_positions を伸ばす
#   なければ)
#     return -1

idx = 0
for ch in t:
    charcode = charcode_mapper[ch]
    idx = bisect.bisect_left(
        char_positions[charcode],
        idx,
        0,
        len(char_positions[charcode])
    )
    # print(ch)  # s
    # print(char_positions[charcode])  # [5, 12]
    try:
        idx = char_positions[charcode][idx]
    except Exception:
        print('-1')
        sys.exit(1)
    # print(idx)
    if len(s) - idx < len(t):
        extend_char_positions()


print(idx + 1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import deque
import bisect
import sys

# 準備
idx = 0
charcode_mapper = {}
for ch in "abcdefghijklmnopqrstuvwxyz":
    charcode_mapper[ch] = idx
    idx += 1

s = input().strip()  # e.g., "contest"
t = input().strip()  # e.g., "son"
# s = "contest"
# t = "son"
# t = "programming"
# t = "sentence"

# s 中の文字の出現順序を保持する (本当は一行でできそう)
# こういうリストを作る (イメージ)
# [
#     [x, y],  # a の出現位置
#     [z],     # b の出現位置
#     ...,
#     [i, j]   # z の出現位置
# ]
char_idx = 0
char_positions = [[] for _ in range(26)]  # 26文字分


def extend_char_positions():
    global char_idx
    for ch in s:
        char_positions[charcode_mapper[ch]].append(char_idx)
        char_idx += 1


extend_char_positions()
extend_char_positions()

# print(charcode_mapper)
# print(char_positions)

# idx を 0 とする
# t の文字をなめていき、char_positions の idx より先にその文字が存在するかどうか確認する
#   あれば)
#     idx をそこまで進める
#     `(len(s)  - idx) < len(t)` であれば char_positions を伸ばす
#   なければ)
#     return -1

idx = 0
for ch in t:
    charcode = charcode_mapper[ch]
    idx = bisect.bisect_left(
        char_positions[charcode],
        idx,
        0,
        len(char_positions[charcode])
    )
    # print(ch)  # s
    # print(char_positions[charcode])  # [5, 12]
    try:
        idx = char_positions[charcode][idx]
    except IndexError:
        print('-1')
        sys.exit(1)
    # print(idx)
    if len(s) - idx < len(t):
        extend_char_positions()


print(idx + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()
d = defaultdict(list)

for i, x in enumerate(s):
    for j in range(len(t)):
        d[x].append(i + len(s) * j)
for x in d.values(): x.sort()

ans = 0
for x in t:
    if x not in d: print(-1); exit()
    ans = d[x][bisect_right(d[x], ans)]

print(ans+1)

Submission status: Runtime Error

Solution code:
import sys


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

    appear_pos = {}  # 文字が出てくる場所
    for idx, T in enumerate(t):
        if T not in appear_pos:
            appear_pos[T] = [idx]
        else:
            appear_pos[T].append(idx)

    search_idx = {}
    for key in appear_pos.keys():
        search_idx[key] = 0

    loop_count = 0
    find_idx = 0
    for S in s:
        if S not in appear_pos:
            print(-1)
            sys.exit()

        if len(appear_pos[S]) > search_idx[S]:
            idx_new = appear_pos[S][search_idx[S]]
        else:
            idx_new = appear_pos[S][search_idx[0]]
        search_idx[S] += 1

        if idx_new > find_idx:
            find_idx = idx_new
            continue

        # 初期化
        find_idx = idx_new
        loop_count += 1
        for key in appear_pos.keys():
            search_idx[key] = 0

    print(find_idx+loop_count*len(t)+1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


def main():
    from bisect import bisect_right

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    # KeyInsight
    # 部分列判定：場所i以降で文字Cが最初に現れる位置を高速に求める
    # アルファベットの出現位置をリストで記録

    # sで各文字が出現する位置を2周分記録
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 1
    p = 0

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        p = alpha[c][bisect_right(alpha[c], p)]

        if p > n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


def main():
    from bisect import bisect

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    # KeyInsight
    # 部分列判定：場所i以降で文字Cが最初に現れる位置を高速に求める
    # アルファベットの出現位置をリストで記録

    # sで各文字が出現する位置を2周分記録
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 1
    p = 0

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        p = alpha[c][bisect(alpha[c], p)]

        if p > n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ans = None
for i in range(len(t)):
    if t[i] not in s:
        ans = -1
        break
else:
    ss = s * len(t)
    tg = 0
    ans = 0
    for i in range(len(ss)):
        ans += 1 
        if tg == len(t):
            break
        if ss[i] == t[tg]:
            tg += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import bisect


S = input()
T = input()

if set(T) - set(S):
    print(-1)
    exit()

dic = defaultdict(list)
leng_dic = defaultdict(int)

for pos, s in enumerate(S):
    dic[s].append(pos)
    leng_dic[s] += 1

length = len(S)
now = -1
count = 0
for t in T:
    if dic[t][-1] < now:
        now = -1
        count += 1
    idx = bisect.bisect_left(dic[t], now+1)
    now = dic[t][idx]

ans = count*length + now + 1
print(ans)

Submission status: Runtime Error

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

ss = s*len(t)
k = 0
ans = 0
while k < len(t):
    try:
        ans += ss.index(t[k]) + 1
        ss = ss[ss.index(t[k])+1:]
        k += 1
    except:
        ans = -1
        break
print(ans)

Submission status: Runtime Error

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

for i in range(1, len(t)):
    if t == s:
        ans = len(t)
    elif t[i] in s:
        ans = s.index(t[0]) + 1
        if s.index(t[i]) >= s.index(t[i-1]):
            ans += s.index(t[i]) - s.index(t[i-1])
        else:
            ans += s.index(t[i]) - s.index(t[i-1]) + len(s)
    else:
        ans = -1
        break
print(ans)

Submission status: Runtime Error

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

ans = s.index(t[0]) + 1
for i in range(1, len(t)):
    if t == s:
        ans = len(t)
    elif t[i] in s:
        if s.index(t[i]) >= s.index(t[i-1]):
            ans += s.index(t[i]) - s.index(t[i-1])
        else:
            ans += s.index(t[i]) - s.index(t[i-1]) + len(s)
    else:
        ans = -1
        break
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
data = {}
max = len(s)
for i in range(24):
    data[chr(i + ord('a'))] = max + 1
for i in range(len(s)):
    if data[s[i]] > i + 1:
        data[s[i]] = i + 1
ans = 0
pre = max
for i in range(len(t)):
    if data[t[i]] == max + 1:
        print(-1)
        exit()
    else:
        if pre < data[t[i]]:
            ans += (data[t[i]] - pre)
            pre = data[t[i]]
        else:
            ans += (max + data[t[i]] - pre)
            pre = data[t[i]]
    
print(ans)

Submission status: Runtime Error

Solution code:

# import sys
# input = sys.stdin.readline
import bisect


def ch_to_int(c):
    return ord(c) - 96


def main():
    s = input()
    t = input()
    pos = 0
    count = 0
    ch = [[] for i in range(26)]

    for i in range(len(s)):
        ch[ch_to_int(s[i])].append(i)

    for i in range(len(t)):
        c = ch_to_int(t[i])
        li = ch[c]

        if len(li) == 0:
            pos = -2
            count = 0
            break

        next_index = bisect.bisect_right(li, pos)
        if next_index >= len(li):
            next_pos = li[0]
            count += 1
            pos = next_pos
        else:
            pos = li[next_index]

    print((pos + 1) + count * len(s))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
    def find(i, ss, step):
        for j in range(step, len(ss)):
            #print(i, j, ss[j])
            if i == ss[j]:
                a = j
                return a, step
        return -1
     
     
    s = input().strip()
    #print(s)
    t = input().strip()
    #print(t)
    ss = s * 10
    #print(ss)
    step = 0
    for i in t:
        a = find(i, ss, step)
        if a == -1:
            print(-1)
            break
        else:
            #print(a)
            step = a[0] + 1
            #print(step)
    if a != -1:
        print(step)

Submission status: Runtime Error

Solution code:
    def find(i, ss, step):
        for j in range(step, len(ss)):
            #print(i, j, ss[j])
            if i == ss[j]:
                a = j
                return a, step
        return -1
     
     
    s = input().strip()
    #print(s)
    t = input().strip()
    #print(t)
    ss = s * 10
    #print(ss)
    step = 0
    for i in t:
        a = find(i, ss, step)
        if a == -1:
            print(-1)
            break
        else:
            #print(a)
            step = a[0] + 1
            #print(step)
    if a != -1:
        print(step)

Submission status: Runtime Error

Solution code:
    def find(i, ss, step):
        for j in range(step, len(ss)):
            #print(i, j, ss[j])
            if i == ss[j]:
                a = j
                return a, step
        return -1
     
     
    s = input().strip()
    #print(s)
    t = input().strip()
    #print(t)
    ss = s * 100
    #print(ss)
    step = 0
    for i in t:
        a = find(i, ss, step)
        if a == -1:
            print(-1)
            break
        else:
            #print(a)
            step = a[0] + 1
            #print(step)
    if a != -1:
        print(step)

Submission status: Runtime Error

Solution code:
from bisect import bisect

#Aのなかでlより大きな最小の値を得る.Aはソート済み

s = input()
t = input()
a = 'abcdefghijklmnopqrstuvwxyz'
d = {}
for ch in a:
  d[ch] = []
for ch,n in zip(s,range(len(s))):
  d[ch].append(n)

rep = 0
p = -1
for ch in t:
  if len(d[ch])==0:
    print("-1")
    exit()
  else:
    i = bisect(d[ch],p)
    if i!=len(d[ch]):p=d[ch][i]
    else:
      p = d[ch][0]
      rep+=1
for i in range(1,len(t)):
  if ret[i] < ret[i-1]:rep+=1

e = len(s) - ret[-1]

print(len(s)*rep - e + 1)

Submission status: Runtime Error

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

pos = [0]*len(t)
for i, c in enumerate(t):
    ind = [ii for ii, v in enumerate(s) if v == c]
    if ind[0] == -1:
        print(-1)
        exit()
    pos[i] = ind

print(pos)

lens = len(s)
last = pos[0][0]
print(last)
res = last + 1
for vals in pos[1:]:
    for i, val in enumerate(vals):
        if last < val:
            res += val - last
            break
        else:
            if i==len(vals)-1:
                res += (lens - last - 1) + (val + 1)
            else:
                continue
        last = val

print(res)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    s = str(input())
    t = str(input())
    n = len(s)-1
    m = len(t)-1
    result = 0
    point = 0
    counter = 0
    i = t[0]
    c = 1
    while c <= m:
        print(point, t[c])
        if i in s[point:]:
            x = s[point:].index(i)
            result += x + 1
            point += x + 1
            i = t[c]
            c += 1
            counter = 0
        else:
            result += n + 2 - point
            point = 0
            counter += 1
            if counter >= 2:
                print(-1)
                sys.exit()
    print(result)
if __int__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
s = input()
ss = ''.join([s,s])
t = input()
ans = 0
count = 0
dp = [0 for _ in range(len(t))]
slength = len(s)

for i in range(len(t)):
    for j in range(len(s)):
#            print('i:',i)
#            print('j:',j)
        if ss[j+(dp[i-1]%slength)]==t[i]:
            if i==0:
                dp[i] = j+1
                break
            else:
                dp[i] = dp[i-1] + j + 1
                break
        if j==len(S)-1:
            ans = -1
            break
            
if ans == -1:
    print(ans)
else:
    print(dp[len(t)-1])
    #print(dp)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_right
s = input()
t = input()
ss = set(s)
tt = set(t)
count = 0
for i in tt:
  if not i in ss:
    print(-1)
    break
else:
  dic = defaultdict(list)
  for i in range(len(s)):
    dic[s[i]] += [i+1]
  ans = 0
  for i in range(len(t)):
    x = ans%len(s)
    if dic[t[i]][-1]+1<=x:
      ans = ans - x + len(s) + dic[t[i]][0]
    else:
      ind = bisect_right(dic[t[i]], x)
      ans = ans - x + dic[t[i]][ind]
  print(ans)

Submission status: Runtime Error

Solution code:
import re
import bisect
s = input()
len_s = len(s)
t = input()

ind_dict = {i : [] for i in t}
for i, _s in enumerate(s):
    if _s in t:
        ind_dict[_s] += [i]
ind_ls = [[j.start(0) for j in re.finditer(i,s)] for i in t]

def get_least(last, s, dic):
    ls = dic[s]
    ind = bisect.bisect_right(ls, last)
    if ind >= len(ls):
        return ls[0]
    else:
        return ls[ind]

if -1 in [s.find(_t) for _t in t]:
    print(-1)
else:
    cnt = 0
    last = get_least(0, t[0], ind_dict)
    for _t in t[1:]:
        _next = get_least(last, _t, ind_dict)
        if _next < last:
            cnt += 1
        last = _next
    print(cnt * len(s) + _next + 1)

Submission status: Runtime Error

Solution code:
import re
import bisect
s = input()
len_s = len(s)
t = input()

ind_ls = [[j.start(0) for j in re.finditer(i,s)] for i in t]

def get_least(s_ind, ls):
    ind = bisect.bisect_right(ls, s_ind)
    if ind >= len(ls):
        return ls[0]
    else:
        return ls[ind]

if -1 in [s.find(_t) for _t in t]:
    print(-1)
else:
    cnt = 0
    last = get_least(0, ind_ls[0])
    for ind in ind_ls[1:]:
        _next = get_least(last, ind)
        if _next < last:
            cnt += 1
        last = _next
    print(cnt * len(s) + _next + 1)

Submission status: Runtime Error

Solution code:
import bisect

s = input()
t = input()

dic = {}

for i, c in enumerate(s):
    if c not in dic:
        dic[c] = []
        
    dic[c].append(i)

currentIndex = -1
roop = 0

for c in t:
    if c not in dic:
        print(-1)
        SystemExit(0)
    
    if currentIndex >= dic[c][-1]:
        roop += 1
        currentIndex = dic[c][0]
    else:
        index =  bisect.bisect_right(dic[c], currentIndex)
        currentIndex = dic[c][index]

result = (roop * len(s)) + currentIndex + 1
print(result)

Submission status: Runtime Error

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

slist=list(s)
tlist=list(t)
#番兵設定
slist.append("aa")
scounter=0

for tchar in tlist:
  for schar in slist:
    #sを探してもない文字だった場合
    if schar =="aa":
      scounter=-1
      break
    if tchar==schar:
      break
    scounter+=1
    
  if scounter==-1:
    break
    
print(scounter)


while endflag==False:
  if

Submission status: Runtime Error

Solution code:
n=input()
m=input()
b=len(m)
list=[]
c=0
p=n
d=0
c=0
for i in range(b):
  n=n+p
a=len(n)
for i in range(b):
  if d<0:
    continue
  d=0
  for j in range(c,a):
    if m[i]==n[j]:
      c=j+1
      list.append(0)
      break
if len(list)==b:
  print(c)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
n=input()
m=input()
b=len(m)
list=[]
c=0
p=n
d=0
c=0
for i in range(b):
  if d<0:
    continue
  a=len(n)
  d=0
  for j in range(c,a):
    if m[i]==n[j]:
      n=n+p
      c=j+1
      list.append(0)
      break
if len(list)==b:
  print(c)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
n=input()
m=input()
b=len(m)
c=0
p=n
d=0
c=0
for i in range(b):
  if d<0:
    continue
  a=len(n)
  d=0
  for j in range(c,a):
    if m[i]==n[j]:
      n=n+p
      c=j
      d=d+a-1
      break
    else:
      d=d-1
if d>0:
  print(c+1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
n=input()
m=input()
b=len(m)
c=0
p=n
d=0
c=0
for i in range(b):
  a=len(n)
  d=0
  for j in range(c,a):
    if m[i]==n[j]:
      n=n+p
      c=j+1
      d=d+a-1
      break
    else:
      d=d-1
if d>0:
  print(c+1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
n=input()
m=input()
b=len(m)
c=0
p=n
d=0
c=0
for i in range(b):
  a=len(n)
  d=0
  for j in range(c,a):
    if m[i]==n[j]:
      n=n+p
      c=j
      d=d+a-1
      break
    else:
      d=d-1
if d>0:
  print(c+1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
i = 0
cidx = -1
for sc in s:
  try:
    idx = t.index(sc)
    if idx > cidx:
      i += (idx-cidex)
    else:
      i += (len(s)-cidx-1)
      i += (idx+1)
  cidx = idx
  except ValueError:
    print(-1)
    break
print(i)

Submission status: Runtime Error

Solution code:
from sys import exit, stderr, stdin, setrecursionlimit
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return



def main():
    # まず可能かどうか
    S = str(input().rstrip())*2
    T = str(input().rstrip())
    LS = len(S)//2
    LT = len(T)
    S *= 3
    # はじめて出る位置
    char_p = dict()
    for i in range(LS):
        if not S[i] in char_p:
            char_p[S[i]] = i
    print(char_p)

    # char_pの文字が２つめのはじめて出る位置までに
    char_d = dict(zip(char_p.keys(),[[0 for __ in range(LS+char_p[c])] for c in char_p]))
    for c in char_p:
        dis = 1
        for i in range(LS+char_p[c]-1,-1,-1):
            if S[i] == c:
                char_d[c][i] = dis
                dis = 1
            else:
                char_d[c][i] = dis
                dis += 1
    # 答えの計算
    debug(char_d)
    cur = char_p[T[0]]
    for t in T[1:]:
        if t not in char_p:
            print(-1)
            exit()
        else:
            debug(t,'string')
            #それ以外なら区切りで相対的な位置を出して足す
            rel_cur = cur%LS
            debug(rel_cur,"relative_cursol")
            cur += char_d[t][rel_cur]
        debug(cur,"cur")
        # print()
    print(cur+1)






if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect
import sys
S = input()
T = input()


# sが何番目に出てくるかの辞書をついくる
s_index = {}
for i in range(len(S)):
    if S[i] in s_index:
        s_index[S[i]].append(i + 1)
    else:
        s_index[S[i]] = [i+1]


current_s_index = 0
loop_count = 0
ans = 0
for t in T:
    if not t in s_index:
        print(-1)
        sys.exit()

    if current_s_index > s_index[t][-1]:
        current_s_index = s_index[t][0]
        loop_count += 1
    else:
        index = bisect.bisect(s_index[t], current_s_index)
        current_s_index = s_index[t][index]

print(current_s_index + loop_count * len(S))

Submission status: Runtime Error

Solution code:
def search(list, query):
    # first i where list[i] > query
    # sorted
    low = 0
    high = len(list)-1
    while low <= high:
        mid = (low+high) // 2
        if list[mid] > query and (mid == 0 or index[mid-1] <= query):
            return mid
        elif list[mid] > query:
            high = mid-1
        else:
            low = mid+1
    return -1

s = input()
t = input()
s_letters = set(s)
letter_indices = {letter: [] for letter in s_letters}
for index, letter in enumerate(s): # map letter to its index in s
    letter_indices[letter].append(index)
for letter in t:
    if letter not in s_letters:
        print(-1)
        break
else:
    index = 0
    i = 1
    for letter in t:
        found_index = search(letter_indices[letter], index)
        if found_index == -1: # use next copy of s
            i += 1
            index = letter_indices[letter][0]
        else:
            index = letter_indices[letter][found_index]
    print((i-1)*len(s)+index+1)

Submission status: Runtime Error

Solution code:
def search(list, query):
    # first i where list[i] > query
    # sorted
    low = 0
    high = len(list)-1
    while low <= high:
        mid = (low+high) // 2
        if list[mid] > query and (mid == 0 or index[mid-1] <= query):
            return mid
        elif list[mid] > query:
            high = mid-1
        else:
            low = mid
    return -1

s = input()
t = input()
s_letters = set(s)
letter_indices = {letter: [] for letter in s_letters}
for index, letter in enumerate(s): # map letter to its index in s
    letter_indices[letter].append(index)
for letter in t:
    if letter not in s_letters:
        print(-1)
        break
else:
    index = 0
    i = 1
    for letter in t:
        found_index = search(letter_indices[letter], index)
        if found_index == -1: # use next copy of s
            i += 1
            index = letter_indices[letter][0]
        else:
            index = letter_indices[letter][found_index]
    print((i-1)*len(s)+index+1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import bisect
s = input()
t = input()



count = 0
s_len = len(s)
s_list = np.zeros(len(s))
t_list = []*len(t)
indexes = []

for i in range(26):
  
  indexes.append([j for j, x in enumerate(s) if x == chr(i + ord('a')) ])
  

for i,k in enumerate(t):

  index = indexes[ord(k)-97]
  
  if len(indexes) == 0:
    print(-1)
    sys.exit(0)
  else:
    t_list.insert(i,index)
    


pre = -1
for i in range(len(t)):
  
  #high = [j  for j in t_list[i] if j > pre]
  high = bisect.bisect_left(t_list[i], pre) 

  if high >= len(t_list[i]):
    
    count += s_len - pre  + t_list[i][0]
    pre = t_list[i][0] 
  else:
    
    count += t_list[i][high] - pre 
    pre = t_list[i][high]

print(count)

Submission status: Runtime Error

Solution code:
def get_answer(input_list):
    so = input_list[0]
    s = so[0]
    s_index = 1
    s_len = len(so)
    t = input_list[1]
    ret = -1

    """
    """
    for i in range(1000):
        find_flag = True
        ss = s
        for tt in t:
            ii = ss.find(tt)
            if ii < 0:
                find_flag = False
                break
            ss = ss[ii + 1:]
        if find_flag:
            ret = len(s)
            break
        s += so[s_index]
        s_index = (s_index + 1) % s_len

    return ret


if __name__ == "__main__":
    input_list = []
    while True:
        try:
            input1 = input()
            if not input1:
                break
            if len(input1) == 0:
                break
            input_list.append(input1)
        except EOFError:
            break
    print(get_answer(input_list))

Submission status: Runtime Error

Solution code:
def solve_e(n, a_list):
    days = 0
    ind_list = [0] * n
    match_count = 0
    queue = list(range(n))
    stack = dict()
    while len(queue) > 0:
        days += 1
        new_queue = []
        for p in queue:
            if ind_list[p] < n - 1:
                q = a_list[p][ind_list[p]] - 1
                k = str(min(p, q)) + "_" + str(max(p, q))
                if k in stack.keys():
                    ind_list[p] += 1
                    ind_list[q] += 1
                    # print(days, p, q)
                    new_queue.append(p)
                    new_queue.append(q)
                    match_count += 1
                else:
                    stack[k] = 1
        queue = new_queue
    if match_count == n * (n - 1) // 2:
        return days - 1
    else:
        return -1


def test():
    n = 1000
    a_list = []
    for i in range(N):
        a_list.append(list(range(1, i + 1)) + list(range(i + 2, n + 1)))
    print(solve_e(n, a_list))


def main():
    n = int(input())
    a_list = []
    for _ in range(n):
        a_list.append(list(map(int, input().split())))
    print(solve_e(n, a_list))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
s = input()
t = input()
cnt = 0
last = 0
b = [{} for i in range(len(s))]
b[-1][s[-1]] = len(s) - 1
for i in range(len(s)-1)[::-1]:
    b[i] = b[i + 1].copy()
    b[i][s[i]] = i

for i in t:
    if i in b[last]:
        last = b[last][i]
    else:
        if last == 0:
            print(-1)
            exit()
        else:
            last = b[0][i]
            cnt +=1
print(cnt*len(s) + last + 1)

Submission status: Runtime Error

Solution code:
seq = input()
sub = input()

n = len(seq)
m = len(sub)

sums = 0
pos  = -1

for i in range(m):
  char = sub[i]
  add  = 0
  pos += 1
  add += 1
  while(char != seq[pos]):
    add +=1
    pos = (pos + 1) % n
    if add > n :
      print(-1)
      exit()
  sums += add 

print(sums)

Submission status: Runtime Error

Solution code:
import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]

for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for i in range(26):
  if chr(97+1)
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

for letter in t:
  if s.find(letter) == -1:
    print(-1)
    sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_right

s = input()
t = input()

t_set = set(t)

if len(t_set -set(s)) != 0:
    print(-1)
    sys.exit()

s_len = len(s)
def index_list(char):
    word = s
    ret = list()
    sum = 0
    try:
        while True:
            index = word.index(char)+ 1        
            sum+=index
            ret.append(sum)
            word = word[index:]
    except:
        if sum == 0:
            ret.append(-1)
    return ret

alpha_dict = dict()
for char in t_set:
    alpha_dict[char] = index_list(char)

index_old = 0
n_s = 0
for char in t:
    index = alpha_dict[char]
    
    flg = True
    
    if index[-1] < index_old:
        pass
    else:
        index_old = index[bisect_right(index, index_old)]
        flg =False
    if flg:
        index_old = index[0]
        n_s += 1
        
print(n_s*s_len + index_old)

Submission status: Runtime Error

Solution code:
import sys

s = str(input())
t = str(input())

st = tuple(s)
tt = tuple(t)

if not tt <= st:
  print('-1')
  sys.exit()

cnt = 0
f = int(len(st)/2)

for i in tt:
  try:
    f = st.index(i,f+1,len(st))
  except ValueError:
    f = st.index(i,0,f+1)
    cnt += 1

if cnt:
  if not f == len(st):
    print(len(st) * cnt + f + 1)
  else: 
    print(len(st) * (cnt + 1)+ f + 1)
else:
  print(f + 1)

Submission status: Runtime Error

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

st = tuple(s)
tt = tuple(t)
sg = set(st)
tg = set(tt)

if not tg & sg:
  print('-1')

sb = st[int(len(st)/2):]
sf = st[:int(len(st)/2)]
cnt = 0
f = int(len(st)/2)
sta = st

for i in tt:
    try:
      f = sta.index(i,f,len(st))
    except ValueError:
      f = sta.index(i,0,f)
      cnt += 1
      sta += sta

print(len(st) * cnt + f + 1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
c = 0
pre = 0
rep = 0
dict = {word:[] for word in 'abcdefghijklmnopqrstuvwxyz'}
for i, w in enumerate(s):
    dict[w].append(i+1)
for n in t:
    if len(dict[n]) < 1:
        c = -1
        break
    if pre > dict[n][0]:
        rep += 1
    pre = dict[n][0]
    if len(dict[n]) > 1:
        num = dict[n].pop(0)
        dict[n].append(num)
    print('pre: {}'.format(pre))
    print('rep: {}'.format(rep))
    print('dict[n]: {}'.format(dict[n]))

if c == -1:
    print(-1)
else:
    print(len(s) * rep + dict[t[-1]][-1])

Submission status: Runtime Error

Solution code:
Copy
Copy
from bisect import bisect_left
 
ALPHABET = "abcdefghijklmnopqrstuvwxyz"
 
 
def main(s, t):
    positions = {char: [] for char in ALPHABET}
    for i, char in enumerate(s):
        positions[char].append(i)
 
    current = 0
    answer = 0
    for char in t:
        pos_num = len(positions[char])
        if pos_num < 1:
            return -1
        idx = bisect_left(positions[char], current)
        if idx < pos_num:
            current = positions[char][idx] + 1
        else:
            answer += len(s)
            idx = bisect_left(positions[char], 0)
            current = positions[char][idx] + 1
 
    answer += current
    return answer
 
 
s = input()
t = input()
print(main(s, t))