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:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

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


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

chars = set()
for t in T:
    chars.add(t)

chars = list(chars)
l = len(chars)
L1 = [0]*l
L2 = [[0 for _ in range(l)] for _ in range(l)]
W = S + S
for i in range(l):
    xi = W.find(chars[i])
    if xi == -1:
        print(-1)
        sys.exit()
    L1[i] = xi

for i in range(l):
    xi = L1[i]
    for j in range(l):
        yi = W[xi+1:].find(chars[j])
        if yi == -1:
            if i==j:
                L2[i][j] = len(S)
            else:
                L2[i][j] = W[0:xi].find(chars[j])
        else:
            L2[i][j] = yi+1

d = dict()
for i in range(len(chars)):
    d[chars[i]] = i

ans = L1[d[T[0]]]
prev = T[0]
for t in T[1:]:
    ans += L2[d[prev]][d[t]]
    prev = t

print(ans+1)

Submission status: Wrong Answer

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

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


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

chars = set()
for t in T:
    chars.add(t)

chars = list(chars)
l = len(chars)
L1 = [0]*l
L2 = [[0 for _ in range(l)] for _ in range(l)]
W = S + S
for i in range(l):
    xi = W.find(chars[i])
    if xi == -1:
        print(-1)
        sys.exit()
    L1[i] = xi

for i in range(l):
    xi = L1[i]
    for j in range(l):
        yi = W[xi+1:].find(chars[j])
        if yi == -1:
            L2[i][j] = len(S)
        else:
            L2[i][j] = yi+1

d = dict()
for i in range(len(chars)):
    d[chars[i]] = i

ans = L1[d[T[0]]]
prev = T[0]
for t in T[1:]:
    ans += L2[d[prev]][d[t]]
    prev = t

print(ans+1)

Submission status: Wrong Answer

Solution code:
import bisect

S = input().strip()
T = input().strip()

x = [[] for j in range(26)]

for i, s in enumerate(S):
    x[ord(s) - ord('a')].append(i)

sett = list(set(T))

for t in sett:
    if len(x[ord(t) - ord('a')]) == 0:
        print(-1)
        exit()

c = 0
z = 0

for t in T:
    y = bisect.bisect_left(x[ord(t) - ord('a')], c)
    if y == len(x[ord(t) - ord('a')]):
        z += 1
        c = x[ord(t) - ord('a')][0]
    else:
        c = x[ord(t) - ord('a')][y]

