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: Accepted

Solution code:
#!/usr/bin/env python3
import sys, bisect
sys.setrecursionlimit(300000)


def solve(s: str, t: str):
    N = 26
    pos = [[] for _ in range(N)]
    for i, c in enumerate(s):
        pos[ord(c) - ord('a')].append(i)

    tmp = 0
    num = 0
    for C in t:
        c = ord(C) - ord('a')
        le = len(pos[c])
        if le < 1:
            print(-1)
            return
        idx = bisect.bisect_left(pos[c], tmp)
        #print(pos[c], C, idx)
        if idx < le:
            tmp = pos[c][idx] + 1
        else:
            idx = bisect.bisect_left(pos[c], 0)
            tmp = pos[c][idx] + 1
            num += 1
        #print(C, num, tmp)
    ret = num * len(s) + tmp
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right
s = input()
t = input()
n = len(s)
m = len(t)

# 存在確認
aa = set(s)
for i in t:
    if i not in aa:
        print(-1)
        exit()

d = defaultdict(list)

for i in range(n):
    d[s[i]].append(i)

pos = -1
cnt = 0
for c in t:
    j = bisect_right(d[c], pos)
    if j < len(d[c]):
        pos = d[c][j]
    else:
        cnt += 1
        pos = d[c][0]
print(cnt*n + pos+1)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from collections import defaultdict

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

L = len(s)
M = len(t)

ss = s * 2

ind_dict = defaultdict(list)
for i in range(2 * L):
    ind_dict[ss[i]].append(i)


def query_str(c, ind):
    if len(ind_dict[c]) == 0:
        return -1
    else:
        r = bisect_right(ind_dict[c], ind)
        return ind_dict[c][r]


res_total = 0
res = -1
for i in range(M):
    res = query_str(t[i], res)
    if res == -1:
        res_total = 0
        break
    if res >= L:
        res -= L
        res_total += L

if res == -1:
    print(-1)
else:
    print(res_total + res + 1)

Submission status: Accepted

Solution code:
import collections
from bisect import bisect_right
d=collections.defaultdict(list)
s=input()
t=input()
for i,S in enumerate(s,1):
    d[S].append(i)
k=0
ans=0
for i in t:
    l=d[i]
    if len(l)==0:
        print(-1)
        quit()
    if l[-1]<=ans:
        ans=l[0]
        k+=1
    else:
        ans=l[bisect_right(l,ans)]
