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: Wrong Answer

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

import bisect
from collections import defaultdict
d = defaultdict(list)
for i in range(len(s)):
    d[s[i]].append(i)

now=-1
cnt=0
for i in range(len(t)):
    if len(d[t[i]])==0:
        print(-1)
        exit()
    found=False

    ind = bisect.bisect_left(d[t[i]],now)
    if ind!=len(d[t[i]]):
        now=d[t[i]][ind]
    else:
        now=d[t[i]][0]
        cnt+=1

print(cnt*len(s) + d[t[-1]][0]+1)

Submission status: Wrong Answer

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

from collections import defaultdict
d = defaultdict(list)
for i in range(len(s)):
    d[s[i]].append(i)

now=-1
cnt=0
for i in range(len(t)):
    if len(d[t[i]])==0:
        print(-1)
        exit()
    found=False

    for idx in d[t[i]]:
        if idx > now:
            found=True
            now=idx
            break
    if not found:
        now=d[t[i]][0]
        cnt+=1
print(cnt*len(s) + d[t[-1]][0]+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  for i in range(n):
    if len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
  cnt=0
  for i in range(n-1):
    l=len(lindex[ord(t[i+1])-97])
    if l==bisect_right(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0]):
      cnt+=1
  k=lindex[ord(t[n-1])-97][0]
  return print(m*cnt+k+1)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  for i in range(n):
    if len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
  cnt=0
  for i in range(n-1):
    l=len(lindex[ord(t[i+1])-97])
    if l==bisect_left(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0]):
      cnt+=1
  k=lindex[ord(t[n-1])-97][0]
  return print(m*cnt+k+1)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
s,t=open(0)
n=len(s)-1
a={}
for i in range(n):
  u=s[i]
  a[u]=a.get(u,[])+[i]
p=0
q=0
for u in t:
  v=a.get(u,False)
  if v:
    for w in a[u]:
      if w>q:
        q=w
        break
    else:
      p+=1
      q=a[u][0]
  else:
    print(-1)
    break
else:
  print(p*n+q+1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lis=[]
  for i in range(n):
    if t[i] not in s:
      print(-1)
      exit()
    else:
      inde=s.index(t[i])
      lis.append([inde,i])
      if i==n-1:
        k=inde
  lis.sort()
  for i in range(n):
    lis[i][0]=i
  lis.sort(key=itemgetter(1))
  cnt=0
  for i in range(n-1):
    if lis[i][0]>lis[i+1][0]:
      cnt+=1
  return print(m*cnt+k+1)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#一つのsでtのどこまで生成できるか
#毎回文字列sの頭から見てたら遅いのでsの辞書化
import bisect
s = input()
t = input()

sd = {}
for i,ss in enumerate(s):
    if ss not in sd:
        sd[ss] = [i]
    else:
        sd[ss].append(i)

ans = 1
s_idx = -1
for tt in t:
    if tt not in sd:
        print(-1)
        exit()
    while True:
        n_s_idx = bisect.bisect_left(sd[tt],s_idx)
        if [n_s_idx] == len(sd[tt]) - 1:
            ans += 1
            s_idx = -1
            break
        else:
            s_idx = n_s_idx
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s = input()
t = input()

l = len(s)

ss = s * 2
let = [[] for _ in range(26)]
for i, e in enumerate(ss, 1):
    idx = ord(e) - ord("a")
    let[idx].append(i)

for e in t:
    idx = ord(e) - ord("a")
    if not let[idx]:
        print(-1)
        exit()

i = 1
times = 0
for e in t:
    j = ord(e) - ord("a")
    choose = bisect_left(let[j], i)
    q, i = divmod(let[j][choose], l)
    times += q

ans = times * l + i
print(ans)

Submission status: Wrong Answer

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i)

out = 0
cnt = -1
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l + 1
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt + 1
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] < V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * (cnt + 1))
    else:
        print(len(S) * cnt + V[-1])
a = 0

Submission status: Wrong Answer

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i)

out = 0
cnt = 0
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l + 1
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt + 1
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] < V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * (cnt + 1))
    else:
        print(len(S) * cnt + V[-1])
a = 0

Submission status: Wrong Answer

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i)

out = 0
cnt = 0
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l + 1
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt + 1
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] < V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * (cnt + 1))
    else:
        print