print(z * len(S) + c + 1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
lt = set(list(t))
ls = list(s)
ss = set(ls)
it = {}
mod = len(s)
p = -1
ans = 0
ind = 0
for x in lt:
    if x in ss: 
        if x not in it: it[x] = []
    else:
        print(-1)
        exit()
for i in range(len(s)):
    x = s[i]
    if x in it: it[x].append(i+1)
print(it)
for x in t:
    l = it[x]
    k = True
    for y in l:
        if ans % mod == mod - 1:
            ans = l[0]
        elif y >= ans % mod:
            ans = ans // mod * mod + y
            k = False
            break
        ans = l[0]
    if k:
        ind += 1
    #print(ans,ind,k)
print(ans + mod * ind)

Submission status: Wrong Answer

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

S = [ord(s)-97 for s in S]
T = [ord(t)-97 for t in T]

N = len(S)

dp = [[-1 for j in range(26)] for i in range(N)]

for i,s in enumerate(S):
    if dp[N-1][s] == -1:
        dp[N-1][s] = i

for i in range(N-2,-1,-1):
    for j in range(26):
        dp[i][j] = dp[i+1][j]
    dp[i][S[i+1]] = i+1

M = len(T)
ans = dp[N-1][T[0]] + 1
now = dp[N-1][T[0]]
if ans == -1:
    print(-1)
    exit()
for i in range(1,M):
    t = T[i]
    if dp[now][t] == -1:
        print(-1)
        exit()
    if now < dp[now][t]:
        ans += dp[now][t] - now
    else:
        ans += N + dp[now][t] - now
    now = dp[now][t]

print(ans)

Submission status: Wrong Answer

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

ans=0
s_inx=0
t_inx=0
s_l=len(s)
t_l=len(t)

c=0
while t_inx<=t_l-1:
  try:
    temp_inx=s[s_inx:].index(t[t_inx])
    s_inx+=temp_inx+1
    t_inx+=1
    c=0
  except:
    c+=1
    s_inx=0
    ans+=s_l

  if c==2:
    print(-1)
    exit()
else:
  ans+=s_inx+1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter, deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    D = {}
    for i in range(len(s)):
        if D.get(s[i]) is None:
            D[s[i]] = i

    cnt = 1
    pre = D.get(t[0], -1)
    if pre == -1:
        print(-1)
        exit()
    i = 1
    while i < len(t):
        idx = D.get(t[i], -1)
        if idx == -1:
            print(-1)
            exit()

        if idx < pre:
            cnt += 1
        pre = idx
        i += 1

    res = len(s) * cnt - (len(s) - 1 - D.get(t[-1]))
    print(res)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

ans=0
s_inx=0
t_inx=0
s_l=len(s)
t_l=len(t)

c=0
while t_inx<=t_l-1:
  try:
    temp_inx=s[s_inx:].index(t[t_inx])
    s_inx+=temp_inx
    t_inx+=1
    c=0
  except:
    c+=1
    s_inx=0
    ans+=s_l

  if c==2:
    print(-1)
    exit()
else:
  ans+=s_inx+1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

s=input()
t=input()
import collections
dic={}
lim={}
mod=len(s)
for ind,i in enumerate(s):
    if i not in dic:
        dic[i] = []
        lim[i] = 0
    dic[i].append(ind)
    lim[i] += 1
now=0
cnt=0
ok = True
import bisect
for i in t:
    if i not in dic:
        ok=False
        break
    ed = bisect.bisect_left(dic[i],now)
    if ed == lim[i]:
        cnt+=1
        now = dic[i][0]
    else:
        now = dic[i][ed]
    #print(now)
if ok==True:
    print(mod*cnt+now+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
lt = set(list(t))
ls = list(s)
ss = set(ls)
it = {}
mod = len(s)
p = -1
ans = 0
ind = 0
for x in lt:
    if x in ss: 
        if x not in it: it[x] = []
    else:
        print(-1)
        exit()
for i in range(len(s)):
    x = s[i]
    if x in it: it[x].append(i)
#print(it)
for x in t:
    l = it[x]
    k = True
    for y in l:
        if y >= ans % mod:
            ans = ans // mod * mod + y
            k = False
            break
        ans = l[0]
    if k:
        ind += 1
    #print(ans,ind,k)
print(ans + 1 + mod * ind)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()
ls = len(s)
sets = set(s)
sett = set(t)
ind = [[] for _ in range(26)]
temp = 0
ans = 0
if sett.issubset(sets) == False:
    print('-1')
else:
    for i in range(ls):
        ind[ord(s[i])-97].append(i+1)
    for x in t:
        if temp >= ind[ord(x)-97][-1]:
            ans += ls - temp + ind[ord(x)-97][0]
            temp = ind[ord(x)-97][0]
        else:
            bs = bisect.bisect_left(ind[ord(x)-97],temp)
            ans += ind[ord(x)-97][bs] - temp
            temp = ind[ord(x)-97][bs]
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()
ls = len(s)
sets = set(s)
sett = set(t)
ind = [[] for _ in range(26)]
temp = 0
ans = 0
if sett.issubset(sets) == False:
    print('-1')
else:
    for i in range(ls):
        ind[ord(s[i])-97].append(i+1)
    for x in t:
        if temp > ind[ord(x)-97][-1]:
            ans += ls - temp + ind[ord(x)-97][0]
            temp = ind[ord(x)-97][0]
        else:
            bs = bisect.bisect_left(ind[ord(x)-97],temp)
            ans += ind[ord(x)-97][bs] - temp
            temp = ind[ord(x)-97][bs]
    print(ans)

Submission status: Wrong Answer

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

cnt = 0
for i in s:
    d[i].append(cnt)
    ls = len(s)
    for j in range(1,len(t)*ls + 1):
        d[i].append(cnt+ls*j)
    cnt += 1

for k in d.keys():
    d[k].sort()
    
        
if not set(s) > set(t):
    print(-1)
else:
    now = -1
    for i in t:
        tmp = bisect.bisect_left(d[i], now)
        now = d[i][tmp]
    print(now+1)

Submission status: Wrong Answer

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

cnt = 0
for i in s:
    d[i].append(cnt)
    ls = len(s)
    for j in range(1,len(t)*ls + 1):
        d[i].append(cnt+ls*j)
    cnt += 1
    
    
if not set(s) > set(t):
    print(-1)
else:
    now = -1
    for i in t:
        while True:
            tmp = d[i].popleft()
            if tmp > now:
                now = tmp
                break
    print(now+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def main():
    S = input()
    T = input()
    lens = len(S)
    s = set(S)
    t = set(T)
    for i in t:
        if not i in s:
            return -2
    S = S + S
    alpha = [[] for i in range(26)]
    for i, v in enumerate(S):
        alpha[ord(v)-ord('a')].append(i)
    ans = 0
    idx = 0
    cnt = 0
    for i in T:
        # 二分探索で探す
        idx = bisect_left(alpha[ord(i)-ord('a')], idx)
        idx = alpha[ord(i)-ord('a')][idx]
        if idx >= lens:
            cnt += 1
            idx %= lens
        ans = cnt * lens + idx
    return ans

print(main()+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from bisect import bisect_right

def main():
    S = input()
    T = input()
    lens = len(S)
    s = set(S)
    t = set(T)
    for i in t:
        if not i in s:
            return -2
    S = S + S
    alpha = [[] for i in range(26)]
    for i, v in enumerate(S):
        alpha[ord(v)-ord('a')].append(i)
    ans = 0
    idx = 0
    cnt = 0
    for i in T:
        # 二分探索で探す
        idx = bisect_right(alpha[ord(i)-ord('a')], idx)
        if alpha[ord(i)-ord('a')][idx] >= lens:
            cnt += 1
        ans = cnt * lens + alpha[ord(i)-ord('a')][idx] % lens
        idx = alpha[ord(i)-ord('a')][idx] % lens
    return ans

print(main()+1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
if not set(t) <= set(s):
    print(-1)
    exit()
t_index = 0
cnt = 0
last = 0
while t_index < len(t) - 1:
    cnt += 1
    for i in range(len(s)):
        if t[t_index] == s[i]:
            t_index += 1
        if t_index == len(t):
            last = i
            break
print((cnt-1)*len(s)+last+1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
if not set(t) <= set(s):
    print(-1)
    exit()
t_index = 0
cnt = 0
last = 0
while t_index < len(t) - 1:
    cnt += 1
    for i in range(len(s)):
        if t[t_index] == s[i]:
            t_index += 1
        if t_index == len(t):
            last = i
            break
print(cnt*len(s)-(len(s)-cnt))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from bisect import bisect_left

s = readline().rstrip().decode()
t = readline().rstrip().decode()
al = defaultdict(list)
s_size = len(s)
for i, ss in enumerate(s):
    al[ss].append(i + 1)
cnt = 0
tmp = 0
memo = 0
for tt in t:
    memo = bisect_left(al[tt], tmp)
    if not al[tt]:
        print(-1)
        exit()
    if memo == len(al[tt]):
        memo = 0
        cnt += s_size
    cnt += al[tt][memo] - tmp
    tmp = al[tt][memo]
print(cnt)

Submission status: Wrong Answer

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]==[]):
    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: Wrong Answer

Solution code:
from collections import defaultdict
import bisect
S = input()
T = input()

d = defaultdict(list)

for i, s in enumerate(S):
    d[s].append(i)

ans = 0
now = -1
for t in T:
    arr = d[t]
    if len(arr) == 0:
        print(-1)
        exit()
    idx = bisect.bisect_left(arr, now)
    if idx == len(arr):
        ans += 1
        now = arr[0]
    else:
        now = arr[idx]
print(ans * len(S) + now + 1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
if not set(t) <= set(s):
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def main():
    s=input()
    t=input()
    s_abc=[]
    for i in range(26):
        s_abc.append([j for j,ss in enumerate(s) if ord(ss)==ord('a')+i])
    cur=0
    loop=0
    for tt in t:
        tt_num=ord(tt)-ord('a')
        if s_abc[tt_num]==[]:
            print(-1)
            sys.exit()
        next_idx=bisect.bisect(s_abc[tt_num],cur)
        if next_idx==len(s_abc[tt_num]) or s_abc[tt_num][next_idx]<=cur:
            loop+=1
            cur=s_abc[tt_num][0]
        else:
            cur=s_abc[tt_num][next_idx]
    print(len(s)*loop+cur+1)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def main():
    s=input()
    t=input()
    s_abc=[]
    for i in range(26):
        s_abc.append([j for j,ss in enumerate(s) if ord(ss)==ord('a')+i])
    cur=0
    loop=0
    for tt in t:
        tt_num=ord(tt)-ord('a')
        if s_abc[tt_num]==[]:
            print(-1)
            sys.exit()
        next_idx=bisect.bisect(s_abc[tt_num],cur)
        if next_idx==len(s_abc[tt_num]):
            loop+=1
            cur=s_abc[tt_num][0]
        else:
            cur=s_abc[tt_num][next_idx]
    print(len(s)*loop+cur+1)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
alphabet='abcdefghijklmnopqrstuvwxyz'
def alp2num(s):
  return alphabet.index(s)

s=input()
t=input()
n=len(s)

nums=[[-1]*26 for _ in range(n)]
for i in range(-1, -n, -1):
  nums[i-1]=nums[i]
  nums[i-1][alp2num(s[i])]=n+i
  
nums[-1]=nums[0]
nums[-1][alp2num(s[0])]=0
for i in range(-1, -n, -1):
  nums[i-1]=nums[i]
  nums[i-1][alp2num(s[i])]=n+i
    
ans=0
posi=-1
for c in t:
  if nums[posi][alp2num(c)]==-1:
    print(-1)
    exit()
  
  if posi>=nums[posi][alp2num(c)]:
    ans+=n
  posi=nums[posi][alp2num(c)]
  
print(ans+posi+1)

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
loc = [0]*len(t)
for i in range(len(t)):
  if t[i] in s:
    loc[i] = s.index(t[i])+1
  else:
    print(-1)
    exit()

#print(loc)
dp0=[0]*len(t)
dp1=[0]*len(t)
dp0[0]=loc[0]
dp1[0]=loc[0]
for i in range(1, len(t)):
  if loc[i]<dp1[i-1]:
    dp0[i]=dp0[i-1]+len(s)-loc[i-1]+loc[i]
  else:
    dp0[i]=dp0[i-1]+loc[i]-loc[i-1]
  dp1[i]=loc[i]
  
print(dp0[len(t)-1])
#print(dp1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i,i+len(s)]
    else:
        ma[each_s].append(i)
        ma[each_s].append(i+len(s))
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li,'tmp')

    lee = len(s_li)
    new_li = tmp_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min',lee)
    if min_index>= lee:
        repeat_count += 1
        min_index = new_li[0]
    elif min_index <= last_index:
        repeat_count += 1
        min_index = new_li[0]
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i,i+len(s)]
    else:
        ma[each_s].append(i)
        ma[each_s].append(i+len(s))
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li,'tmp')

    lee = len(s_li)
    new_li = tmp_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min',lee)
    if min_index>= lee:
        repeat_count += 1
        min_index -= lee
    elif min_index <= last_index:
        repeat_count += 1
        min_index = new_li[0]
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i,i+len(s)]
    else:
        ma[each_s].append(i)
        ma[each_s].append(i+len(s))
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li,'tmp')

    lee = len(s_li)
    new_li = tmp_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min',lee)
    if min_index>= lee:
        repeat_count += 1
        min_index -= lee
    elif min_index <= last_index:
        repeat_count += 1
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
ss = s+s
a = "abcdefghijklmnopqrstuvwxyz"
alphabet = {}
for i in range(26):
    alphabet[i] = a[i]
