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:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())



def run():
    S, T = input(), input()
    dic = defaultdict(lambda : [])
    for i, s in enumerate(S):
        dic[s].append(i)

    k = 0
    ans = 1
    for t in T:
        if t in dic.keys():
            i = bisect.bisect_right(dic[t], k)
            if i >= len(dic[t]):
                k = dic[t][0]
                ans += 1
            else:
                k = dic[t][i]

        else:
            print(-1)
            return

    print((ans-1) * len(S) + k +1)


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()

Submission status: Wrong Answer

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

def s2n(s):
    return ord(s)-97

ALF=[[] for _ in [0]*26]
for i in range(len(S)):
    ALF[s2n(S[i])].append(i)

ALF_T=[0]*26
seqT=[]
res=0
for t in T:
    i=s2n(t)
    if ALF[i]:
        seqT.append(ALF[i][ALF_T[i]])
        ALF_T[i]=(ALF_T[i]+1)%(len(ALF[i]))
    else:
        res=-1
if res>=0:
    tmp=[]
    m=-1
    for n in seqT:
        if m<n:
            tmp.append(n)
        else:
            res+=1
            tmp=[n]
        m=n
    res=res*len(S)+tmp[-1]+1
print(res)

Submission status: Wrong Answer

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

n = len(s)
m = len(t)
s += s
next = [[-1] * 26 for _ in range(len(s) + 1)]

# 場所iから、次の文字jへの場所、みたいなテーブル
# 後ろから更新してくと最短距離になる
# next[i]は場所iを含む
for i in range(len(s) - 1, -1, -1):
    c = ord(s[i]) - ord('a')
    for j in range(26):
        if j == c:
            next[i][j] = i
        else:
            next[i][j] = next[i + 1][j]
now = 0
ans = 0
for i in range(m):
    c = ord(t[i]) - ord('a')
    if next[i][c] == -1:
        print(-1)
        exit()
    ans += next[now][c] - now + 1
    now = next[now][c] + 1
    if now >= n:
        now -= n
print(ans)

Submission status: Wrong Answer

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

n = len(s)
m = len(t)
s += s
next = [[-1] * 26 for _ in range(len(s) + 1)]

# 場所iから、次の文字jへの場所、みたいなテーブル
# 後ろから更新してくと最短距離になる
for i in range(len(s) - 1, -1, -1):
    c = ord(s[i]) - ord('a')
    for j in range(26):
        if j == c:
            next[i][j] = i
        else:
            next[i][j] = next[i + 1][j]
now = 0
ans = 0
for i in range(m):
    c = ord(t[i]) - ord('a')
    if next[i][c] == -1:
        print(-1)
        exit()
    ans += next[now][c] - now
    now = next[now][c]
    if now >= n:
        now -= n
print(ans + 1)

Submission status: Wrong Answer

Solution code:
import itertools
s = input()
t = input()
ss = set(s)
st = set(t)
ans = -1
if (ss & st != st):
  print(-1)