Submission status: Wrong Answer

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i)

out = 0
cnt = 0
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l + 1
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt + 1
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] < V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * cnt)
    else:
        print(len(S) * cnt + V[-1])
a = 0

Submission status: Wrong Answer

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i)

out = 0
cnt = 0
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l + 1
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt + 1
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] < V[i]:
            cnt += 1
    if cnt == 0:
        print(len(S))
    elif V[-1] == len(S):
        print(len(S) * cnt)
    else:
        print(len(S) * cnt + V[-1])
a = 0

Submission status: Wrong Answer

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i)

out = 0
cnt = 0
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l + 1
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt + 1
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] < V[i]:
            cnt += 1
    if V[-1] == len(S):
        print(len(S) * cnt)
    else:
        print(len(S) * cnt + V[-1])
a = 0

Submission status: Wrong Answer

Solution code:
import string
import bisect

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

s_alpha_ind = {x:[] for x in string.ascii_lowercase}

for i in range(len_s):
    s_alpha_ind[s[i]].append(i)

ans = 1
now_s_ind = 0
for i in range(len_t):
    now_t = t[i]
    if len(s_alpha_ind[now_t]) == 0:
        ans = -1
        break
    else:
        # print('now s_ind is: '+ str(now_s_ind))
        # print('-'*30)
        # print('now_t is: ' + str(now_t))

        # 二分探索で、now_s_indよりも大きな値を探す
        # なければ最初の値を返す
        Inds = s_alpha_ind[now_t]
        ind = bisect.bisect_right(Inds, now_s_ind)
        # print('Inds is :')
        # print(Inds)
        # print('ind is:' + str(ind))

        if ind == len(Inds):
            ans += (len_s-1) - now_s_ind + (Inds[0]+1)
            if i == 0:
                ans -= len_s
            now_s_ind = Inds[0]
        else:
            ans += Inds[ind] - now_s_ind
            now_s_ind = Inds[ind]
        # print('ans is:' +  str(ans))


print(ans)

Submission status: Wrong Answer

Solution code:
import string
import bisect

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

s_alpha_ind = {x:[] for x in string.ascii_lowercase}

for i in range(len_s):
    s_alpha_ind[s[i]].append(i)

ans = 1
now_s_ind = 0
for i in range(len_t):
    now_t = t[i]
    if len(s_alpha_ind[now_t]) == 0:
        ans = -1
        break
    else:
        # print('now s_ind is: '+ str(now_s_ind))
        # print('-'*30)
        # print('now_t is: ' + str(now_t))

        # 二分探索で、now_s_indよりも大きな値を探す
        # なければ最初の値を返す
        Inds = s_alpha_ind[now_t]
        ind = bisect.bisect_right(Inds, now_s_ind)
        if ind == len(Inds):
            ans += (len_s-1) - now_s_ind + (Inds[0]+1)
            now_s_ind = Inds[0]
        else:
            ans += Inds[ind] - now_s_ind
            now_s_ind = Inds[ind]
        # print('ans is:' +  str(ans))


print(ans)

Submission status: Wrong Answer

Solution code:
import string
import bisect

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

s_alpha_ind = {x:[] for x in string.ascii_lowercase}

for i in range(len_s):
    s_alpha_ind[s[i]].append(i)

ans = 1
now_s_ind = 0
for i in range(len_t):
    now_t = t[i]
    if len(s_alpha_ind[now_t]) == 0:
        ans = -1
        break
    else:
        # print('now s_ind is: '+ str(now_s_ind))
        # print('-'*30)
        # print('now_t is: ' + str(now_t))
        
        # 二分探索で、now_s_indよりも大きな値を探す
        # なければ最初の値を返す
        Inds = s_alpha_ind[now_t]
        ind = bisect.bisect_right(Inds, now_s_ind)
        if ind == len(Inds):
            ans += len_s - now_s_ind + Inds[0]
            now_s_ind = Inds[0]
        else:
            ans += Inds[ind] - now_s_ind
            now_s_ind = Inds[ind]
        # print('ans is:' +  str(ans))

            
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
alph=[[]for _ in range(26)]
for i in range(len(s)):
	alph[ord(s[i])-ord("a")].append(i)