NEXT = [[-1]*len(s) for _ in range(26)]
cur = [0]*26
for i in range(len(ss)):
    index = ord(ss[i])-97
    if cur[index] < len(s):
        for j in range(cur[index],min(i,len(s))):
            NEXT[index][j] = i
            cur[index] = i
ans = 0
tmp = 0
for i in range(len(t)):
    char = ord(t[i])-97
    if NEXT[char][tmp] == -1:
        print(-1)
        exit()
    ans += NEXT[char][tmp]-tmp
    tmp = NEXT[char][tmp]
    if tmp >= len(s):
        tmp -= len(s)
print(ans+1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i,i+len(s)]
    else:
        ma[each_s].append(i)
        ma[each_s].append(i+len(s))
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li,'tmp')

    lee = len(s_li)
    new_li = tmp_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min',lee)
    if min_index>= lee:
        repeat_count += 1
        min_index -= lee
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
k = 0
q = 0
for i in range(len(T)):
    if S.count(T[i]) != 0:
        s = S.index(T[i])
        while True :
            if s > k:
                k = s
                break
            else:
                s += len(S)
    else:
        q = 1
        k = -2
        break
print(k+1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i]
    else:
        ma[each_s].append(i)
t = input()
t_li = list(t)
print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li)

    lee = len(s_li)
    add_li = [ii+lee for ii in tmp_li]
    new_li = tmp_li + add_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min')
    if min_index>= lee:
        repeat_count += 1
        min_index -= lee
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

