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:
import bisect
import sys
def main():
    input = sys.stdin.readline
    s = input()[:-1]
    t = input()[:-1]
    S = "abcdefghijklmnopqrstuvwxyz"
    A = [[] for k in range(26)]
    for k in range(len(s)):
        A[S.index(s[k])].append(k+1)
    ans = 0
    now = 0
    for k in range(len(t)):
        if len(A[S.index(t[k])]) == 0:
            print(-1)
            exit(0)
        if max(A[S.index(t[k])]) <= now:
            ans += len(s)
            now = min(A[S.index(t[k])])
        else:
            now = A[S.index(t[k])][bisect.bisect_left(A[S.index(t[k])],now)]
    print(ans+now)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# kartikay26

from math import *
from collections import *
from itertools import *
from functools import *
from random import *
def getl(t=int): return [t(x) for x in input().split()]
def get(t=int): return t(input())
alphabet = [chr(x) for x in range(ord('a'), ord('z')+1)]
alnum = lambda x: ord(x) - ord('a')

def main():
	a = input()
	b = input()
	n = len(a)
	next_ = [next_arr(alphabet[i], a) for i in range(26)]
	ptr = -1
	ans = 0
	for ch in b:
		old_ptr = ptr
		ptr = next_[alnum(ch)][ptr]
		if ptr == -1:
			print(-1)
			exit()
		if ptr < old_ptr:
			ans += n
	print(ans+ptr+1)

def next_arr(ch, a):
	n = len(a)
	i = a.find(ch)
	if i == -1:
		return [-1] * n
	ret = [-1] * n
	while ret[prev(i,n)] == -1:
		if a[i] == ch:
			ret[prev(i,n)] = i
		else:
			ret[prev(i,n)] = ret[i]
		i = prev(i,n)
	return ret


def next(i, n):
	return (i+1) % n
def prev(i, n):
	return (i-1+n) % n

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:

s = list(input())
t = input()
tmp=0
ans=0
flag=True
for ch in t:
    if ch in s:
        indexes = [i for i, x in enumerate(s) if x == ch]
        if len(indexes)==1:
            if indexes[0]-tmp<=0:
                ans += indexes[0]+(len(s)-tmp)
            else:
                ans += (indexes[0]-tmp)
            tmp = indexes[0]
        else:
            cp = []
            for i in range(len(indexes)):
                if indexes[i]<=tmp:
                    cp.append(indexes[i]+len(s)-tmp)
                else:
                    cp.append(indexes[i]-tmp)
            ans += min(cp)
            tmp = indexes[cp.index(min(cp))]
    else:
        flag = False
