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

s = input()
t = input()

abc = "abcdefghijklmnopgrstuvwxyz"

p = {}

for i in abc:
  p[i] = []
for i in range(len(s)):
  p[s[i]].append(i)
for i in abc:
  p[i].sort()

l = 0
c = 0

flg = True

for i in t:
  tar = p[i]
  if(len(tar) == 0):
    flg = False
    break
  index = bisect.bisect_left(tar,c)
  if(index == len(tar)):
    index = 0
    l += 1
  c = tar[index]


if(flg):
  print(l*len(s) + c + 1)

else:
  print("-1")

Submission status: Runtime Error

Solution code:
s,t=([chr(c)-chr('a') for c in input()]for _ in'xx')
if set(t)-set(s):
  print(-1)
else:
  u=s+s
  nxt = [None for _ in range(len(u)+1)]
  nxt[len(u)]=[0 for _ in range(26)]
  for i in range(len(u)-1,-1,-1):
    nxt[i] = [v+1 for v in nxt[i+1]]
    nxt[i][u[i]]=0
  p = 0
  for c in t:
    p += nxt[p%len(s)][c]+1
  print(p)

Submission status: Runtime Error

Solution code:
import bisect

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

# 辞書を作る
dictionary = {}

tt = t[:]
ss = s * 2

i = 0
while len(ss):
    _s = ss.pop(0)
    if _s not in dictionary:
        dictionary[_s] = [i]
    else:
        dictionary[_s].append(i)
    i += 1

result = 0
before = 0
sLen = len(s)
while len(t) > 0:
    _t = t.pop(0)
    next = dictionary[_t][bisect.bisect_left(dictionary[_t], before)] + 1
    result += next - before
    before = next
    if next >= sLen:
        before -= sLen

print(result)

Submission status: Runtime Error

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

def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        print(countMakeTbyS(s, t))
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    for i in range(len(t)):
        if t[i] in s:
            continue
        else:
            ans = False
            break
    return ans

def countMakeTbyS(s, t):
    count = 1
    p_t = 0
    while(p_t < len(t)):
        for i in range(len(s)):
            if t[p_t] == s[i]:
                p_t += 1
        count += 1
    return count


main()

Submission status: Runtime Error

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

def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    for i in range(len(t)):
        if t[i] in s:
            continue
        else:
            ans = False
            break
    return ans

def countMakeTbyS(s, t):
    count = 1
    p_t = 0
    while(p_t < len(t)):
        for i in range(len(s)):
            if t[p_t] == s[i]:
                p_t += 1
        count += 1
    return count


main()

Submission status: Runtime Error

Solution code:
s = input()
t = input()
l = 10**5
S = s*l

a = 0
flag = True
for i in range(len(t)):
    if t[i] in S:
        a = S.index(t[i], a)+1
    else:
        flag = False
        break
        
if flag:
    print(a)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
l = 10**5
S = s*l
a = 0
flag = True
for i in range(len(t)):
    if t[i] in S[a:]:
        a += S[a:].index(t[i])+1
    else:
        flag = False
        break
        
if flag:
    print(a)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ss = s*len(t)
pos = 0
try:
    for c in t:
        pos += ss[pos:].index(c)
except:
    pos = -2