Submission status: Wrong Answer

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

i=1
nextDic=[[-1]*27 for _ in range(len(s))]
cnt=0

tmp=[-1]*27
cnt=0
for i,ss in enumerate(s):
    if tmp[ord(ss)-97]==-1:
        tmp[ord(ss)-97]=i
        cnt+=1
    if cnt==27:
        break

nextDic[-1]=tmp
for i in range(1,len(s)):
    index=len(s)-i-1

    nextChar=ord(s[index+1])-97

    for j in range(len(nextDic[index])):
        if j==nextChar:
            nextDic[index][j]=index+1
        else:
            nextDic[index][j]=nextDic[index+1][j]

posi=0
result=1

flag=0

#print(nextDic)
cnt=0
for tt in t:
    ttt=ord(tt)-97
    tmp=nextDic[posi][ttt]
    #print(posi,">>",tmp)
    if posi==0 and flag==0 and tt==s[0]:
        posi=0
        flag=1
    else:
        if tmp==-1:
            print(-1)
            exit()
        if posi>=tmp:
            cnt+=1
        posi=tmp
    #print(result)

print(posi+1+len(s)*cnt)

Submission status: Wrong Answer

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

i=1
nextDic=[[-1]*27 for _ in range(len(s))]
cnt=0

for i,ss in enumerate(s):
    index=ord(ss)-97
    if nextDic[-1][index]==-1:
        nextDic[-1][index]=i
        cnt+=1