if flag:
    print(ans+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
s = input() # 文字列を変数に格納
t = input() # 文字列を変数に格納

p = 0
count = 0

for i in range(len(t)):
    flag = 0
    for j in range(p,len(s)):
        if t[i] == s[j]:
            p = j
            flag = 1
            break
    if flag == 0:
        count += 1
        for j in range(p):
            if t[i] == s[j]:
                p = j
                flag = 1
                break
    if flag == 0:
        flag = 2
        break
        
if flag == 2:
    print(-1)
else:
    print(count*len(s) + p + 1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
s = input()
t = input()
sc = [ [] for _ in range(26)]

n = len(s)
for i in range(n):
    p = ord(s[i]) - ord('a')
    sc[p].append(i)

for c in t:
    p = ord(c) - ord('a')
    if len(sc[p]) == 0:
        print(-1)
        exit()

ans = 1
x = 0
for c in t:
    p = ord(c) - ord('a')
    if len(sc[p]) == 0:
        print(-1)
        exit()
    tmp = bisect_right(sc[p], x)
    if tmp == len(sc[p]):
        px = x
        x = sc[p][0]
        ans += n - px + x
    else:
        px = x
        x = sc[p][tmp]
        ans += x - px
print(ans)

Submission status: Wrong Answer

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

ans = []
for x in t:
  tmp = s.find(x)
  if tmp < 0:
    print('-1')
    sys.exit()
  else:
    index = -1
    tt =[]
    while True:
      index = s.find(x,index+1)
      if index>=0:
        tt.append(index)
      else:
        break
    ans.append(tt)

cnt = 0
end = []
for i in range(len(t)):
  end.append('0')
end[0] = min(ans[0])
for i in range(len(t)-1):
  if len(ans[i+1])>0:
    for ii in ans[i+1]:
      if end[i] < ii:
        end[i+1] = ii
        break
      else:
        end[i+1] = ii


cnt = 0
for i in range(len(end)-1):
  if end[i] >= end[i+1]:
    cnt += len(s)

cnt += end[len(end)-1]+1

print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left
from collections import defaultdict
INF = float("inf")


def solve(s: str, t: str):

    S = len(s)
    T = len(t)
    ABC = defaultdict(list)
    for i, c in enumerate(s):
        ABC[c].append(i)

    counter = 0
    head = 0
    # print(ABC)
    for tt in t:
        if len(ABC[tt]) == 0:
            print(-1)
            return
        j = bisect_left(ABC[tt], head) % len(ABC[tt])
        # print(tt, ABC[tt], j, ABC[tt][j], head)
        counter += (ABC[tt][j]-head+1) % S
        head = (ABC[tt][j]+1) % S
    print(counter)
    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: Wrong Answer

Solution code:
import numpy as np
s = input()
t = input()
i = 0
r = 1
n = len(s)

d = dict()
for x in t:
    if x not in d:
        d[x] = np.where(np.array(list(s)) == x)[0]
    if len(d[x]) == 0:
        r = -1
        break

if r != -1:
    for x in t:
        y = np.where(d[x]>i)[0]
        if len(y) == 0:
            r += n - i
            i = d[x][0]
            r += i
        else:
            j = d[x][y[0]]
            r += j - i
            i = j
print(r)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left


class Solution:
    def main(self):
        s = input()
        t = input()
        n = len(s)
        m = len(t)
        charpos = defaultdict(list)
        for i in range(n):
            charpos[s[i]].append(i)

        crrpos = 0
        loop = 0
        for j in range(m):
            if t[j] not in charpos:
                print(-1)
                return
            else:
                for pos in charpos[t[j]]:
                    if crrpos < pos:
                        crrpos = pos
                        break
                else:
                    loop += 1
                    crrpos = charpos[t[j]][0]

        print(loop*n + crrpos + 1)

if __name__ == '__main__':
    Solution().main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from copy import deepcopy


## input
def main():
  S = str(input())
  T = str(input())
  sdict = defaultdict(lambda:set([]))
  for i,s in enumerate(S):
    sdict[s].add(i)
  tdict = deepcopy(sdict)

  Tidx = [0 for _ in range(len(T)+1)]
  for i,t in enumerate(T):
    if len(sdict[t]) == 0:
      return -1
    else:
      if len(tdict[t]) == 0:
        tdict[t] = deepcopy(sdict[t])
      Tidx[i+1] = min(tdict[t])+1
      tdict[t].remove(Tidx[i+1]-1)

  ans = 0
  for i in range(1,len(Tidx)):
    if Tidx[i-1] < Tidx[i]:
      ans += Tidx[i]-Tidx[i-1]
    else:
      ans += len(S)-Tidx[i-1]+Tidx[i]
  return ans


if __name__ == "__main__":
  ans = main()
  print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    S = list(sys.stdin.readline().rstrip())
    T = list(sys.stdin.readline().rstrip())

    # 巻き戻る → 文字数分プラスする
    L = []
    for t in T:
        if t in S:
            si = S.index(t)
            L.append(si)
        else:
            print(-1)
            exit()

    prev = L[0]
    ans = 0
    Slen = len(S)

    for l in L[1::]:
        if prev > l:
            ans += Slen
        prev = l
    ans += (L[len(L) - 1] + 1)

    print(ans)

Submission status: Wrong Answer

Solution code:
alpha2num = lambda c: ord(c) - ord('a') 

s = list(input())
alpha = [[] for i in range(26)]
a = 'abcdefghijklmnopqrstuvwxyz'

for i in range(len(s)):
    alpha[alpha2num(s[i])].append(i)

#print(alpha)

t = list(input())
l = [0] * 26
ans = 0


s_unique = list(set(s))
t_unique = list(set(t))
check = 0
tmp = 0
#print(l)

for i in t_unique:
    if i in s_unique:
        pass
    else:
        check = 1

if check == 0:

    for i in range(len(t)):
        if i == 0:
            last = alpha[alpha2num(t[i])][l[alpha2num(t[i])]]
            l[alpha2num(t[i])] += 1
        else:
            if l[alpha2num(t[i])] >= len(alpha[alpha2num(t[i])]):
                l = [0] * 26
                l[alpha2num(t[i])] += 1
                last = tmp
                ans += 1
            else:
                tmp = alpha[alpha2num(t[i])][l[alpha2num(t[i])]]
                l[alpha2num(t[i])] += 1
#                print(tmp)
                if tmp < last:
                    l = [0] * 26
                    last = tmp
                    ans += 1
                else:
                    last = tmp

#    print(ans)
    print(max(ans * len(s) + tmp + 1, len(s)))

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys

s = input()
t = input()

a = []
ls = len(s)
lt = len(t)

for i in t:
    try:
        a.append(s.index(i))
    except:
        print("-1")
        sys.exit()

p = 0
q = 0

for i in range(lt):
    if i > 0:
        if i == lt - 1:
            q = a[i]
            if a[i - 1] > a[i]:
                p += 1
        else:
            if a[i - 1] > a[i]:
                p += 1
            else:
                q = a[i]
    else:
        q = a[i]

if p > 99:
    print("-1")
else:
    ans = p * ls + q + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    s = input()
    t = input()
    count = 0
    keys = list(set(s))
    D = dict(zip(keys, [[] for _ in range(len(keys))]))
    for ss in s:
        D[ss].append(count)
        count += 1
    tmp = 0
    count = 0
    for tt in range(len(t)):
        if t[tt] in keys:
            # print(tmp, count)
            flag = 1
            for dd in D[t[tt]]:
                if tmp < dd:
                    tmp = dd
                    flag = 0
                    break
            if flag:
                tmp = D[t[tt]][0]
                count += 1
        else:
            print(-1)
            exit()
    print(count * len(s) + tmp + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
a = [0]
ans = 0
lens = len(s)
lent = len(t)


for i in range(lent):
  a.append(s.find(t[i]))
  
if(-1 in a):
  print(-1)
else:
  for i in range(lent):
    if(a[i] > a[i+1]):
      ans += (lens + a[i+1] - a[i])
    else:
      ans += (a[i+1] - a[i])
  print(ans+1)

Submission status: Wrong Answer

Solution code:
s = list(str(input()))
t = list(str(input()))
sdic = {}

ans = 0
sin_ = 0
for i in t:
  if i in s[sin_:]:
    s_ = s[sin_:].index(i) + 1
    sin = sin_ + s_
    sin_ = sin
    ans += s_
  elif i in s:
    s_ = s.index(i) + 1
    sin = s_
    if sin_ < sin:
      ans += (sin - sin_)
      sin_ = sin
    else:
      ans += (len(s) - sin + sin)
      sin_ = sin
  else:
    ans = -1
    break
print(ans)

Submission status: Wrong Answer

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

print(s)

Trigger=True
OK=False
count=0

while Trigger:
    Trigger=False
    for i in range(len(s)):
        if len(t)==0:
            OK=True
            break
        elif s[i]==t[0]:
            del t[0]
            Trigger=True
        count+=1  
        
if OK:
    print(count)
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()

#len_s = len(s)

#alpha2num = lambda c: ord(c) - ord('a')

results = {}
for i in range(len(s)):
    results.setdefault(s[i], []).append(i+1)

#print(results)

ans = 0
cnt = 0
num = 1

for i in range(len(t)):
    #キーがない場合は-1を出力
    if not t[i] in results.keys():
        print(-1)
        exit()
    else:
        idx = bisect.bisect_right(results[t[i]],cnt)
        #print(ans, len(results[t[i]]) , idx)
        if len(results[t[i]]) <= idx:
            cnt = results[t[i]][0]
            ans = len(s)*num + cnt
            num += 1
        else:
            #print(results[t[i]][idx],results[t[i]])
            cnt = results[t[i]][idx] - cnt
            ans += cnt
            
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import *

S = input()
T = input()

ds = {}
for i,s in enumerate(S) :
    if s not in ds :
        ds[s] = [i]
    else :
        ds[s].append(i)
L = []
ind = -1
flg = 0
for t in T :
    if t not in ds :
        ans = -1
        flg = 1
        break
if flg == 0 :
    for t in T :
        if ind >= ds[t][-1] :
            ind = ds[t][0]
            L.append(ind)
        else :
            ind = ds[t][bisect_right(ds[t], ind)]
            L.append(ind)

    cnt = 0
    val = L[0]
    for i in range(1,len(L)) :
        if val >= L[i] :
            val = L[i]
            cnt += 1

    ans = cnt * len(S) + L[-1] + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math 
s = str(input())
t = str(input())
cnt_s = 0
cnt_t = 0
result = 0

while cnt_s != int(len(s)):
	if s[cnt_s] == t[cnt_t]:
		cnt_s = cnt_s + 1
	
	cnt_t = cnt_t + 1
	if cnt_t == int(len(t)):
		cnt_t = 0
	result = result + 1

print(result)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
s = input()
t = input()

ds = defaultdict(int)
for i in range(len(s)):
    ds[s[i]] += 1
dt = defaultdict(int)
for i in range(len(t)):
    dt[t[i]] += 1

possible = True
for ti in dt:
    if ti not in ds:
        possible = False
        break


if possible:
    n = len(s)
    m = len(dt)
    edge = []
    for i in range(n):
        if s[i] in dt:
            edge.append((s[i], i))
    l = len(edge)
    # for i in range(len(edge)):
    #     dist = 0
    #     for j in range(1, len(edge)+1):
    #         k = (i + j) % len(edge)
    #         if edge[k][0] not in edge[i][2]:
    #             if i == k:
    #                 edge[i][2][ edge[k][0] ] = (n, k)
    #             else:
    #                 edge[i][2][ edge[k][0] ] = ((edge[k][1] - edge[i][1] + n) % n, k)
    #         if len(edge[i][2]) == m:
    #             break

    # for i in range(len(edge)):
    #     print(edge[i])

    ans = x = 0
    for i in range(n):
        if s[i] == t[0]:
            ans = i + 1
            break
    for i in range(len(edge)):
        if edge[i][0] == t[0]:
            x = i
            break

    for i in range(1, len(t)):
        x_pre = x
        while edge[x][0] != t[i]:
            x += 1
            x %= l
        if x == x_pre:
            ans += n
        else:
            ans += (n + edge[x][1] - edge[x_pre][1]) % n
else:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
ans=0
s1=s
ans=0
flag=1
for i in t:
    if i not in s1:
        flag=0
if flag==0:
    print(-1)
else:
    for i in t:
        if i in s1:
            ans+=s1.index(i)+1
            s1=s1[s1.index(i)+1:]
        else:
            ans = (ans//len(s)+1)*len(s) 
            ans+=s.index(i)+1   
            s1=s[s.index(i)+1:]
    print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意


ss = input()
t = input()

s = ss+ss


l = len(s)
d = [[-1]*26 for _ in range(l)]
now = [-1]*27

ans = -1
for i,c in enumerate(s):
    for j in range(26):
        if now[j] == -1: continue
        if d[now[j]][ord(c)-97] == -1:
            d[now[j]][ord(c)-97] = i
    now[ord(c)-97] = i
            
#print(now)
#print(d)

ans = ss.find(t[0])
if ans == -1:
    print(-1)
    exit()

ls = len(ss)
#print(ans)
lt = len(t)-1

res = ans
for i in range(lt):
#    print(res, d[res])
    if d[res][ord(t[i+1])-97] == -1:
        print(-1)
        exit()
    diff = d[res][ord(t[i+1])-97] - res 
    ans += diff
    res = (res+diff)%ls


print(ans+1)

Submission status: Wrong Answer

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

s_len = len(s)
t_len = len(t)

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

def get_ord(c):
    return ord(c)-97

for i in range(s_len):
    ord_c = get_ord(s[i])
    n[ord_c].append(i)

#print(n)

#print("s_len",s_len)
#print("t_len",t_len)

def get_ans():
    res = 0
    for i in range(t_len):
        rr = res % s_len
        t_ord = get_ord(t[i])
        words = n[t_ord]
        if(len(words)==0):
            return -1
        if(words[len(words)-1]<=rr):
            res += s_len - rr 
            #print("add",s_len-rr)
            rr = -1
        
        bis = bisect.bisect_right(words,rr)
        #print(bis,len(words),rr,words)
        w = words[bis]
        if(rr!=-1):
            res += w - rr
        else:
            res += w
        #print(t[i],words,rr,res)
    
    return res+1

print(get_ans())

Submission status: Wrong Answer

Solution code:
import collections

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

    ns, nt = len(s), len(t)
    cs, ct = set(list(s)), set(list(t))
    for c in ct:
        if c not in cs: return -1

    d = collections.defaultdict(list)
    for i in range(ns):
        if s[i] in ct: d[s[i]].append(i)

    i = 0
    for c in t:
        while d[c][0] <= i:
            d[c].append(d[c].pop(0)+ns)
        i = d[c][0]
    return i+1


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from copy import deepcopy


## input
def main():
  S = str(input())
  T = str(input())
  sdict = defaultdict(lambda:set([]))
  for i,s in enumerate(S):
    sdict[s].add(i)
  tdict = deepcopy(sdict)

  Tidx = [0 for _ in range(len(T)+1)]
  for i,t in enumerate(T):
    if len(sdict[t]) == 0:
      return -1
    else:
      if len(tdict[t]) == 0:
        tdict[t] = deepcopy(sdict[t])
      Tidx[i+1] = min(tdict[t])+1
      tdict[t].remove(Tidx[i+1]-1)

  ans = 0
  for i in range(1,len(Tidx)):
    if Tidx[i-1] < Tidx[i]:
      ans += Tidx[i]-Tidx[i-1]
    else:
      ans += len(S)-Tidx[i-1]+Tidx[i]-1
  return ans


if __name__ == "__main__":
  ans = main()
  print(ans)

Submission status: Wrong Answer

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

def search_index(t_atom, last_index):
    for j in range(last_index, len(s)):
        if t_atom == s[j]:
            return j
    for j in range(0, last_index):
        if t_atom == s[j]:
            return j

    return -1

def solve():
    last_index = 0
    t_index = []
    loop_cost = 1


    for i in range(len(t)):
        t_atom = t[i]
        t_atom_index = search_index(t_atom, last_index)
        if t_atom_index == -1:
            return -1
        else:
            t_index.append(t_atom_index)
            last_index = t_atom_index

    remainder_cost = t_index[-1] + 1

    for i in range(1, len(t)):
        if t_index[i - 1] >= t_index[i]:
            loop_cost += 1

    return len(s) * (loop_cost - 1) + remainder_cost

print(solve())

Submission status: Wrong Answer

Solution code:

from bisect import bisect_left
s= input()
t = input()

d = {}
n = len(s)
ans = 0
for i in range(len(s)):
    if s[i] not in d:
        d[s[i]] = [i+1]
    else:
        d[s[i]].append(i+1)

flag = True
bef = 0
for c in t:
    if c not in d:
        flag = False
        break
    else:
        temp = bisect_left(d[c],bef)
        if temp == len(d[c]):
            temp = d[c][0]
            ans += temp + (n-bef)
            bef = temp
        else:
            temp = d[c][temp]
            ans += temp-bef
            bef = temp
    # print(ans)
if flag:
    print(ans)
else:
    print(-1)




# arr = [0,2,4]
# print(bisect_left(arr,1))
# print(bisect_left(arr,5))
# print(bisect_left(arr,3))

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
for i in T:
    if i not in S:
        print(-1)
        exit()

N = len(S)
nex = [[N] * 26 for i in range(N + 1)]
for i in range(N - 1, -1, -1):
    for j in range(26):
        nex[i][j] = nex[i + 1][j]
    nex[i][ord(S[i]) - ord('a')] = i


M = len(T)
i = 0
num = 0
j = 0
while j < M:
    if nex[i][ord(T[j]) - ord('a')] < N:
        num += nex[i][ord(T[j]) - ord('a')] - i
        i = nex[i][ord(T[j]) - ord('a')]
        j += 1
    else:
        num += N - i
        i = 0

print(num + 1)

Submission status: Wrong Answer

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

s = input().strip()
t = input().strip()
n = len(s)
m = len(t)
p = 0
q = 0
fold = 0
l = [[] for _ in range(26)]
lim = [0 for _ in range(26)] 
for i, x in enumerate(s):
	l[ord(x) - 97].append(i)
	lim[ord(x) - 97] += 1
r = [0 for _ in range(26)]
cur = -1
while (q < m):
	x = t[q]
	ind = ord(x) - 97
	#print(x, cur)
	if l[ind] == []:
		print(-1)
		exit(0)
	else:
		#print("HERE", r[ind], lim[ind])
		if r[ind] >= lim[ind]:
			fold += 1
			r = [0 for _ in range(26)]
			cur = -1
		else:
			c = l[ind][r[ind]]
			while (c <= cur and r[ind] < lim[ind]):
				c = l[ind][r[ind]]
				r[ind] += 1
			if c > cur:
				cur = c
				q += 1
				r[ind] += 1
			else:
				fold += 1
				r = [0 for _ in range(26)]
				cur = -1
#print(fold, n, cur)
print(fold * n + cur + 1)

Submission status: Wrong Answer

Solution code:
import bisect as bs

def main():
	s = input()
	t = input()
	indx = [[] for _ in range(26)]
	count = [0 for _ in range(26)]
	loop = 0
	pre = -1
	lens = len(s)
	for i in range(lens):
		c = ord(s[i])-97
		indx[c] += [i]
		count[c] += 1
	for i in range(len(t)):
		c = ord(t[i])-97
		if indx[c] == []:
			print(-1)
			return
		ref = bs.bisect(indx[c],pre)
		if indx[c][ref%count[c]] < pre:
			loop += 1
		pre = indx[c][ref%count[c]]
		# print(pre)
	print(loop*lens + pre+1)

main()

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
lens=len(s)
lent=len(t)
d = {}

for i in range(lens):
    if s[i] in d:
        d[s[i]].append(i)
    else:
        d[s[i]] = [i]

tmp=0
r=0
snum=0
for i in range(lent):
    if d.get(t[i],None)==None:
        print("-1")
        exit()
    else:
        lis=d[t[i]]
        lis.sort()
        r = bisect.bisect_right(lis,tmp)
        if(len(lis) <= r):
            snum+=lens
            tmp=lis[0]
        else:
            tmp=lis[r]
print(snum+tmp+1)

Submission status: Wrong Answer

Solution code:

from bisect import bisect_right as br

def main():
    S = [s for s in input()]
    T = [t for t in input()]
    slen = len(S)
    tlen = len(T)

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

    ans = 0
    pre = 0
    if T[0] in dic:
        if T[0] != S[0]:
            ans = dic[T[0]][0]
    else:
        print(-1)
        return 
    
    for j in range(1,tlen):
        t = T[j]
        if t in dic:
            point = br(dic[t],pre)
            if point == len(dic[t]):
                ans += slen - pre + dic[t][0]
                pre = dic[t][0]
            else:
                if pre == dic[t] == point:
                    ans += slen
                else:
                    ans += dic[t][point] - pre
                    pre = dic[t][point]
        else:
            print(-1)
            return
    print(ans + 1)
    return 
main()

Submission status: Wrong Answer

Solution code:
from bisect import *

S = input()
T = input()

ds = {}
for i,s in enumerate(S) :
    if s not in ds :
        ds[s] = [i]
    else :
        ds[s].append(i)
L = []
ind = 0
flg = 0
for t in T :
    if t not in ds :
        ans = -1
        flg = 1
        break
if flg == 0 :
    for t in T :
        if ind >= ds[t][-1] :
            ind = ds[t][0]
            L.append(ind)
        else :
            ind = ds[t][bisect_left(ds[t], ind)]
            L.append(ind)

    cnt = 0
    val = L[0]
    for i in range(1,len(L)) :
        if val >= L[i] :
            val = L[i]
            cnt += 1

    ans = cnt * len(S) + L[-1] + 1
print(ans)

Submission status: Wrong Answer

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

if not set(S) >= set(T):
    print(-1)
    exit()

str_repeat_num = 0
now_idx = 0
for t in T:
    for i, s in enumerate(S[now_idx:]):
        if t == s:
            now_idx = i + 1 + now_idx
            break
    else:
        str_repeat_num += 1
        for i, s in enumerate(S[:now_idx]):
            if t == s:
                now_idx = i + 1
print(len(S) * str_repeat_num + now_idx)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 昇順にソート済みのarrから、n以上の最小の要素を探索して返します。
# 存在しない場合は、Noneを返します。
def bin_gte(arr, n):
    l = 0
    r = len(arr) - 1
    c = (l+r)//2
    while l < r:
        c = (l+r)//2
        if arr[c] >= n:
            r = c
        else :
            l = c+1
    c = max(0, (l+r)//2)
    if arr[c] >= n:
        return (c, arr[c])
    else:
        return None


s = input()
t = input()
n = len(s)
m = len(t)
appears = [ [] for _ in range(26)]
for i,app in enumerate(appears):
    char = chr(ord('a') + i)
    base = 0
    while True:
        f = s.find(char, base)
        if f == -1:
            break
        app.append(f)
        base = f+1

cur = 0
loop = 0
for char in t:
    appear = appears[ord(char) - ord('a')]
    if len(appear) == 0:
        print('-1')
        exit()

    nex = bin_gte(appear, cur)

    if nex == None:
        loop += 1
        cur = appear[0]
    else:
        cur = nex[1]

print(loop * n + cur + 1)

# print(appears)
# print(appears[ord('t') - ord('a')])

Submission status: Wrong Answer

Solution code:
alpha2num = lambda c: ord(c) - ord('a') 

s = list(input())
alpha = [[] for i in range(26)]
a = 'abcdefghijklmnopqrstuvwxyz'

for i in range(len(s)):
    alpha[alpha2num(s[i])].append(i)

print(alpha)

t = list(input())
l = [0] * 26
ans = 0


s_unique = list(set(s))
t_unique = list(set(t))
check = 0
tmp = 0
print(l)

for i in t_unique:
    if i in s_unique:
        pass
    else:
        check = 1

if check == 0:

    for i in range(len(t)):
        if i == 0:
            last = alpha[alpha2num(t[i])][l[alpha2num(t[i])]]
        else:
            if l[alpha2num(t[i])] >= len(alpha[alpha2num(t[i])]):
                l = [0] * 26
                last = tmp
                ans += 1
            else:
                tmp = alpha[alpha2num(t[i])][l[alpha2num(t[i])]]
                l[alpha2num(t[i])] += 1
                print(tmp)
                if tmp < last:
                    l = [0] * 26
                    last = tmp
                    ans += 1
                else:
                    last = tmp

#    print(ans)
    print(max(ans * len(s) + tmp + 1, len(s)))

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
s="contest"
t="programming"

jisho={}
alphabets = [chr(ord('a') + i) for i in range(26)]
for moji in alphabets:
    jisho[moji] = [i for i,x in enumerate(s) if x==moji]

lis = [jisho[moji] for moji in t]
if [] in lis:
    print(-1)
else:
    old=-1
    order=[]
    for i,cand in enumerate(lis):
        
        tes = [temp for temp in cand if temp>old]
        if len(tes)==0:
            ans = min(cand)
        else:
            ans = min(tes)
        old=ans
        order.append(ans)
    
    old=-1
    count=0
    for i,num in enumerate(order):
        if num<=old: count+=1
        old=num
    print(count*len(s)+order[-1]+1)

Submission status: Wrong Answer

Solution code:
# kartikay26

from math import *
from collections import *
from itertools import *
from functools import *
from random import *
def getl(t=int): return [t(x) for x in input().split()]
def get(t=int): return t(input())
alphabet = [chr(x) for x in range(ord('a'), ord('z')+1)]
alnum = lambda x: ord(x) - ord('a')

def main():
	a = input()
	b = input()
	n = len(a)
	next_ = [next_arr(alphabet[i], a) for i in range(26)]
	ptr = 0
	ans = 0
	for ch in b:
		old_ptr = ptr
		ptr = next_[alnum(ch)][ptr]
		if ptr == -1:
			print(-1)
			exit()
		if ptr < old_ptr:
			ans += n
	print(ans+ptr+1)

def next_arr(ch, a):
	n = len(a)
	i = a.find(ch)
	if i == -1:
		return [-1] * n
	ret = [-1] * n
	while ret[prev(i,n)] == -1:
		if a[i] == ch:
			ret[prev(i,n)] = i
		else:
			ret[prev(i,n)] = ret[i]
		i = prev(i,n)
	return ret


def next(i, n):
	return (i+1) % n
def prev(i, n):
	return (i-1+n) % n

if __name__ == "__main__":
	main()