else:
  x = [[] for _ in range(len(s))]
  for i in range(len(t)):
    ind = s.index(t[i])
    x[ind].append(i)
  fx = list(itertools.chain.from_iterable(x))
  cnt = 0
  for i in range(1,len(fx)):
    if fx[i]<fx[i-1]:
      cnt += 1
  m = max(fx)
  mi = 0
  for i in range(len(x)):
    if m in x[i]:
      mi = i
  print(len(s)*cnt + mi+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()

n = len(s)

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

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

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

Submission status: Wrong Answer

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

X = [[] for _ in range(26)]
for i, c in enumerate(s):
    j = ord(c)-ord('a')
    X[j].append(i)

ans = 0
import bisect
cur = -1
for c in t:
    j = ord(c)-ord('a')
    if len(X[j]) == 0:
        print(-1)
        exit()
    k = bisect.bisect_left(X[j], cur)
    if k != len(X[j]):
        cur = X[j][k]
    else:
        cur = X[j][0]
        ans += len(s)
ans += cur+1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *

s,t = input(),input()
before,count = len(s),0
idx = defaultdict(list)

if not set(t) <= set(s):
  print("-1")
  exit()

for i,l in enumerate(s):
  idx[l] += [i]
  
for c in t:
  N = idx[c]
  index = bisect_left(N, before)
  if index > len(N) - 1:
    before = N[0]
    count += 1
  else:
    before = N[index]
    
print((count - 1) * len(s) + before + 1)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()
if set(list(s + t)) != set(list(s)):
    print(-1)
    exit()
check = set(list(t))
dic = {}
for Str in check:
    dic[Str] = []
for i in range(len(s)):
    if s[i] in check:
        dic[s[i]] += [i]
times = 0
now = 0
for p in t:
    if now >= dic[p][-1]:
        now = dic[p][0]
        times += 1
    else:
        now = dic[p][bisect.bisect(dic[p], now)]
print(len(s) * times + now + 1)

Submission status: Wrong Answer

Solution code:
import bisect

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

sdic={}
for idx,i in enumerate(s*2):
  if i in sdic.keys():
    sdic[i].append(idx)
  else:
    sdic[i]=[idx]

    
ans=k=0
for i in t:
  if i not in sdic.keys():
    print(-1)
    exit()
  t=bisect.bisect_left(sdic[i], ans%n)
  if len(sdic[i])==t:
    t=0
    k+=n
  ans=sdic[i][t]+k
  
print(ans+1)

Submission status: Wrong Answer

Solution code:
import string
import bisect
s=input()
t=input()
S=[[] for _ in range(26)]
a=string.ascii_lowercase
now=-1
ans=-1
count=0
for i in range(len(s)):
    for j in range(26):
        if s[i]==a[j]:
            S[j].append(i)
            break
for i in range(len(t)):
    for j in range(26):
        if t[i]==a[j]:
            break
    if len(S[j])==0:
        break
    nex=bisect.bisect_left(S[j],now)
    if nex==len(S[j]) or now>=S[j][nex]:
        count+=1
        now=S[j][0]
    else:
        now=S[j][nex]
    if i==len(t)-1:
        ans=count*(len(s))+now+1
print(ans)

Submission status: Wrong Answer

Solution code:
import string
import bisect
s=input()
t=input()
S=[[] for _ in range(26)]
a=string.ascii_lowercase
now=0
ans=-1
count=0
for i in range(len(s)):
    for j in range(26):
        if s[i]==a[j]:
            S[j].append(i)
            break
for i in range(len(t)):
    for j in range(26):
        if t[i]==a[j]:
            break
    if len(S[j])==0:
        break
    nex=bisect.bisect_left(S[j],now)
    if nex==len(S[j]) or now>=S[j][nex]:
        count+=1
        now=S[j][0]
    else:
        now=S[j][nex]
    if i==len(t)-1:
        ans=count*(len(s))+now+1
print(ans)

Submission status: Wrong Answer

Solution code:
import string
import bisect
s=input()
t=input()
S=[[] for _ in range(26)]
a=string.ascii_lowercase
now=0
ans=-1
count=0
for i in range(len(s)):
    for j in range(26):
        if s[i]==a[j]:
            S[j].append(i)
            break
for i in range(len(t)):
    for j in range(26):
        if t[i]==a[j]:
            break
    if len(S[j])==0:
        break
    nex=bisect.bisect_left(S[j],now)
    if nex==len(S[j]):
        count+=1
        now=S[j][0]
    else:
        now=S[j][nex]
    if i==len(t)-1:
        ans=count*(len(s))+now+1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()
n = len(s)
s0 = {}
for i in range(n):
    s0.setdefault(s[i], [])
    s0[s[i]].append(i)
print(s0)
num1 = 0
num2 = -1
flag = True
for i in t:
    if i not in s:
        flag = False
        break
    num = bisect.bisect_right(s0[i], num2)
    if num == len(s0[i]):
        num1 += 1
        num2 = s0[i][0]
    else:
        num2 = s0[i][num]
    print(num1, num2)
if flag == True:
    print(num1 * n + num2 + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()
n = len(s)
s0 = {}
for i in range(n):
    s0.setdefault(s[i], [])
    s0[s[i]].append(i)
num1 = 0
num2 = 0
flag = True
for i in t:
    if i not in s:
        flag = False
        break
    num = bisect.bisect_right(s0[i], num2)
    if num == len(s0[i]):
        num1 += 1
        num2 = s0[i][0]
    else:
        num2 = s0[i][num]
if flag == True:
    print(num1 * n + num2 + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
"""
tの先頭から、できるだけ長い文字列を一回のsで消費するゲーム
できるだけ短い時間で、残っているtの先頭からどこまでを一回で消費できるかを判断したい。
部分文字列DPのときにやったみたいに、ns[i][j] => i番目より後ろで、つぎに文字jが出てくるインデックス
という表を作っておけばよい。
"""

S = input()
T = input()
N = len(S)
dp = [[-1]*26 for _ in range(N+1)]
for i in range(N):
    s = S[i]
    dp[i][ord(s)-ord("a")] = i+1

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

cycleCnt = 0
sInd = 0
for i in range(len(T)):
    if dp[sInd][ord(T[i])-ord("a")] == -1:
        cycleCnt += 1
        sInd = 0
        if dp[sInd][ord(T[i])-ord("a")] == -1:
            print(-1)
            exit()
    sInd = dp[sInd][ord(T[i])-ord("a")]
if cycleCnt >= 100:
    print(-1)
else:
    print(cycleCnt*N+sInd)

Submission status: Wrong Answer

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


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

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


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

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

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

Submission status: Wrong Answer

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


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

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


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

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

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

Submission status: Wrong Answer

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

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

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

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


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

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

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

Submission status: Wrong Answer

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

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

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

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


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

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

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

Submission status: Wrong Answer

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

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

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

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


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

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

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

Submission status: Wrong Answer

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

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

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


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

ans=[]
tmp=0
for i in range(len_t):
    idx=ord(t[i])-97
    if len(pos[idx])==0:
        print(-1)
        exit()

    if tmp<pos[idx][-1]:
        l=0
        r = len(pos[idx]) - 1
        while l + 1 < r:
            mid = (l + r) // 2
            if pos[idx][mid] <= tmp:
                l = mid
            else:
                r=mid
        ans.append(pos[idx][r])
        tmp=pos[idx][r]
    else:
        ans.append(pos[idx][0])
        tmp=pos[idx][0]

cnt=0
for i in range(1,len_t):
    if ans[i-1]>=ans[i]:
        cnt+=1

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

Submission status: Wrong Answer

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

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

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


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

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

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

Submission status: Wrong Answer

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

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

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


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

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

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

Submission status: Wrong Answer

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

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

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


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

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

Submission status: Wrong Answer

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

from collections import Counter
from collections import deque

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

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

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

abc="abcdefghijklmnopqrstuvwxyz"
C=[deque([]) for _ in range(26)]
for i in range(Ls):
        C[abc.index(s[i])].append(i)

Nt=[]
idx=C[abc.index(t[0])].popleft()
Nt.append(idx)
C[abc.index(t[0])].append(idx+Ls)

for j in range(1,Lt):
    idx=C[abc.index(t[j])].popleft()
    while idx<=Nt[-1]:
        idx+=Ls
    Nt.append(idx)
    C[abc.index(t[j])].append(idx+Ls)

print(Nt[-1]+1)

Submission status: Wrong Answer

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

from collections import Counter
from collections import deque

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

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

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

abc="abcdefghijklmnopqrstuvwxyz"
C=[deque([]) for _ in range(26)]
for i in range(Ls):
        C[abc.index(s[i])].append(i)

Nt=[]
for j in range(Lt):
    idx=C[abc.index(t[j])].popleft()
    Nt.append(idx)
    C[abc.index(t[j])].append(idx)

cnt=0
for k in range(1,Lt):
    if Nt[k-1]>=Nt[k]:
        cnt+=1

print(cnt*Ls+Nt[-1]+1)

Submission status: Wrong Answer

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

Ls=len(s)
Lt=len(t)
from collections import deque

q=deque(t)
cnt1=0
now=q.popleft()
while q:
    cnt2=0
    for i in range(Ls):
        cnt2+=1
        if s[i]==now:
            if not q:
                ans=cnt1*Ls+cnt2
                print(ans)
                exit()
            else:
                now=q.popleft()
    cnt1+=1
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

def main():
    S = input()
    T = input()
    Ls = len(S)
    Lt = len(T)
    d = defaultdict(list)
    for i in range(Ls):
        d[S[i]].append(i+1)

    now = 0
    loop = 0
    for t in T:
        if not d[t]:
            print(-1)
            exit()
        ni = bisect_left(d[t], now)
        if ni > len(d[t]) - 1:
            now = 0
            loop += 1
            ni = bisect_left(d[t], now)
            now = d[t][ni]
        else:
            now = d[t][ni]

    ans = loop * Ls + now
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

def main():
    S = input()
    T = input()
    Ls = len(S)
    Lt = len(T)
    d = defaultdict(list)
    for i in range(Ls):
        d[S[i]].append(i+1)

    now = 0
    ans = 0
    flag = False
    for i in range(Lt):
        if not d[T[i]]:
            print(-1)
            exit()
        ni = bisect_left(d[T[i]], now)
        if ni >= len(d[T[i]]):
            now = 0
            ans += Ls
            ni = bisect_left(d[T[i]], now)
            now = d[T[i]][ni]

        else:
            now = d[T[i]][ni]

    ans += now
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque
from bisect import *
alphabets = list("abcdefghijklmnopqrstuvwxyz")
s = input()
t = input()
cs = Counter(list(s))
ct = Counter(list(t))
for char in alphabets:
    if ct[char] > 0 and cs[char]==0:
        print(-1)
        exit()

l_s = len(s)
l_t = len(t)
ss = list(s+s)
c2loc = {char: [] for char in alphabets}
for i in range(l_s*2):
    c2loc[ss[i]].append(i)

ans = 0
now = -1
for i in range(l_t):
    target = t[i]
    target_idxes = c2loc[target]
    idx = bisect_left(target_idxes, now)
    ans += target_idxes[idx] - now
    now = target_idxes[idx]%l_s
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque
alphabets = list("abcdefghijklmnopqrstuvwxyz")
s = input()
t = input()
cs = Counter(list(s))
ct = Counter(list(t))
for char in alphabets:
    if ct[char] > 0 and cs[char]==0:
        print(-1)
        exit()

l_s = len(s)
l_t = len(t)
c2loc = {char: deque() for char in alphabets}
for i in range(l_s):
    c2loc[s[i]].append(i)

ans = 0
now = -1
i = 0
while i < l_t:
    target = t[i]
    target_idx = c2loc[target].popleft()
    if target_idx > now:
        ans += target_idx - now
        now = target_idx
        c2loc[target].append(target_idx)
        i += 1
    else:
        c2loc[target].append(target_idx)
        c2loc[target] = deque(sorted(list(c2loc[target])))
        ans += (l_s - now - 1)
        now = -1
        # c2loc[target].append(target_idx)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter, deque
alphabets = list("abcdefghijklmnopqrstuvwxyz")
s = input()
t = input()
cs = Counter(list(s))
ct = Counter(list(t))
for char in alphabets:
    if ct[char] > 0 and cs[char]==0:
        print(-1)
        exit()

l_s = len(s)
l_t = len(t)
c2loc = {char: deque() for char in alphabets}
for i in range(l_s):
    c2loc[s[i]].append(i)

ans = 0
now = -1
for i in range(l_t):
    target = t[i]
    target_idx = c2loc[target].popleft()
    if target_idx > now:
        ans += target_idx - now
        now = target_idx
        c2loc[target].append(target_idx)
    else:
        ans += target_idx + (l_s - now)
        now = target_idx
        c2loc[target].append(target_idx)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


s = S()
t = S()
set_s = set(s)
set_t = set(t)
if (set_t <= set_s) is False:
    print(-1)
    exit()
alphabet2index = defaultdict(list)
for i, alphabet in enumerate(s):
    alphabet2index[alphabet].append(i+1)
ans = 0
pos = 0
prev_pos = 0
base = 0
for _t in t:
    ng_flg = True
    while ng_flg:
        pos_lis = alphabet2index[_t]
        i = 0
        while len(pos_lis) > i:
            if (pos_lis[i] >= pos):
                pos = pos_lis[i]
                ans += (pos_lis[i]-prev_pos)
                # print(pos_lis[i], prev_pos, )
                prev_pos = pos
                ng_flg = False
                break
            i += 1
        else:
            prev_pos = pos - len(s)
            # print(prev_pos)
            # print('base', base)
            pos = 0

print(ans)

Submission status: Wrong Answer

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

qs = [[1] for i in range(26)]
for i in range(len(s)):
    qs[ord(s[i]) - ord("a")].append(i)
    
ans = 1
x = 0

for i in range(len(t)):

    
    if len(qs[ord(t[i]) - ord("a")]) >= 2:
        
        a = qs[ord(t[i]) - ord("a")][0]
        
        
        if qs[ord(t[i]) - ord("a")][0] >= len(qs[ord(t[i]) - ord("a")]):
            qs[ord(t[i]) - ord("a")][0] = 1
            a = 1
        

        if qs[ord(t[i]) - ord("a")][a] >= x:
            

            ans -= x
            ans += qs[ord(t[i]) - ord("a")][a]
            x = qs[ord(t[i]) - ord("a")][a]
            
            qs[ord(t[i]) - ord("a")][0] += 1
            
                
        else:
            ans -= x
            ans += len(s)
            qs[ord(t[i]) - ord("a")][0] = 1
            x = qs[ord(t[i]) - ord("a")][1]
            ans += x
            qs[ord(t[i]) - ord("a")][0] += 1

            
    else:
        ans = -1
        break

print(ans)

Submission status: Wrong Answer

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

qs = [[1] for i in range(26)]
for i in range(len(s)):
    qs[ord(s[i]) - ord("a")].append(i)
qt = [[1] for i in range(26)]
for i in range(len(t)):
    qt[ord(t[i]) - ord("a")].append(i)
    
ans = 1
x = -1


for i in range(len(t)):
    
    if len(qs[ord(t[i]) - ord("a")]) >= 2:
        
        a = qs[ord(t[i]) - ord("a")][0]

        if qs[ord(t[i]) - ord("a")][a] > x:
            if i != 0:
                ans -= x
            ans += qs[ord(t[i]) - ord("a")][a]
            x = qs[ord(t[i]) - ord("a")][a]
            
            qs[ord(t[i]) - ord("a")][0] += 1
            if qs[ord(t[i]) - ord("a")][0] >= len(qs[ord(t[i]) - ord("a")]):
                qs[ord(t[i]) - ord("a")][0] = 1
                
        else:
            ans -= x
            ans += len(s)
            qs[ord(t[i]) - ord("a")][0] = 1
            x = qs[ord(t[i]) - ord("a")][1]
            ans += x

            
    else:
        ans = -1
        break

print(ans)

Submission status: Wrong Answer

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

qs = [[1] for i in range(26)]
for i in range(len(s)):
    qs[ord(s[i]) - ord("a")].append(i)
qt = [[1] for i in range(26)]
for i in range(len(t)):
    qt[ord(t[i]) - ord("a")].append(i)
    
ans = 1
x = 0

for i in range(len(t)):
    
    if len(qs[ord(t[i]) - ord("a")]) >= 2:
        
        a = qs[ord(t[i]) - ord("a")][0]

        if qs[ord(t[i]) - ord("a")][a] >= x:
            
            ans -= x
            ans += qs[ord(t[i]) - ord("a")][a]
            x = qs[ord(t[i]) - ord("a")][a]
            
            qs[ord(t[i]) - ord("a")][0] += 1
            if qs[ord(t[i]) - ord("a")][0] >= len(qs[ord(t[i]) - ord("a")]):
                qs[ord(t[i]) - ord("a")][0] = 1
                
        else:
            ans -= x
            ans += len(s)
            qs[ord(t[i]) - ord("a")][0] = 1
            x = qs[ord(t[i]) - ord("a")][1]
            ans += x

            
    else:
        ans = -1
        break

print(ans)

Submission status: Wrong Answer

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

qs = [[1] for i in range(26)]
for i in range(len(s)):
    qs[ord(s[i]) - ord("a")].append(i)
qt = [[1] for i in range(26)]
for i in range(len(t)):
    qt[ord(t[i]) - ord("a")].append(i)
    
ans = 1
x = 0


for i in range(len(t)):
    
    if len(qs[ord(t[i]) - ord("a")]) >= 2:
        
        a = qs[ord(t[i]) - ord("a")][0]

        if qs[ord(t[i]) - ord("a")][a] > x:
            
            ans -= x
            ans += qs[ord(t[i]) - ord("a")][a]
            x = qs[ord(t[i]) - ord("a")][a]
            
            qs[ord(t[i]) - ord("a")][0] += 1
            if qs[ord(t[i]) - ord("a")][0] >= len(qs[ord(t[i]) - ord("a")]):
                qs[ord(t[i]) - ord("a")][0] = 1
                
        else:
            ans -= x
            ans += len(s)
            qs[ord(t[i]) - ord("a")][0] = 1
            x = qs[ord(t[i]) - ord("a")][1]
            ans += x

            
    else:
        ans = -1
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

# d := {"a":[], "b":[], ..., "z":[]}
d = {}
key = list("abcdefghijklmnopqrstuvwxyz")
for i in range(26):
    d[key[i]] = []

# 1文字ずつ分割してリスト化
S = list(input())
N = len(S)

T = list(input())
M = len(T)

for i in range(N):
    d[S[i]].append(i)

# print(d)

S_set = set(S)

ans = 0
now = 0
# Tの1文字目, 2文字目, ...
for i in range(M):
    if T[i] in S_set:
        next = bisect.bisect_left(d[T[i]], now)
        # print("i,next = ", i, next)
        # 右端ではない場合
        if next < len(d[T[i]]):
            now = d[T[i]][next]
        # 右端になる場合
        else:
            now = d[T[i]][0]
            ans += N
    else:
        print(-1)
        exit()

ans += now+1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

# d := {"a":[], "b":[], ..., "z":[]}
d = {}
key = list("abcdefghijklmnopqrstuvwxyz")
for i in range(26):
    d[key[i]] = []

# 1文字ずつ分割してリスト化
S = list(input())
N = len(S)

T = list(input())
M = len(T)

for i in range(N):
    d[S[i]].append(i)

# print(d)

S_set = set(S)

ans = 0
now = 0
# Tの1文字目, 2文字目, ...
for i in range(M):
    if T[i] in S_set:
        next = bisect.bisect_right(d[T[i]], now)
        # print("i,next = ", i, next)
        # 右端ではない場合
        if next < len(d[T[i]]):
            now = d[T[i]][next]
        # 右端になる場合
        else:
            now = d[T[i]][0]
            ans += N
    else:
        print(-1)
        exit()

ans += now
ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import*
s=input()
t=input()
n=len(s)
d=dict(zip([chr(i+97) for i in range(26)],[[] for _ in range(26)]))
for i,j in enumerate(s,1):
  d[j]+=[i]
ans=0
cnt=0
for i in t:
  if d[i]:
    j=bisect_left(d[i],ans)
    if j==len(d[i]):
      cnt+=1
      ans=d[i][0]
    else:ans=d[i][j]
  else:
    cnt,ans=0,-1
    break
print(cnt*n+ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
dic = defaultdict(list)
s = input()
t = input()
n = len(s)
for i in range(n):
    dic[s[i]].append(i+1)

#print(dic)

for i in t:
    if dic[i]==[]:
        print(-1)
        sys.exit()
        
ans = dic[t[0]][0]

if len(t)==1:
    print(ans)
    sys.exit()

count=0
#print(ans)
for i in range(1, len(t)):
    if ans >= dic[t[i]][-1]:
        count += 1
        ans = dic[t[i]][-1]
    elif ans < dic[t[i]][0]:
        ans = dic[t[i]][0]
    else:
        sm = 0
        la = len(dic[t[i]])-1
        while sm+1<la:
            mi = (sm + la)//2
            if ans >= mi:
                sm = mi
            else:
                la = mi
        ans = dic[t[i]][la]
#print("ans:{}, count:{}, n:{}".format(ans, count, n))
print(ans+count*n)