#print(nextDic)
#print("")    
for i in range(len(s)-1):
    index=len(s)-i-1
    ss=ord(s[index])-97

    for j in range(len(nextDic[index])):
        if nextDic[index][j]!=-1:
            if j!=ss:
                    nextDic[index-1][j]=nextDic[index][j]
            else:
                nextDic[index-1][j]=index
    #print(nextDic)
    #print("")

posi=0
result=1

flag=0

#print(nextDic)
cnt=0
for tt in t:
    ttt=ord(tt)-97
    tmp=nextDic[posi][ttt]
    #print(posi,">>",tmp)
    if posi==0 and flag==0 and tt==s[0]:
        posi=0
        flag=1
    else:
        if tmp==-1:
            print(-1)
            exit()
        if posi>=tmp:
            cnt+=1
        posi=tmp
    #print(result)

print(posi+1+len(s)*cnt)

Submission status: Wrong Answer

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

i=1
nextDic=[[-1]*27 for _ in range(len(s))]
cnt=0

for i,ss in enumerate(s):
    index=ord(ss)-97
    if nextDic[-1][index]==-1:
        nextDic[-1][index]=i
        cnt+=1
#print(nextDic)
#print("")    
for i in range(len(s)-1):
    index=len(s)-i-1
    ss=ord(s[index])-97

    for j in range(len(nextDic[index])):
        if nextDic[index][j]!=-1:
            if j!=ss:
                    nextDic[index-1][j]=nextDic[index][j]
            else:
                nextDic[index-1][j]=index
    #print(nextDic)
    #print("")