print(len(s)*k+ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()

n = len(s)

mp = [[] for _ in range(26)]
s += s
for i in range(len(s)):
    mp[ord(s[i]) - ord('a')].append(i)

ans = 0
now = -1
for i in range(len(t)):
    a = ord(t[i]) - ord('a')
    if len(mp[a]) == 0:
        print(-1)
        exit()

    nxt = bisect_right(mp[a], now)
    nxt = mp[a][nxt]
    ans += nxt - now
    if nxt > n:
        now = nxt - n
    else:
        now = nxt
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
s = input()
t = input()
n_s = len(s)
n_t = len(t)

for i in range(n_t):
    if t[i] not in s:
        print(-1)
        exit()

idx = [[] for _ in range(26)]
#print(ord("a"))
#print(ord("z"))

def a_idx(a):
    idx = ord(a)
    idx -= 97
    return idx


for i in range(n_s):
    idx[a_idx(s[i])].append(i)

t_junnban = []
for i in range(n_t):
    t_junnban.append(idx[a_idx(t[i])])
print(t_junnban)

now = 0
ans = 0
for i in range(n_t):
    ni = bisect_right(t_junnban[i], now)
    if ni >= len(t_junnban[i]):
        now = 0
        ans += n_s
        ni = bisect_right(t_junnban[i], now)
        now = t_junnban[i][ni-1]
    else:
        now = t_junnban[i][ni]
ans += now+1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
s = input()
t = input()
n_s = len(s)
n_t = len(t)

for i in range(n_t):
    if t[i] not in s:
        print(-1)
        exit()

idx = [[] for _ in range(26)]
#print(ord("a"))
#print(ord("z"))

def a_idx(a):
    idx = ord(a)
    idx -= 97
    return idx


for i in range(n_s):
    idx[a_idx(s[i])].append(i)

t_junnban = []
for i in range(n_t):
    t_junnban.append(idx[a_idx(t[i])])
print(t_junnban)

now = 0
ans = 0
for i in range(n_t):
    ni = bisect_left(t_junnban[i], now)
    if ni >= len(t_junnban[i]):
        now = 0
        ans += n_s
        ni = bisect_left(t_junnban[i], now)
        now = t_junnban[i][ni]
    else:
        now = t_junnban[i][ni]
ans += now+1
print(ans)

Submission status: Runtime Error

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

pos=[[] for _ in range(26)]

len_s=len(s)
len_t=len(t)


for i in range(len_s):
    idx=ord(s[i])-97
    pos[idx].append(i)

ans=[]
tmp=0
for i in range(len_t):
    idx=ord(t[i])-97
    if len(pos[idx])==0:
        print(-1)
        exit()
    if tmp>pos[idx][-1]:
        ans.append(pos[idx][0])
        tmp=pos[idx][0]
    elif tmp<=pos[idx][0]:
        ans.append(pos[idx][0])
        tmp=pos[idx][0]
    else:
        l=0
        r=len(pos[idx])-1
        while l+1<r:
            mid=(l+r)//2
            if pos[idx][mid]<=ans:
                l=mid
            else:
                r=mid
        ans.append(pos[idx][r])
        tmp=pos[idx][r]
cnt=0
for i in range(1,len_t):
    if ans[i-1]>=ans[i]:
        cnt+=1

print(cnt*len_s+ans[-1]+1)

Submission status: Runtime Error

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

l_s = len(S)
l_t = len(T)

s_pos = {}
for i in range(l_s):
    if S[i] in s_pos:
        s_pos[S[i]].append(i)
    else:
        s_pos[S[i]] = [i]

n_pos = {}
for key, val in s_pos.items():
    n_pos[key] = [0]*l_s
    l = 0
    for p in val:
        for i in range(l, p + 1):
            n_pos[key][i] = p
        l = p + 1
    for i in range(l, l_s):
        n_pos[key][i] = val[0]

flg = True

if T[0] in n_pos:
    c = n_pos[T[0]][0]
    loop_cnt = 0

    for i in range(l_t - 1):
        if not T[i + 1] in n_pos:
            flg = False
        n_c = n_pos[T[i + 1]][c]
        if c >= n_c:
            loop_cnt += 1
        c = n_c
else:
    flg = False

if flg:
    print(loop_cnt * l_s + c + 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import bisect

S = input()
T = input()

l_s = len(S)
l_t = len(T)

s_pos = {}
for i in range(l_s):
    if S[i] in s_pos:
        s_pos[S[i]].append(i)
    else:
        s_pos[S[i]] = [i]

f_pos = [[] for _ in range(l_t)]
for i in range(l_t):
    if T[i] in s_pos:
        f_pos[i] = s_pos[T[i]]

loop_cnt = 0
c = min(f_pos[0])
for i in range(l_t - 1):
    p = bisect.bisect_right(f_pos[i + 1], c)
    if p >= len(f_pos[i + 1]):
        loop_cnt += 1
        c = f_pos[i + 1][p - 1]
    else:
        c = f_pos[i + 1][p]
        
print(loop_cnt * l_s + c + 1)

Submission status: Runtime Error

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

from collections import Counter

S=Counter(s)
T=Counter(t)

for a in T.keys():
    if not a in S.keys():
        print(-1)
        exit()

Ls=len(s)
Lt=len(t)

from collections import deque

abc="abcdefghjijklmnopqrstuvwxyz"
pos=[[] for _ in range(26)]
for i in range(Ls):
    ch=s[i]
    idx=abc.index(ch)
    pos[idx].append(i)

Ns=[]
now=0
for i in range(Lt):
    ch=t[i]
    idx=abc.index(ch)
    if pos[idx][-1]<now:
        Ns.append(pos[idx][0])
        now=pos[idx][0]
        continue
    l=0
    r=len(pos[idx])
    while l+1<r:
        mid=(l+r)//2
        if pos[idx][mid]<=now:
            l=mid
        else:
            r=mid
    Ns.append(pos[idx][l])
    now=pos[idx][l]

cnt=0
for i in range(1,Lt):
    if Ns[i-1]>=Ns[i]:
        cnt+=1
print(cnt*Ls+Ns[-1]+1)

Submission status: Runtime Error

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

from collections import Counter

S=Counter(s)
T=Counter(t)

for a in T.keys():
    if not a in S.keys():
        print(-1)
        exit()

Ls=len(s)
Lt=len(t)

from collections import deque

abc="abcdefghjijklmnopqrstuvwxyz"
pos=[[] for _ in range(26)]
for i in range(Ls):
    ch=s[i]
    idx=abc.index(ch)
    pos[idx].append(i)

Ns=[]
now=0
for i in range(Lt):
    ch=t[i]
    idx=abc.index(ch)
    if pos[idx][-1]<now:
        Ns.append(pos[idx][0])
        now=pos[idx][0]
        continue
    l=-1
    r=len(pos[idx])
    while l+1<r:
        mid=(l+r)//2
        if pos[idx][mid]<now:
            l=mid
        else:
            r=mid
    Ns.append(pos[idx][r])
    now=pos[idx][r]

cnt=0
for i in range(1,Lt):
    if Ns[i-1]>=Ns[i]:
        cnt+=1
print(cnt*Ls+Ns[-1]+1)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# inputna
s = input()
t = input()

l = [chr(v) for v in range(ord("a"), ord("z")+1)]
d = {c:i for i,c in enumerate(l)}

def snx(s, target=None, reverse=False, loop=False):
    """文字列sの各要素について、cがiより→で最初に現れる位置n[i][c]
    loop=Trueのとき周回した先のインデックスまで求める
    """
    if target is None:
        target = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:None for c in target}
    nx = [[None]*len(target) for _ in range(len(s))]
    if not reverse:
        i = len(s)-1
        for c in reversed(s):
            d[c] = i
            for j,t in enumerate(target):
                nx[i][j] = d[t]
            i -= 1
        if loop:
            for i in range(len(s)):
                for j in range(len(target)):
                    if nx[i][j] is None:
                        nx[i][j] = nx[0][j]
    else:
        i = 0
        for c in s:
            d[c] = i
            for j,t in enumerate(target):
                nx[i][j] = d[t]
            i += 1
        if loop:
            for i in range(len(s)):
                for j in range(len(target)):
                    if nx[i][j] is None:
                        nx[i][j] = nx[-1][j]
    return nx
nx = snx(s, loop=True)
c = -1
ans = 0
for i in range(len(t)):
    nc = nx[c+1][d[t[i]]]
    if nc is None:
        ans = -1
        break
    elif nc>c:
        ans += nc-c
    else:
        ans += nc+len(s)-c
    c = nc
print(ans)

Submission status: Runtime Error

Solution code:
from math import *
from bisect import *
s=input()
t=input()
n=len(s)
nn=len(t)
ss=[[]for i in range(26)]
tt=[[] for i in range(26)]
ans=0
k=0
for i in range(n):
    ss[ord(s[i])-97].append(i+1)
for i in t:
    j=ss[ord(i)-97]
    if len(j)==0:
        print(-1)
        exit()
    else:
        if j[-1]<ans:
            ans=j[0]
            k+=1
        else:
            ans=j[bisect(j,ans)]
print(k*n+ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import copy
import sys
s = input()
n_s = len(s)
t = input()
n_t = len(t)

chr_firstind = defaultdict(lambda:-1)
chr_nextind = defaultdict(lambda:-1)
i_to_chr_nextind = [0] * n_s
for i in range(n_s-1,-1,-1):
    chr_firstind[s[i]] = i
    i_to_chr_nextind[i] = copy.copy(chr_nextind)
    chr_nextind[s[i]] = i 

first_target = t[0]
previous_ind = chr_firstind[first_target]
if previous_ind == -1:
    print(-1)
    sys.exit()
if n_t == 1:
    print(first_ind+1)
    sys.exit()
s_used = 0
for i in range(1,n_t):
    # 一つ前のtarget_indを使って、次のtargetのs内でのindexを求める
    d = i_to_chr_nextind[previous_ind]
    next_ind = d[t[i]]
    if next_ind == -1:
        s_used += 1
        next_ind = chr_firstind[t[i]]
        if next_ind == -1:
            print(-1)
            sys.exit()
    previous_ind = next_ind
print(n_s*s_used+previous_ind+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import copy
s = input()
import sys
n_s = len(s)
t = input()
n_t = len(t)

alphabet = [chr(i) for i in range(97, 97+26)]
al_d = {}
for i in range(26):
    al_d[alphabet[i]] = i

chr_firstind = defaultdict(lambda:-1)
chr_nextind = defaultdict(lambda:-1)
i_to_chr_nextind = [0] * n_s
for i in range(n_s-1,-1,-1):
    chr_firstind[s[i]] = i
    i_to_chr_nextind[i] = copy.copy(chr_nextind)
    chr_nextind[s[i]] = i 

first_target = t[0]
previous_ind = chr_firstind[first_target]
if n_t == 1:
    if previous_ind == -1:
        print(-1)
    else:
        print(first_ind)+1
    sys.exit()
s_used = 0
for i in range(1,n_t):
    # 一つ前のtarget_indを使って、次のtargetのs内でのindexを求める
    d = i_to_chr_nextind[previous_ind]
    next_ind = d[t[i]]
    if next_ind == -1:
        s_used += 1
        next_ind = chr_firstind[t[i]]
        if next_ind == -1:
            print(-1)
            sys.exit()
    previous_ind = next_ind
print(n_s*s_used+previous_ind+1)

Submission status: Runtime Error

Solution code:
N, *A = map(int, open(0).read().split())

A = [0] + A
B = [0] * (N + 1)
sum_B = 0
for i in range(N, 0, -1):
    if sum(B[j] for j in range(i, N + 1, i)) % 2 != A[i]:
        B[i] = 1
        sum_B += 1
print(sum_B)
print(*[i for i, b in enumerate(B) if b])

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	if nx.get((c,x[j])) is None:
		nx[('.',c)] = i+1
	else:
		continue
	for j in range(i+1,len(x)):
		if nx.get((c,x[j])) is None:
			nx[(c,x[j])] = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

Submission status: Runtime Error

Solution code:
from bisect import *
from collections import defaultdict
import sys
input = sys.stdin.readline

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

dic = defaultdict(list)
for i, s in enumerate(S):
    dic[s].append(i)


s0 = -1
cnt = 0
for t in T:
    if not dic[t]:
        print(-1)
        exit()
    p = bisect_right(dic[t],s0)
    if p >= len(dic[t]):
        cnt += 1
        s0 = min(dic[t])
    else:
        s0 = dic[t][bisect_right(dic[t], p)]

print(L*cnt+s0 +1)

Submission status: Runtime Error

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    for i in t:
        if not i in s:
            print(-1)
            exit()
    s *= lt
    nm = 0
    for i,si in enumerate(s):
        if si == t[nm]:
            nm += 1
        if nm == lt:
            print(i+1)
            exit()

    return None

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
s=input()
t=input()
dic={}
for i in range(len(t)):
  if t[i] in dic:
    continue
  if t[i] not in dic:
    dic[t[i]]=[]
for i in range(len(s)):
  if s[i] in dic:
    dic[s[i]].append(i)
n=-1
k=0

for i in range(len(t)):
  l=bisect.bisect_right(dic[t[i]],n)
  if l<len(dic[t[i]]):
    n=dic[t[i]][l]
  else:
    n=dic[t[i]][0]
    k+=1
print(len(s)*k+n+1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

S = input()
T = input()

ss = set(list(S))
st = set(list(T))
if not (st <= ss):
    print(-1)
    exit()
alpha = {chr(97+i): [] for i in range(26)}
for i, s in enumerate(S):
    alpha[s].append(i+1)
n = len(S)
now = 0
ans = 0
for t in T:
    if alpha[t][-1] < now:
        ans += (n - now) + alpha[t][0]
        now = alpha[t][0]
    else:
        i = bisect_left(alpha[t], now+1)
        ans += alpha[t][i] - now
        now = alpha[t][i]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from _bisect import bisect_right

s,t=input(),input()
m=len(s)

if set(s)&set(t)!=set(t):print(-1);exit()

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>=num:
        ans +=m
    index=num
    
print(ans+index)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from _bisect import bisect_right

s,t=input(),input()
m=len(s)

if set(s)&set(t)!=set(t):print(-1);exit()

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>num:
        ans +=m
    index=num
    
print(ans+index)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_e

from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

# Tの文字はSに出ていないといけない
for ch in T:
    if ch not in S:
        print("-1")
        exit()

# Sの中での位置
iS = defaultdict(list)
for (idx, ch) in enumerate(S):
    iS[ch].append(idx)

# 探索
cnt = 0
cur = -1
for v in T:
    i = bisect_right(iS[ch], cur)
    if i == len(iS[v]):
        j = iS[v][0]
    else:
        j = iS[v][i]

    if cur >= j:
        cnt += 1
    cur = j

print(cnt * len(S) + cur + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()

indices = defaultdict(list)
for i, v in enumerate(s):
    indices[v].append(i)

cnt = 0
cur = -1
mod = len(s)
flag = False
for v in t:
    if v not in indices:
        flag = True
        break

    i = bisect_right(indices[v], cur)
    if i == len(indices[v]):
        j = indices[v][0]
    else:
        j = indices[v][i]

    if cur >= j:
        cnt += 1
    cur = j

if flag:
    print(-1)
else:
    print(cnt * mod + cur + 1)

Submission status: Runtime Error

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

s = rs()
t = rs()


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

import bisect

def bisect_right(arr, x):
    # a_i <= x < a_{i+1}
    l, r = 0, len(arr)
    while r - l > 1:
        c = (r + l) // 2
        if x >= arr[c]:
            l = c
        else:
            r = c
    return r

num = 0
cur = -1

for c in t:
	if c not in pos:
		print(-1)
		exit()
	#i = bisect.bisect_right(pos[c], cur)
	i = search(pos[c], cur)
	if i == len(pos[c]):
		i = 0
		num += 1
	cur = pos[c][i]
print(num*len(s)+cur+1)

Submission status: Runtime Error

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

t_set = list(set([i for i in t]))
flg = False
for ts in t_set:
  if ts not in s:
    flg = True
    break

def bi_search(l, target):
  length = len(l)
  if length == 1:
    if l[0] <= target:
      return -1
    return l[0]
  elif length == 2:
    if target >= l[1]:
      return -1
    elif target < l[0]:
      return l[0]
    else:
      return l[1]
  elif l[length//2] < target:
    return bi_search(l[:length//2])
  else:
    return bi_search(l[length//2:])
    
if flg:
  print(-1)
else:
  from collections import defaultdict
  indices = defaultdict(list)
  for i, si in enumerate(s):
    indices[si].append(i+1)
  ans = 0
  lap = 0
  for ti in t:
    target = indices[ti]
    r = bi_search(target, ans % len(s))
    if r == -1:
      lap += 1
      ans = lap * len(s) + target[0]
    else:
      ans = lap * len(s) + r
    #print(ti, r, ans, ans % len(s))
  print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,ans)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,ans)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + counter[T[::-1][0]][0] + 1
    print(ans)




if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
s, t = [x.strip() for x in open(0).readlines()]
if set(t) - set(s) != set():
    print(-1)
else:
    d = defaultdict(deque)
    n = len(s)
    for i, c in enumerate(s, 1):
        d[c].append(i)
    ans = 0
    for c in t:
        while True:
            i = d[c].popleft()
            d[c].append(i + n)
            if ans < i:
                ans = i
                break
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline

S = readline().rstrip()
T = readline().rstrip()

if len(set(T) - set(S)) > 0:
  print(-1)
  exit(0)
  
import bisect
# Tの各文字を探す
S2 = S * 2
from collections import defaultdict
# ある文字が何文字目にあるか辞書
dic = defaultdict(list)

for i in range(len(S2)):
  dic[S2[i]] += [i]

ind = -1
ans = 0
for t in T:
  # 探す文字はt
  targets = dic[t]
#  print("targets",targets,"t",t,"ind + 1",ind + 1)
  newind = targets[bisect.bisect_left(targets, ind + 1)]
#  print("t",t,"S2",S2,"newind",newind)
  ans += (newind - ind)
  if newind > len(S):
    newind -= len(S)
  ind = newind

print(ans)

Submission status: Runtime Error

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

sbasic=[[] for _ in range(26)]
for i,s in enumerate(S):
  sbasic[ord(s)-ord("a")].append(i)

for s in set(S):
    if len(sbasic[ord(s)-ord("a")])==0:
        print(-1)
        exit()

slist=copy.deepcopy(sbasic)
index=-1
roop=0
for t in T:
  if len(sbasic[ord(t)-ord("a")])==0:
    roop+=1
    #slist=copy.deepcopy(sbasic)
    index=-1
  pos=bisect.bisect_right(sbasic[ord(t)-ord("a")],index)
  if pos==len(sbasic[ord(t)-ord("a")]):
    roop+=1
    #slist=copy.deepcopy(sbasic)
    index=-1
    pos=0
  index=sbasic[ord(t)-ord("a")][pos]
  
print(len(S)*roop+index+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

input = sys.stdin.readline
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Runtime Error

Solution code:


S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Runtime Error

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

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input()
T = input()


idx = S.index(T[0])
ans = idx+1
lenT = len(T)
for i in range(1,lenT):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Runtime Error

Solution code:
# Python3 (3.4.3)
import sys

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input()
T = input()


idx = S.index(T[0])
ans = idx+1
lenT = len(T)
for i in range(1,lenT):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Runtime Error

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()


idx = S.index(T[0])
ans = idx+1
lenT = len(T)
for i in range(1,lenT):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Runtime Error

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()


idx = S.index(T[0])
ans = idx+1
for i in range(1,len(T)):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import bisect
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

s=list(ns())
t=list(ns())
d={'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}

order=[[] for _ in range(26)]

for i in range(len(s)):
  order[d[s[i]]].append(i)
  
now=0
ans=0
rep=0
for i in range(len(t)):
  inds=d[t[i]]
  if(order[inds]==[]):
    print(-1)
    sys.exit(0)
  index=bisect.bisect_left(order[inds],now)
  if(index==len(order[inds])):
    now=order[inds][0]
    rep+=1
  else:
    now=order[inds][index]


print(rep*len(s)+now+1)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import bisect
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

s=list(ns())
t=list(ns())
d={'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}

order=[[] for _ in range(26)]

for i in range(len(s)):
  order[d[s[i]]].append(i)
  
now=0
ans=0
rep=0
for i in range(len(t)):
  inds=d[t[i]]
  if(order[inds]==0):
    print(-1)
    sys.exit(0)
  index=bisect.bisect_left(order[inds],now)
  if(index==len(order[inds])):
    now=order[inds][0]
    rep+=1
  else:
    now=order[inds][index]


print(rep*len(s)+now+1)

Submission status: Runtime Error

Solution code:
import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l.append(G.copy())
  G[s[i]] = i
l = l[::-1]  
stG = G.copy()

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind == len(t):
        break          
    cnt += 1

###    
if cnt != -1:      
  print(cnt*len(s)-(len(s)-(lind+1)))
else:
  print(cnt)

Submission status: Runtime Error

Solution code:
  print(cnt)import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l.append(G.copy())
  G[s[i]] = i
l = l[::-1]  
stG = G.copy()

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind == len(t):
        break          
    cnt += 1

###    
if cnt != -1:      
  print(cnt*len(s)-(len(s)-(lind+1)))
else:
  print(cnt)

Submission status: Runtime Error

Solution code:
import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l.append(G.copy())
  G[s[i]] = i
l = l[::-1]  
stG = G.copy()

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind == len(t):
        break   
    if ind == len(t):
      break        
    cnt += 1

###    
if cnt != -1:      
  print(cnt*len(s)+stG[t[-1]]+1)
else:
  print(cnt)