now=[0]*26
ans=0
p=-1
for i in range(len(t)):
	r=ord(t[i])-ord("a")
	if len(alph[r])==0:
		print(-1)
		exit()

	if p<=alph[r][now[r]]:
		ans+=alph[r][now[r]]-p
	else:
		ans+=len(s)-p+alph[r][now[r]]
	p=alph[r][now[r]]

	now[r]+=1
	if now[r]==len(alph[r]):
		now[r]=0
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
alph=[[]for _ in range(26)]
for i in range(len(s)):
	alph[ord(s[i])-ord("a")].append(i)
now=[0]*26
ans=1
p=0
for i in range(len(t)):
	if len(alph[ord(t[i])-ord("a")])==0:
		print(-1)
		exit()
	if now[ord(t[i])-ord("a")]==len(alph[ord(t[i])-ord("a")]):
		now[ord(t[i])-ord("a")]=0
	if p<alph[ord(t[i])-ord("a")][now[ord(t[i])-ord("a")]]:
		ans+=alph[ord(t[i])-ord("a")][now[ord(t[i])-ord("a")]]-p
	else:
		ans+=len(s)-p+alph[ord(t[i])-ord("a")][now[ord(t[i])-ord("a")]]
	p=alph[ord(t[i])-ord("a")][now[ord(t[i])-ord("a")]]
	now[ord(t[i])-ord("a")]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
s = [ord(i) - ord("a") for i in input()]
t = [ord(i) - ord("a") for i in input()]
index = [[] for _ in range(26)]

for i, x in enumerate(s):
    index[x].append(i)


l_s = len(s)

for x in index:
    if x:
        x.append(x[0] + l_s)

cnt = 0
for r in t:
    seq = index[r]
    if not seq:
        cnt = -2
        break
    i = cnt % l_s
    j = bisect_right(seq, i)
    cnt += seq[j] - i