posi=0
result=1

flag=0

#print(nextDic)

for tt in t:
    ttt=ord(tt)-97
    tmp=nextDic[posi][ttt]
    #print(posi,">>",tmp)
    if posi==0 and flag==0 and tt==s[0]:
        posi=0
        flag=1
    else:
        if tmp==-1:
            print(-1)
            exit()
        if posi<tmp:
            result+=tmp-posi
        else:
            result+=len(s)+(tmp+1)-(posi+1)
        posi=tmp
    #print(result)

print(result)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()

d = dict()

for i, ch in enumerate(s):
    if ch in d:
        d[ch].append(i)
    else:
        d[ch] = [i]

ret = 0
cindex = -1

for ch in t:
    if ch not in d:
        print(-1)
        exit()
    else:
        ls = d[ch]
        index = bisect.bisect_right(ls, ret)
        index = 0 if (index == len(ls)) else index
        if cindex < ls[index]:
            ret += (ls[index] - cindex)
            cindex = ls[index]
        else:
            ret += len(s) + ls[index] - cindex
            cindex = ls[index]

print(ret)

Submission status: Wrong Answer

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

i=1
dic=[[] for _ in range(27)]
for ss in s:
    dic[ord(ss) - 97].append(i) 
    i+=1

for index,item in enumerate(dic):
    item.sort()
    dic[index]=item

posi=-1
count=0
for tt in t:
    if dic[ord(tt) - 97]==[]:
        print(-1)
        exit()
    
    flag=0
    if posi>dic[ord(tt) - 97][-1]:
        count+=1
        posi=dic[ord(tt) - 97][0]
    else:
        for item in dic[ord(tt) - 97]:
            if posi<item:
                posi=item
                break
    
print(count*len(s)+posi)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
x=dict()
for i in range(len(s)):
    x[s[i]]=0
for i in range(len(t)):
    if t[i] in x:
        x[t[i]]=1
    else:
        print(-1)
        exit()

S=[[]for _ in range(26)]
for i in range(len(s)):
    tmp=s[i]
    num=ord(tmp)
    num=num-97
    S[num].append(i+1)

chk=[0 for _ in range(26)]

ans=0
p=0
for i in range(len(t)):
    #print(ans)
    tmp=t[i]
    num=ord(tmp)
    num=num-97
    #print(S[num])
    #print(p)
    if len(S[num])==chk[num]:
        chk[num]=0

    if S[num][chk[num]]>p:
        ans+=(S[num][chk[num]]-p)
        p=S[num][chk[num]]
    else:
        sa=len(s)-p
        p=0
        ans+=sa
        ans+=(S[num][chk[num]]-p)
        p=S[num][chk[num]]
    chk[num]+=1

print(ans)

Submission status: Wrong Answer