print(pos+1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ss = s*len(t)
pos = 0
for c in t:
    pos += ss[pos:].index(c)
print(pos+1)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
alp=string.ascii_lowercase
d_al=dict([(i,j) for j,i in enumerate(alp)])

s=[d_al[i] for i in input()]
t=[d_al[i] for i in input()]
Ss=set(s)
St=set(t)
ns=len(s)
nt=len(t)
ss=s*2
#print(ss)

g=[{} for _ in range(ns)]
pos=[-1]*26
for i in range(ns*2)[::-1]:
    for j in Ss:
        if i<ns:
            g[i][j]=pos[j]-i
    pos[ss[i]]=i
#for i in range(len(g)):
#    print(g[i])

if len(St-Ss)!=0:
    ans=-1
else:
    cur=0
    ans=1+g[-1][t[0]]
    cur+=g[-1][t[0]]
    for i in range(1,nt):
        #print(cur,s[cur],'tg=',t[i],g[cur][t[i]])
        ans+=g[cur][t[i]]
        cur+=g[cur][t[i]]
        cur%=ns
print(ans)#,loop,has)

Submission status: Runtime Error

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

p = 0
roop = 0
dic = [['' for i in range(len(s))] for j in range(26)]

for i in range(len(t)):
    dis = 0
    if dic[ord(t[i])-97][p] == '':
        for j in range(p,len(s)):
            if t[i] == s[j]:
                for k in range(p,j+1):
                    dic[ord(t[i])-97][k] = j
                dis = 1
                break
        if dis == 0:
            for j in range(0,p):
                if t[i] == s[j]:
                    for k in range(p,len(s)):
                        dic[ord(t[i])-97][k] = j
                    for k in range(0,j+1):
                        dic[ord(t[i])-97][k] = j
                    dis = 1
                    break
        if dis == 0:
            dis = 2
            break
    if p > dic[ord(t[i])-97][p]:
        roop += 1
    p = dic[ord(t[i])-97][p] + 1

if dis == 2:
    print(-1)
else:
    print(roop*len(s)+p)

Submission status: Runtime Error

Solution code:
#N, M = map(int, input().split())
#List_ab = [list(map(int, input().split())) for i in range(N)]
s = input()
t = input()
  
p = 0
roop = 0
dic = [['' for i in range(len(s))] for j in range(26)]

for i in range(len(t)):
    dis = 0
    if dic[ord(t[i])-97][p] == '':
        for j in range(p,len(s)):
            if t[i] == s[j]:
                for k in range(p,j+1):
                    dic[ord(t[i])-97][k] = j
                dis = 1
                break
        if dis == 0:
            for j in range(0,p):
                if t[i] == s[j]:
                    for k in range(p,len(s)):
                        dic[ord(t[i])-97][k] = j
                    for k in range(0,j+1):
                        dic[ord(t[i])-97][k] = j
                    dis = 1
                    break
        if dis == 0:
            dis = 2
            break
    if p > dic[ord(t[i])-97][p]:
        roop += 1
    p = dic[ord(t[i])-97][p] + 1
    
print(roop*len(s)+p)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

s=input()
t=input()
s=list(s)
t=list(t)
Ss=set(s)
St=set(t)
n=len(s)

alp=string.ascii_lowercase
di=dict([(i,j) for j,i in enumerate(alp)])
#print(di)
g=[{} for _ in range(n)]
fp=[-1 for i in range(26)]
lp=[-1 for i in range(26)]

for i,c in enumerate(s):
    fp[di[c]]=i
    for next_c in [di[l] for l in Ss]:
        g[i][next_c]=(min(g[i][next_c],fp[next_c]),1)

for i in range(n)[::-1]:
    lp[di[s[i]]]=i
    for next_c in [di[l] for l in Ss]:
        if lp[next_c]!=-1:
            g[i][next_c]=(lp[next_c],0)

m=[[] for i in range(n)]


#print(Ss,St,St-Ss)
if len(St-Ss)!=0:
    ans=-1
else:
    loop=0
    has=0
    st=di[t[0]]
    loop+=g[0][st][1]
    i_n=g[0][st][0]
    has=i_n
    for i in range(1,len(t)):
        ch=di[t[i]]
        loop+=g[i_n][ch][1]
        i_n=g[i_n][ch][0]
        has=g[i_n][ch][0]
        #print(loop,has,i_n,g[i_n][ch])
    ans=loop*n+has+1
print(ans)#,loop,has)
#print([[i,di[i]] for i in s])
'''
for i in g:
    print(sorted(list(i.items()),key=lambda x:x[0]))
'''

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()
t = input()

ss = s * 2

N = len(s)

tN = len(t)


def alpha_index(c):
    return ord(c) - ord("a")


# 次の特定の文字が何文字先にあるか
str_save = np.full((N * 2, 26), -1)

index = 0
loopcnt = 0

for c in t:
    if str_save[index, alpha_index(c)] != -1:
        index = str_save[index, alpha_index(c)]
    else:
        index = ss.find(c, index % N)
        str_save[index % N, alpha_index(c)] = index
        if index == -1:
            print(-1)
            exit()

    index += 1
    if index >= N:
        loopcnt += 1
        index -= N

print (loopcnt * N + index)

Submission status: Runtime Error

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

for i in range(len(t)):
  if not t[i] in s:
    print(-1)
    break
else:
  j = 0
  for i in rane(len(t)):
    j = s[j:].find(t[i])
    if j == -1:
      counter += 1
      j = s.find(t[i])
  print(counter * len(s) + j + 1)

Submission status: Runtime Error

Solution code:
import bisect

s=input()
t=input()

condition=0

index=list()
for a in range(len(t)):
 index.append([i for i, x in enumerate(s) if x == t[a]])

for i in range(len(t)):
 if index[i]==[]:
   condition=1
   break

if condition==1:
  print(-1)
else:
  #print(index)
  b=index[0][0]
  j=1
  loop=0
  if len(t)==1:
    print(b+1)
  else:
   while j <= len(t)-1:
     c=bisect.bisect_left(index[j],b)
     #print(j,index[j],b,c,loop)
     if  c < index[j][len(index[j])-1]:
        b=index[j][c]
        #print(j,b,loop)
        j=j+1
        if j==len(t):
          print(b+loop+1)
          break
     else:
        loop=loop+len(s)
        b=index[j][0]
        j=j+1
        if j==len(t):
          print(b+loop+1)
          break
        if loop == len(s)*(10**100):
           print(-1)
           break

Submission status: Runtime Error

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

idx = -1
if set(t) <= set(s):
    for i in t:
        idx = s.find(i, idx+1)
        s += s
    print(idx+1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
 
strings = s*len(t)

idx = -1
if set(t) <= set(s):
    for i in t:
        idx = strings.find(i, idx+1)
    print(idx+1)
else:
    print("-1")

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ss = list(s)*len(t)
lt = list(t)

if set(list(t)).issubset(set(list(s))):
    for i in range(len(s)*len(t)):
        if ss[i] == lt[0]:
            lt.pop(0)
            if len(lt) == 0:
                ans = i+1
                break
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
cnt = 0
for i in range(t):
  for j in range(s):
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    sletters = set()
    for i in s:
        sletters.add(i)

    for i in t:
        if i not in sletters:
            print(-1)
            return

    s = s*len(t)
    i = 0
    j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
            j += 1
        else:
            i += 1

    print(i)


main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from re import finditer
from bisect import bisect_left

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


    str_dict = defaultdict(list)



    for char in set(t):
        m = finditer(char, s)
        if not m:
            return '-1'
        for j in m:
            str_dict[char] += [j.start() + 1]



    ans = 0
    for i in t:
        remain = ans % len(s)
        array = str_dict[i]
        str_ind = bisect_left(array, remain)
        if str_ind != len(array):
            ans += array[str_ind] - remain
        else:
            ans += len(s) - remain + array[0]
    return ans


print(main())

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()
t = input()

ss = s * 2

N = len(s)

tN = len(t)


def alpha_index(c):
    return ord(c) - ord("a")


# 次の特定の文字が何文字先にあるか
str_save = np.full((N * 2, 26), -1)

index = -1
loopcnt = 0

for c in t:
    if str_save[index+1, alpha_index(c)] != -1:
        index = str_save[index+1, alpha_index(c)]
    else:
        index = ss.find(c, (index+1) % N)
        str_save[(index+1) % N, alpha_index(c)] = index
        if index == -1:
            print(-1)
            exit()

    if index >= N:
        loopcnt += 1
        index -= N
    index += 1

print (loopcnt * N + index + 1)

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()
t = input()

ss = s * 2

N = len(s)

tN = len(t)


def alpha_index(c):
    return ord(c) - ord("a")


# 次の特定の文字が何文字先にあるか
str_save = np.full((N * 2, 26), -1)

index = -1
loopcnt = 0

for c in t:
    if str_save[index+1, alpha_index(c)] != -1:
        index = str_save[index+1, alpha_index(c)]
    else:
        index = ss.find(c, (index+1) % N)
        str_save[(index+1) % N, alpha_index(c)] = index
        if index == -1:
            print(-1)
            exit()

    if index >= N:
        loopcnt += 1
        index -= N

print (loopcnt * N + index + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from re import finditer
from bisect import bisect_left

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


    str_dict = defaultdict(list)



    for char in set(t):
        for j in finditer(char, s):
            str_dict[char] += [j.start() + 1]



    ans = 0
    for i in t:
        remain = ans % len(s)
        array = str_dict[i]
        str_ind = bisect_left(array, remain)
        if str_ind != len(array):
            ans += array[str_ind] - remain
        else:
            ans += len(s) - remain + array[0]
    return ans


print(main())

Submission status: Runtime Error

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

# 10倍速いらしい
input = sys.stdin.readline

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

S = input().rstrip()
T = input().rstrip()

sn = len(S)
M = [dict() for _ in range(sn)]
for i, s in enumerate(S):
    for j in range(sn):
        M[(i - j + sn) % sn][s] = min(M[(i - j + sn) % sn].get(s, INF), j)
    for j in range(sn):
        if M[(i - j + sn) % sn][s] == 0:
            M[(i - j + sn) % sn][s] = M[(i - j + sn + 1) % sn][s] + 1


ans = 0
idx = sn - 1
for t in T:
    if M[idx].get(t, INF) == INF:
        print(-1)
        sys.exit()
    ans += M[idx][t]
    idx = (idx + M[idx][t]) % sn

print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
l = len(s)
s2 = s*2
if not set(s) => set(t) :
    print(-1)
else :
    lowers = sorted(set(t))
    ldict = {v:i for i, v in enumerate(lowers)}
    dist = [[0 for j in range(l)] for i in range(len(lowers))]
    for j in range(l) :
        for i, b in enumerate(lowers) :
            for k, c in enumerate(s2[j+1:]) :
                if c == b :
                    dist[i][j] = 1+k
                    break
    ans = 0
    last = -1
    for c in t :
        diff = dist[ldict[c]][last]
        ans += diff
        last = (last+diff)%l
    print(ans)

Submission status: Runtime Error

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

lst = [[] for _ in range(30)]
ch = 'abcdefghijklmnopqrstuvwxyz'
for k, i in enumerate(s+s):
    lst[ch.find(i)].append(k)

len_s = len(s)

count = 0
index = -1
for i in t:
    if lst[ch.find(i)] == []:
        print(-1)
        break
    next_index = lst[ch.find(i)][bisect.bisect_right(lst[ch.find(i)], index)]
    count += next_index - index
    if next_index >= len_s:
        next_index -= len_s
    index = next_index
else:
    print(count)

Submission status: Runtime Error

Solution code:
s=input()
t=input()
l=list()
for _ in list(t):
  if [i for i,x in enumerate(list(s)) if x==_] != list():
    l.append([i for i,x in enumerate(list(s)) if x==_])
  else:
    print(-1)
    exit()
if len(t)==1:
  print(s.index(t)+1)
  exit()
ed=l[0][0]
cd=0
for i in range(len(t))[1:-1]:
  k=l[i]
  if max(k+[ed])==ed :
    cd+=1
    ed=k[0]
  else:
    ex=sorted(k+[ed])
    exex=ex.index()
    ed=k[exex]
k=l[len(t)-1]
if max(k+[ed])==ed :
  print((cd+1)*len(s)+min(k)+1)
else:
  ex=sorted(k+[ed])
  exex=ex.index(ed)
  ed=k[exex]
  print((cd)*len(s)+ed+1)

Submission status: Runtime Error

Solution code:
s=input()
t=input()
l=list()
for _ in list(t):
  if [i for i,x in enumerate(list(s)) if x==_] != list():
    l.append([i for i,x in enumerate(list(s)) if x==_])
  else:
    print(-1)
    exit()
if len(t)==1:
  print(s.index(t)+1)
  exit()
ed=l[0][0]
for i in range(len(t))[1:-1]:
  k=l[i]
  if max(k+[ed])==ed :
    cd+=1
    ed=k[0]
  else:
    ex=sorted(k+[ed])
    exex=ex.index()
    ed=k[exex]
k=l[len(t)-1]
if max(k+[ed])==ed :
  print((cd+1)*len(s)+min(k)+1)
else:
  ex=sorted(k+[ed])
  exex=ex.index(ed)
  ed=k[exex]
  print((cd)*len(s)+ed+1)

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    ans = 0
    for c in t:
        index = s.index(c)
        if index == ValueError:
            print(-1)
            return
        ans += index+1
        s = s[index+1:] + s[:index+1]
    print(ans)
 
main()

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    ans = 0
    for c in t:
        index = s.index(c)
        if index == -1:
            print(-1)
            return
        ans += index+1
        s = s[index+1:] + s[:index+1]
    print(ans)
 
main()

Submission status: Runtime Error

Solution code:

N,Q  = map(int, input().split())

# 木
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

## クエリを覚えておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

# 和をとっていく
ans = [0]*N
ans[0] = scores[0]
used = [False] * N

"""
dfs TLEする。なんで
"""
# import sys
# sys.setrecursionlimit(100000)
# def dfs(G, v):
#    # vを訪問済みにする
#    used[v] = True
#    #グラフ中の次のVについて
#    for next_v in G[v]:
#        if used[next_v]: continue
#        ans[next_v] = ans[v] + scores[next_v]
#        dfs(G, next_v)
# dfs(G,0)
# print(*ans)

# 木をBFSをする
from collections import deque
used = [False] * N
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    v = q.popleft()
    Vs = G[v]
    for next_v in Vs: 
        if not used[next_v]:
            q.append(next_v)
            ans[next_v] = ans[v] + scores[next_v]
            used[next_v] = True
print(*ans)

Submission status: Runtime Error

Solution code:
import heapq
al = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4, "f": 5,
      "g": 6, "h": 7, "i": 8, "j": 9, "k": 10, "l": 11,
      "m": 12, "n": 13, "o": 14, "p": 15, "q": 16, "r": 17,
      "s": 18, "t": 19, "u": 20, "v": 21, "w": 22, "x": 23,
      "y": 24, "z": 25}
als = [[] for _ in range(26)]
for i in als:
    heapq.heapify(i)
s = list(input())
ls = len(s)
for i, v in enumerate(s):
    heapq.heappush(als[al[v]], i)
t = list(input())
last_no = 0
for i, v in enumerate(t):
    print(als, v)
    if len(als[al[v]]) != 0:
        while True:
            p = heapq.heappop(als[al[v]])
            heapq.heappush(als[al[v]], p + ls)
            if p > last_no:
                last_no = p
                break
    else:
        print(-1)
        exit()
print(last_no + 1)

Submission status: Runtime Error

Solution code:
import sys,heapq,math,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  #resource.setrlimit(RLIMIT_STACK, (128*1024*1024,hard))

alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' ]
hs = {}
for c in alpha:
    hs[c] = {}
    for c2 in alpha:
        hs[c][c2] = {}

s = input().strip()
t = input().strip()

prev = {}
for i in range(len(s)*2):
    ii = i%len(s)
    for ch in prev:
        if prev[ch]<len(s) and prev[ch] not in hs[ch][s[ii]]:
            hs[ch][s[ii]][prev[ch]] = ii
    prev[s[ii]] = i

prev = -1
for i in range(len(s)):
    if s[i]==t[0]:
        prev = i
        break
if prev == -1:
    print(-1)
    exit()

x = 0
for i in range(1,len(t)):
    if len(hs[t[i-1]][t[i]])==0:
        print(-1)
        exit()
    j = hs[t[i-1]][t[i]][prev]
    if j<prev:
        x += 1
    prev = j

print(x*len(s)+prev+1)

Submission status: Runtime Error

Solution code:
s=input()
t=input()
if len(t)==1:
  try:
    print(s.index(t)+1)
  except ValueError:
    print(-1)
    exit()
  l=list()
  for _ in list(t):
    l.append([i for i,x in enumerate(list(s)) if x==_]) if [i for i,x in enumerate(list(s)) if x==_]!=[] else print(-1) and exit()
  ed=l[0][0]
  for i in range(len(t))[1:-1]:
    k=l[i]
    if max(k+[ed])==ed :
      cd+=1
    else:
      ex=list(sorted(k+[ed])).index(ed)
      ed=k[ex]
k=l[len(t)-1]
if max(k+[ed])==ed :
  print((cd+1)*len(s)+min(k)+1)
else:
  ex=list(sorted(k+[ed])).index(ed)
  ed=k[ex]
  print((cd)*len(s)+ed+1)

Submission status: Runtime Error

Solution code:
s=input()
t=input()
if len(t)==1:
  try:
    print(s.index(t)+1)
  except ValueError:
    print(-1)
    exit()
else:
  cd=0
  def cdcd():
    print(-1)
    exit()


  l=list()
  for _ in list(t):
    l.append([i for i,x in enumerate(list(s)) if x==_]) if [i for i,x in enumerate(list(s)) if x==_]!=[] else cdcd
  ed=l[0][0]
  for i in range(len(t))[1:-1]:
    k=l[i]
    if max(k+[ed])==ed :
      cd+=1
    else:
      ex=list(sorted(k+[ed])).index(ed)
      ed=k[ex]
k=l[len(t)-1]
if max(k+[ed])==ed :
  print((cd+1)*len(s)+min(k)+1)
else:
  ex=list(sorted(k+[ed])).index(ed)
  ed=k[ex]
  print((cd)*len(s)+ed+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    T = str(input().strip())

    if not set(T) <= set(S):
        return -1

    n = len(S)
    d = defaultdict(list)
    for i, s in enumerate(S, start=1):
        d[s].append(i)

    cnt = 0
    pos = 0
    for t in T:
        if pos >= d[-1]:
            cnt += 1
            pos = d[t][0]
        else:
            left = 0
            right = len(d[t])
            while left < right:
                mid = (left + right) // 2
                np = d[t][mid]
                if np <= pos:
                    left = mid + 1
                else:
                    right = mid
            pos = d[t][left]

    return n * cnt + pos


if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
import bisect
s=input()
t=input()
dic={}
for v in s:
    dic[v]=True

for u in s:
    if not dic[u]:
        print(-1)
        exit()

nex={}
for i, v in enumerate(s+s):
    if not v in nex:
        nex[v]=[i]
    else:
        nex[v].append(i)
#print(s)
#print(t)
#print(nex)
sl=len(s)
tl=len(t)
def func(st, tn, su):
    #print(st, tn, su)
    if tn == tl:
        return su 
    ind=bisect.bisect_left(nex[t[tn]] ,st)
    nm=(nex[t[tn]][ind]-st)
    return func((st+nm)%sl, tn+1, su+nm)


res=func(-1, 0, 0)

print(res)

Submission status: Runtime Error

Solution code:
abc = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
s = input()
x = [0 for i in range(26)] for j in range(len(s))]
for k in range(2):
    for i in range(len(s)-1,-1,-1):
        if i == 0:
            ib = len(s)-1
        else:
            ib = i-1
        for j in range(26):
            if j == ord(s[i])-97:
                x[ib][j] = i
            else:
                x[ib][j] = x[i][j]
t = input()
i = len(s)-1
count = 0
for j in range(len(t)):
    nxt = x[i][ord(t[j])-97]
    if nxt == 0:
        print(-1)
        exit()
    elif nxt <= i:
        count += 1
        i = nxt
    else:
        i = nxt
print(len(s)*(count-1)+i+1)

Submission status: Runtime Error

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

ls = len(s)
lt = len(t)
st = set(t)
flg = 0

for i in st:
  if s.count(i)==0:
    flg = -1
    print(flg)
    exit()

i = 0
j = 0
s = s*100000

while i<lt:
  if t[i]==s[j]:
    i+=1
  j+=1
  
print(j)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from bisect import bisect_left as bl
s = input()
t = input()
ind = dd(list)
res = 0
for i in range(len(s)):
  ind[s[i]].append(i)
#print(ind)
for i in range(len(t)):
  if len(ind[t[i]]) == 0:
    print(-1)
    exit(0)
  temp = bl(ind[t[i]], res % len(s))
  #print(temp, res, t[i])
  if res % len(s) == ind[t[i]][temp]:
    temp += 1
  if temp == len(ind[t[i]]):
    res += (len(s) - res % len(s)) + ind[t[i]][0]
  else:
    res += ind[t[i]][temp] - res % len(s)
print(res + 1)

Submission status: Runtime Error

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

ls = len(s)
lt = len(t)
st = set(t)
flg = 0

for i in st:
  if s.count(i)==0:
    flg = -1
    print(flg)
    exit()

i = 0
j = 0
s = s*300000

while i<lt:
  if t[i]==s[j]:
    i+=1
  j+=1
  
print(j)

Submission status: Runtime Error

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

next_map = sorted(zip(s*2,range(N*2)))
br = bisect.bisect_right
ans = 0
i = 0
for c in t:
    map_idx = br(next_map,(c,i))
    if map_idx == N*2:
        ans = -2/0
        break
    a,j = next_map[map_idx]
    if a != c :
        ans = -2
        break
    ans += j - i
    i = j%N
ans += 1
print(ans)

Submission status: Runtime Error

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

next_map = sorted(zip(s*2,range(N*2)))
br = bisect.bisect_right
ans = 0
i = 0
for c in t:
    map_idx = br(next_map,(c,i))
    if map_idx == N*2:
        ans = -2
        break
    a,j = next_map[map_idx]
    if a != c :
        ans = -2/0
        break
    ans += j - i
    i = j%N
ans += 1
print(ans)

Submission status: Runtime Error

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
x = []
inde = s.index(t[0])
x.append(inde+1)
if m > 1:
    x.append(n-inde-1)
c = [[] for i in range(26)]
for i in range(n):
    c[alpha.index(s[i])].append(i)
for i in range(1,m):
    inde = s.index(t[i])
    for j in c[s.index(t[i-1])]:
        if inde < j:
            preinde = j
            break
    else:
        preinde = s.index(t[i-1])
    if inde > preinde:
        x.pop()
        x.append(inde-preinde)
        if i != m-1:
            x.append(n-inde-1)
    else:
        x.append(inde+1)
        if i != m-1:
            x.append(n-inde-1)
print(sum(x))

Submission status: Runtime Error

Solution code:
import sys
def SI(): return sys.stdin.readline().strip()

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

    import collections
    didx = collections.defaultdict(int)
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)


    # keys = d.keys()
    # for c in set(t):
    #     if c not in keys:
    #         print(-1)
    #         return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

Submission status: Runtime Error

Solution code:
import sys
s=input()
t=input()
a=[]
answer=0
s*=len(t)
for i in range(len(t)):
  if t[i] in s:
    a.append(s.index(t[i]))
    sc=''
    sc+='A'*(a[i]+1)
    sc+=s[a[i]+1:]
    s=sc
  else:
    print(-1)
    sys.exit()
print(a[-1]+1)

Submission status: Runtime Error

Solution code:
import sys
s=input()
t=input()
a=[]
answer=0
s*=len(t)
for i in range(len(t)):
  if t[i] in s:
    a.append(s.index(t[i]))
    sc=''
    for j in range(a[i]+1):
      sc+='A'
    sc+=s[a[i]+1:]
    s=sc
  else:
    print(-1)
    sys.exit()
print(a[-1]+1)

Submission status: Runtime Error

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

strings = s*len(t)

for str in t:
    if str not in s:
        print("-1")
        break
    strings.strip(str)

n = strings.index(t)
num = len(s)*(n-1)+(s.index(t[-1]))+1

print(num)