print(cnt+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
s = [ord(i) - ord("a") for i in input()]
t = [ord(i) - ord("a") for i in input()]
index = [[] for _ in range(26)]

for i, x in enumerate(s):
    index[x].append(i)


l_s = len(s)

for x in index:
    if x:
        x.append(x[0] + l_s)

print(index)

cnt = 0
for r in t:
    seq = index[r]
    if not seq:
        cnt = -2
        break
    i = cnt % l_s
    j = bisect_right(seq, i)
    cnt += seq[j] - i

print(cnt+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
s = input()
t = input()
l_s = len(s) * 2

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

next_ch = defaultdict(list)
for j, k in ch.items():
    for i in k:
        next_ch[j] += [i] * (i + 1 - len(next_ch[j]))
    next_ch[j] += [k[-1]+l_s//2] * (l_s - len(next_ch[j]))

cnt = 0
for i in t:
    if i not in next_ch.keys():
        cnt = -2
        break
    cnt += next_ch[i][(1+cnt) % l_s] - (cnt % l_s)
print(cnt + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
s = input()
t = input()
l_s = len(s) * 2

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

print(ch)
next_ch = defaultdict(list)
for j, k in ch.items():
    for i in k:
        next_ch[j] += [i] * (i+1)
    next_ch[j] += [k[-1]+l_s] * (l_s - len(next_ch[j]))

cnt = 0
for i in t:
    if i not in next_ch.keys():
        cnt = -2
        break
    cnt += next_ch[i][(1+cnt) % l_s] - (cnt % l_s)
print(cnt + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np
s = input()
t = input()
l_s = len(s)

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

next_ch = defaultdict(list)
for j, k in ch.items():
    w = np.zeros(l_s, dtype=int)
    w[k[-1]:] = k[-1] + l_s
    while k:
        r = k.pop()
        w[:r+1] = r
    next_ch[j] = w

cnt = 0
for i in t:
    if i not in next_ch.keys():
        cnt = -2
        break
    cnt += next_ch[i][cnt % l_s] - (cnt % l_s)
print(cnt + 1)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_right
    s=input()
    t=input()
    ls=len(s)
    lt=len(t)

    dic={i:[] for i in set(t)}
    for i in range(ls):
        st=s[i]
        if st in dic:
            dic[st].append(i)
    
    

    cnt=0
    idx=0
    for i in range(lt):
        st=t[i]
        if dic[st]==[]:
            print(-1)
            exit()

        tmp_idx=bisect_right(dic[st],idx)

        if tmp_idx==len(dic[st]):
            cnt+=1
            idx=dic[st][0]
        
        else:
            idx=dic[st][tmp_idx]
    
    print(cnt*ls+idx+1)  
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_right
    s=input()
    t=input()
    ls=len(s)
    lt=len(t)

    dic={i:[] for i in set(t)}
    for i in range(ls):
        st=s[i]
        if st in dic:
            dic[st].append(i)
    
    

    cnt=0
    idx=0
    for i in range(lt):
        st=t[i]
        if dic[st]==[]:
            print(-1)
            exit()

        tmp_idx=bisect_right(dic[st],idx)

        if tmp_idx==len(dic[st]):
            cnt+=1
            idx=dic[st][-1]
        
        else:
            idx=dic[st][tmp_idx]
    
    print(cnt*ls+idx+1)  
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	t = input()
	if len(set(s)&set(t)) != len(set(t)):
		print(-1)
		exit()

	dic = defaultdict(int)
	for i, char in enumerate(s):
		if not dic[char]:
			dic[char] = i+1

	t_num = list(t)
	for i in range(len(t)):
		t_num[i] = dic[t[i]]
	
	loop = 0
	tmp = t_num[0]
	for n in t_num:
		if n < tmp:
			loop += 1
		tmp = n
		
	print(len(s)*loop+t_num[-1])

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import defaultdict
d = defaultdict(list)

S = input()
T = input()

# 文字列の各文字がどのインデックスにあるか辞書化する
for i in range(len(S)):
    d[S[i]].append(i)


NoFind = False

sequence = 1  # 文字列の連続数
index = -1
for i in range(len(T)):
    if len(d[T[i]]) == 0:
        NoFind = True
        break
    find = bisect_left(d[T[i]], index)
    if find != len(d[T[i]]):
        index = d[T[i]][find] + 1
    else:  # 見つからなかったので文字列を追加
        sequence += 1
        index = -1
        find = bisect_left(d[T[i]], index)
        index = d[T[i]][find] + 1 
            
if NoFind:
    print(index)
else:
    print(len(S)*(sequence-1) + index)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict
d = defaultdict(list)

S = input()
T = input()

# 文字列の各文字がどのインデックスにあるか辞書化する
for i in range(len(S)):
    d[S[i]].append(i)


NoFind = False

sequence = 1  # 文字列の連続数
index = -1
for i in range(len(T)):
    arr = np.array(d[T[i]])
    find = arr[arr > index]
    if len(find) >= 1:
        index = find[0]
    else:  # 見つからなかったので文字列を追加
        sequence += 1
        index = -1
        find = arr[arr > index]
        if len(find) >= 1:
            index = find[0]        
        else:  # 2度目見つからなかったので成立不可
            NoFind = True
            
if NoFind:
    print(index)
else:
    print(len(S)*(sequence-1) + index + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
d = defaultdict(list)

S = input()
T = input()

# 文字列の各文字がどのインデックスにあるか辞書化する
for i in range(len(S)):
    d[S[i]].append(i)


NoFind = False

sequence = 1  # 文字列の連続数
index = -1
for i in range(len(T)):
    for ti in d[T[i]]:
        if ti > index:  # Sのindex以降にT[i]が存在する
            index = ti
            break
    else:  # 見つからなかったので文字列を追加
        sequence += 1
        index = -1
        for ti in d[T[i]]:
            if ti > index:  # Sのindex以降にT[i]が存在する
                index = ti
                break
        else:  # 2度目見つからなかったので成立不可
            NoFind = True
            
if NoFind:
    print(index)
else:
    print(len(S)*(sequence-1) + index + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
d = defaultdict(list)

S = input()
T = input()

# 文字列の各文字がどのインデックスにあるか辞書化する
for i in range(len(S)):
    d[S[i]].append(i)


NoFind = False

sequence = 1  # 文字列の連続数
index = 0
for i in range(len(T)):
    TargetIndex = d[T[i]]
    for ti in TargetIndex:
        if ti >= index:  # Sのindex以降にT[i]が存在する
            index = ti
            break
    else:  # 見つからなかったので文字列を追加
        sequence += 1
        index = 0
        for ti in TargetIndex:
            if ti >= index:  # Sのindex以降にT[i]が存在する
                index = ti
                break
        else:  # 2度目見つからなかったので成立不可
            NoFind = True
            
if NoFind:
    print(-1)
else:
    print(len(S)*(sequence-1) + index + 1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
data = {}
max_s = len(s) + 1
for i in range(26):
    data[chr(i + ord('a'))] = []
for i in range(len(s)):
    data[s[i]].append(i+1)
for i in range(26):
    data[chr(i + ord('a'))].append(max_s)
pre = 0
ans = 0
for i in range(len(t)):
    char = t[i]
    if len(data[char]) == 1:
        print(-1)
        exit()
    else:
        index = bisect.bisect_left(data[char], pre)
        if data[char][index] == max_s:
            ans += len(s) - pre
            pre = data[char][0]
            ans += pre
        else:
            ans += data[char][index] - pre
            pre = data[char][index]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
data = {}
max_s = len(s) + 1
for i in range(26):
    data[chr(i + ord('a'))] = []
for i in range(len(s)):
    data[s[i]].append(i+1)
for i in range(26):
    data[chr(i + ord('a'))].append(max_s)
pre = 0
ans = 0
for i in range(len(t)):
    char = t[i]
    if len(data[char]) == 1:
        print(-1)
        exit()
    else:
        index = bisect.bisect_left(data[char], pre)
        if index + 1 >= len(data[char]):
            ans += len(s) - pre
            pre = data[char][0]
            ans += pre
        else:
            ans += data[char][index] - pre
            pre = data[char][index]
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
t = list(input()[::-1])
cnt = -1
while t:
    now = t.pop()
    cnt += 1
    r = 0
    flg = True
    while r <= n:
        if s[cnt % n] == now:
            flg = False
            break
        cnt += 1
        r += 1
    if flg:
        cnt = -2
print(cnt+1)

Submission status: Wrong Answer

Solution code:
def next_item(arr, target): 
    start = 0
    end = len(arr) - 1
    ans = -1
    while (start <= end): 
        mid = (start + end) // 2
        if arr[mid] < target: 
            start = mid + 1
        else: 
            ans = mid
            end = mid - 1
  
    return arr[ans]


def is_substring(s_char_map, t):
    for char in t:
        if char not in s_char_map:
            return False
    return True


def get_impurity(s, t):
    s_char_map = {}
    
    s_len = len(s)
    for char_idx in range(s_len):
        if s[char_idx] not in s_char_map:
            s_char_map[s[char_idx]] = [char_idx + 1]
        else:
            s_char_map[s[char_idx]].append(char_idx + 1)
    last_idx = -1
    s_length = len(s)
    full_length = 0
    
    if not is_substring(s_char_map, t):
        return -1
    
    for char in t:
        if s_char_map[char][-1] >= last_idx:
            last_idx = next_item(s_char_map[char], last_idx)
            full_length += last_idx - (full_length % s_length)
        else:
            last_idx = s_char_map[char][0]
            full_length += (s_length - (full_length % s_length)) + last_idx
    return full_length

s = input()
t = input()
print(get_impurity(s, t))

Submission status: Wrong Answer

Solution code:
from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)

a=len(s)*len(t)
maxcount=len(s)
for i in range(100):
    if maxcount<a:
        maxcount**=10
    else:
        break


for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=0
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]+1
    else:
        prei=dic[t[i]][0]+1
        count+=N
    if i==len(t)-1:
        count+=prei



if count<=maxcount:
    print(count)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)

a=len(s)*len(t)
maxcount=len(s)
for i in range(100):
    if maxcount<a:
        maxcount**=10
    else:
        break


for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=1
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]
    else:
        prei=dic[t[i]][0]
        count+=N
    if i==len(t)-1:
        count+=prei



if count<=maxcount:
    print(count)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)
for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=1
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]
    else:
        prei=dic[t[i]][0]
        count+=N
    if i==len(t)-1:
        count+=prei
print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
s = input()
t = input()
set_t = set(t)
ss = ''
s2i = defaultdict(list)
for i, si in enumerate(s, 1):
    if si in set_t:
        ss += si
        s2i[si].append(i)
t2i = {k:0 for k in s2i.keys()}
tmi = {k:len(v) for k, v in s2i.items()}
lens = len(s)
if set(ss) != set_t:
    print(-1)
else:
    ans = 0
    pre_ii = 0
    for ti in t:
        i = t2i[ti]
        ii = s2i[ti][i]
        if ii < pre_ii:
            ans += lens-pre_ii + ii
        else:
            ans += ii - pre_ii
        if tmi[ti] >= t2i[ti]+1:
            t2i[ti] = 0
        else:
            t2i[ti] += 1
        pre_ii = ii
    print(ans)

Submission status: Wrong Answer

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

# s'は無限回繰り返されているとみなす
# sの中に含まれていない文字でtが構成されていたら速攻で-1

'''
1234567    ...                      33
contest contest contest contest contest contest
     s      e     nte     n     c   e

だけどcontestを無限に生成して、マッチングさせていくのでは最悪10**10になってTLEになってしまう。
貪欲を高速にやる必要あり。
つまりs'を回すんじゃなくて、tを回してできる方法を考える
t=sentenceなら 1文字目から次にsがでてくるのは5文字後、
6文字目から次にeが出てくるのは6文字後、
12文字目から...みたいに計算できる。 (12文字目は 12%7文字目に対応 (=0のときだけ7文字目に対応))

この操作に必要なのはsのi文字目(1-based-idx)において次に文字cが出てくるのは何文字後か、である。
'''

from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]
if set(t) - set(s):
    print(-1)
    exit()

# 前処理パート
S = s + s
# 逆向きから走査することでi文字目に置いて次にiが出てくるのはどこか見つける
tmp = {}  # いま文字keyが最後に出たのはいくつあとか
skiptable = [None] * (len(s) + 1)

# 前処理の前処理、
for i in range(len(S) - 1, -1, -1):
    moji = S[i]
    for key in tmp.keys():
        tmp[key] += 1  # すべて一文字あとになる
    if i < len(s):
        skiptable[i + 1] = tmp.copy()  # ミュータブルかつアドレス参照に注意
    tmp[moji] = 0  # その文字は0文字あとに修正


# 本処理
# 気をつける点としては、ttがちょうど見てる文字だった場合
#

now = 1
for tt in t:
    idx = now % len(s)
    idx = idx if idx else len(s)
    if s[idx - 1] == tt:
        now += 1
        flg = 1
    else:
        now += skiptable[idx][tt]
        flg = 0
print(now - flg)

Submission status: Wrong Answer

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

# s'は無限回繰り返されているとみなす
# sの中に含まれていない文字でtが構成されていたら速攻で-1

'''
1234567    ...                      33
contest contest contest contest contest contest
     s      e     nte     n     c   e

だけどcontestを無限に生成して、マッチングさせていくのでは最悪10**10になってTLEになってしまう。
貪欲を高速にやる必要あり。
つまりs'を回すんじゃなくて、tを回してできる方法を考える
t=sentenceなら 1文字目から次にsがでてくるのは5文字後、
6文字目から次にeが出てくるのは6文字後、
12文字目から...みたいに計算できる。 (12文字目は 12%7文字目に対応 (=0のときだけ7文字目に対応))

この操作に必要なのはsのi文字目(1-based-idx)において次に文字cが出てくるのは何文字後か、である。
'''

from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]
if set(t) - set(s):
    print(-1)
    exit()

# 前処理パート
S = s + s
# 逆向きから走査することでi文字目に置いて次にiが出てくるのはどこか見つける
tmp = {}  # いま文字keyが最後に出たのはいくつあとか
skiptable = [None] * (len(s) + 1)

# 前処理の前処理、
for i in range(len(S) - 1, -1, -1):
    moji = S[i]
    for key in tmp.keys():
        tmp[key] += 1  # すべて一文字あとになる
    if i < len(s):
        skiptable[i + 1] = tmp.copy()  # ミュータブルかつアドレス参照に注意
    tmp[moji] = 0  # その文字は0文字あとに修正

# # 存在しないが0文字目のための処理?
# for key in tmp.keys():
#     tmp[key] += 1  # すべて一文字あとになる
# if i < len(s):
#     skiptable[i + 1] = deepcopy(tmp)  # ミュータブルかつアドレス参照に注意


# 本処理
if len(t) == 1:
    print(skiptable[1][t])
    exit()


now = 1
for tt in t:
    idx = now % len(s)
    idx = idx if idx else len(s)
    now += skiptable[idx][tt]
print(now)