Solution code:
# S.find()の部分を高速化する
from collections import defaultdict
from bisect import bisect_right
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    S = readline().strip()
    T = readline().strip()

    S_idx = defaultdict(list)
    for i, s in enumerate(S):
        S_idx[s].append(i)
    
    rep = 0
    last_idx = 0
    for t in T:
        t_idx_list = S_idx[t]
        if t_idx_list:
            t_idx = bisect_right(t_idx_list, last_idx)
            if t_idx < len(t_idx_list):
                last_idx = t_idx_list[t_idx]
            else:
                last_idx = t_idx_list[0]
                rep += 1
        else:
            print(-1)
            exit()
    
    ans = len(S) * rep + last_idx + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    S = readline().strip()
    T = readline().strip()

    seen = [0] * 26
    idx_in_S = []
    for t in T:
        ord_t = ord(t) - 97
        if seen[ord_t] == 0:
            t_idx = S.find(t) + 1
            if not t_idx:
                print(-1)
                exit()
            else:
                idx_in_S.append(t_idx)
                seen[ord_t] = t_idx
        else:
            begin = seen[ord_t]
            t_idx = S.find(t, begin) + 1
            if not t_idx:
                idx_in_S.append(seen[ord_t])
            else:
                idx_in_S.append(t_idx)
                seen[ord_t] = t_idx
    
    rep = 0
    for i in range(len(T) - 1):
        if idx_in_S[i] < idx_in_S[i+1]:
            continue
        else:
            rep += 1

    ans = len(S) * rep + idx_in_S[-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    S = readline().strip()
    T = readline().strip()

    idx_in_S = []
    for t in T:
        t_idx = S.find(t) + 1
        if not t_idx:
            print(-1)
            exit()
        else:
            idx_in_S.append(t_idx)
    
    rep = 0
    for i in range(len(T) - 1):
        if idx_in_S[i] < idx_in_S[i+1]:
            continue
        else:
            rep += 1

    ans = len(S) * rep + idx_in_S[-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
s=input()
t=input()
dic={}
n=len(s)
for i in range(n):
	if s[i] in dic:
		dic[s[i]].append(i)
	else:
		dic[s[i]]=[i]
k=0
r=0
for i in t:
	if i in dic:
		a=bisect_right(dic[i],k)
		if a==len(dic[i]):
			r+=1
			k=dic[i][0]
		else:
			k=dic[i][a]
	else:
		print(-1)
		exit()
print(r*n+k+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys

def solve():
    numChar = 26
    ordA = ord('a')

    Ss = input().rstrip()
    Ts = input().rstrip()

    lenS = len(Ss)
    Ss = [ord(S)-ordA for S in Ss]
    Ts = [ord(T)-ordA for T in Ts]

    setS, setT = set(Ss), set(Ts)
    for T in setT:
        if T not in setS:
            print(-1)
            sys.exit()

    posChs = [[] for _ in range(numChar)]
    for i, S in enumerate(Ss+Ss):
        posChs[S].append(i)
    for ch in range(numChar):
        print(ch, posChs[ch])

    ans = 0
    i = -1
    for T in Ts:
        iPos = bisect_right(posChs[T], i)
        i2 = posChs[T][iPos]
        ans += i2 - i
        i = i2 % lenS

    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys

def solve():
    numChar = 26
    ordA = ord('a')

    Ss = input().rstrip()
    Ts = input().rstrip()

    lenS = len(Ss)
    Ss = [ord(S)-ordA for S in Ss]
    Ts = [ord(T)-ordA for T in Ts]

    setS, setT = set(Ss), set(Ts)
    for T in setT:
        if T not in setS:
            print(-1)
            sys.exit()

    posChs = [[] for _ in range(numChar)]
    for i, S in enumerate(Ss+Ss):
        posChs[S].append(i)

    ans = 0
    i = 0
    for T in Ts:
        iPos = bisect_right(posChs[T], i)
        i2 = posChs[T][iPos]
        ans += i2 - i
        i = i2 % lenS

    print(ans+1)


solve()