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:
# https://atcoder.jp/contests/abc138/tasks/abc138_e

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

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

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

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

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

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

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

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


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


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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left
S = input()
sl = len(S)
T = input()
t = set(T)
dic = defaultdict(list)
for c in t:
  for i, m in enumerate(S):
    if m==c:
      dic[c] += [i]
  if dic[c]==[]:
    print(-1)
    import sys
    sys.exit()
p = -1
ans = 0
for c in T:
  if p>dic[c][-1]:
    ans += sl-1-p
    p = -1
  ind = bisect_left(dic[c],p)
  ans += dic[c][ind]-p
  p = dic[c][ind]
print(ans)

Submission status: Wrong Answer

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

# 構成不可
if set(list(T)) - set(list(S)):
    print(-1)
    exit()


# 各文字の出現場所を記録
D = defaultdict(list)
for i, s in enumerate(S):
    D[s].append(i)


ans = 0
marker = 0
for t in T:
    target_char_appeared_indexes = D[t]
    bi = bisect_left(target_char_appeared_indexes, marker)
    # もう一周してこないと見つけられない
    if bi == len(target_char_appeared_indexes):
        ans += NS
        marker = target_char_appeared_indexes[0]
    else:
        marker = target_char_appeared_indexes[bi]


# 0-indexedのため+1
print(ans + marker + 1)

Submission status: Wrong Answer

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

if set(s) >= set(t):
    d = [s.find(x) for x in t]
    cnt = 0
    tmp = -1
    for x in d:
        if tmp >= x:
            cnt += 1
        tmp = x

    print(len(s) * cnt + tmp + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
n = len(S)
m = len(T)
set_S = set(list(S))
for i in range(m):
    if T[i] not in set_S:
        print(-1)
        exit()

# 必ず再現できることが確定
res = [[n]*26 for _ in range(n+1)]
for i in reversed(range(n)):
    for j in range(26):
        res[i][j] = res[i+1][j]
    res[i][ord(S[i])-ord("a")] = i

# print(*res, sep="\n")
cnt = 0
tmp = 0
for i in range(m):
    tmp += 1  # 次の文字へ
    if tmp == n or res[tmp][ord(T[i])-ord("a")] == n:  # そのループで現れない場合次のループに進む
        cnt += n
        tmp = 0
    tmp = res[tmp][ord(T[i])-ord("a")]  # T[i]が現れる場所がわかる
cnt += tmp+1
print(cnt)

Submission status: Wrong Answer

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

# Sのi文字目以降で最初に文字Cが登場するindex
res = [[n]*26 for _ in range(n+1)]
for i in reversed(range(n)):
    for j in range(26):
        res[i][j] = res[i+1][j]  # 一旦そのままの値を引き継いだ後に、今みているS[i]については若い番号で更新する
    res[i][ord(S[i])-ord("a")] = i  # 今後ろから見ていて、同じアルファベットが前の方で見つかったらより若い番号で更新されていく

# 与えられているのはindex
# nにはアクセスできないから、今後現れない文字はnで与えられている
# str_list = [chr(i + ord('a')) for i in range(26)]
# str_list = ' '.join(str_list)
# print(str_list)
# for r in res:
#     print(r)
# nに辿り着いたら26で割った余りを足す
cnt = 0
tmp = 0
for i in range(len(T)):
    # T[i]を探しにいく
    if tmp == n:
        cnt += n
        tmp = 0
    elif res[tmp % n][ord(T[i])-ord("a")] == n:  # もうそのループでは見つからないなら
        if tmp == 0:
            print(-1)
            exit()
        cnt += n
        tmp = 0
    tmp = res[tmp % n][ord(T[i])-ord("a")]  # 0が手に入る
    tmp += 1
cnt += tmp
print(cnt)

Submission status: Wrong Answer

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

# Sのi文字目以降で最初に文字Cが登場するindex
res = [[n]*26 for _ in range(n+1)]
for i in reversed(range(n)):
    for j in range(26):
        res[i][j] = res[i+1][j]  # 一旦そのままの値を引き継いだ後に、今みているS[i]については若い番号で更新する
    res[i][ord(S[i])-ord("a")] = i  # 今後ろから見ていて、同じアルファベットが前の方で見つかったらより若い番号で更新されていく

# 与えられているのはindex
# nにはアクセスできないから、今後現れない文字はnで与えられている
# str_list = [chr(i + ord('a')) for i in range(26)]
# str_list = ' '.join(str_list)
# print(str_list)
# for r in res:
#     print(r)
# nに辿り着いたら26で割った余りを足す
cnt = 0
tmp = 0
for i in range(len(T)):
    # T[i]を探しにいく
    if res[tmp % n][ord(T[i])-ord("a")] == n:  # もうそのループでは見つからないなら
        if tmp == 0:
            print(-1)
            exit()
        cnt += n
        tmp = 0
    tmp = res[tmp % n][ord(T[i])-ord("a")]  # 5が手に入る
    tmp += 1
cnt += tmp
print(cnt)

Submission status: Wrong Answer

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

# Sのi文字目以降で最初に文字Cが登場するindex
res = [[n]*26 for _ in range(n+1)]
for i in reversed(range(n)):
    for j in range(26):
        res[i][j] = res[i+1][j]  # 一旦そのままの値を引き継いだ後に、今みているS[i]については若い番号で更新する
    res[i][ord(S[i])-ord("a")] = i  # 今後ろから見ていて、同じアルファベットが前の方で見つかったらより若い番号で更新されていく

# 与えられているのはindex
# nにはアクセスできないから、今後現れない文字はnで与えられている
str_list = [chr(i + ord('a')) for i in range(26)]
str_list = ' '.join(str_list)
# print(str_list)
# for r in res:
#     print(r)
# nに辿り着いたら26で割った余りを足す
cnt = 0
tmp = 0
for i in range(len(T)):
    # T[i]を探しにいく
    if res[tmp % n][ord(T[i])-ord("a")] == n:  # もうそのループでは見つからないなら
        if tmp % n == 0:
            print(-1)
            exit()
        cnt += n
        tmp = 0
    tmp = res[tmp % n][ord(T[i])-ord("a")]  # 5が手に入る
    tmp += 1
cnt += tmp
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

def main():
    S = input()
    T = input()
    d = defaultdict(list)
    for i, s in enumerate(S):
        d[s].append(i+1)
    pre = 0
    cnt = 0
    loop = 0
    len_S = len(S)
    for t in T:
        if not d[t]:
            print(-1)
            exit()
        index = bisect_left(d[t],pre)
        if index > len(d[t])-1:
            pre = 0
            loop += 1
            index = bisect_left(d[t],pre)
        pre = d[t][index]
        
    ans = loop * len_S + pre
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()
d = defaultdict(list)
e = defaultdict(int)

a, b = set(s), set(t)
if a&b!=b:
    print(-1)
else:
    for i,j in enumerate(s):
        d[j].append(i)
        e[j]+=1
    
    p = -1
    orig_size = len(s)
    ans = 0

    for i in t:
        a = bisect_left(d[i], p)
        if 0<= a < e[i]:
            p = d[i][a]
        else:
            p = d[i][0]
            ans += orig_size
    
    print(ans+p+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

S = input()
T = input()
a = 97

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

glen = [0] * 26
for idx, g in enumerate(grid):
    glen[idx] = len(g)

cnt = 0
cur = 0
for t in T:
    t = ord(t) - a
    if glen[t]:
        pos = bisect_left(grid[t], cur)
        if pos == glen[t]:
            cnt += 1
            cur = grid[t][0]
        else:
            cur = grid[t][pos]
    else:
        cnt = 0
        cur = -2
        break

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

Submission status: Wrong Answer

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

s=list(map(lambda x : ord(x)-97,list(input())))
t=list(map(lambda x : ord(x)-97,list(input())))
#print(s)

alpha=[[] for i in range(26)]
#print(alpha)

for index,item in enumerate(s):
    alpha[item].append(index)
    #print(alpha)

loc=-1
count=0

for index,item in enumerate(t):
    temp=bisect.bisect_left(alpha[item],loc)
    if len(alpha[item])==0:
        print(-1)
        exit()
    if temp==len(alpha[item]):
        count+=1
        loc=alpha[item][0]
    else:
        loc=alpha[item][temp]
    #print(loc,count)
print(loc+1+count*len(s))

Submission status: Wrong Answer

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

# next[i][c] = k : i文字目以降で最初にcが現れるのはk文字目 である (i < |s|)
N = len(s)
next = [dict() for _ in range(N)]
last = dict()
for i, c in enumerate(s + s):
    last_c = last[c] if last.get(c) is not None else -1
    for j in range(last_c + 1, min(i + 1, N)):
        next[j][c] = i % N
    last[c] = i

i = -1
for c in t:
    cur = i % N
    if next[cur].get(c) is None:
        print(-1)
        exit(0)
    n = next[cur][c]
    if cur < n:
        i += n - cur
    elif n < cur:
        i += N - (cur - n)
    else:
        i += N
print(i + 1)

Submission status: Wrong Answer

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

# next[i][c] = k : i文字目以降で最初にcが現れるのはk文字目 である (i < |s|)
N = len(s)
next = [dict() for _ in range(N)]
last = dict()
for i, c in enumerate(s + s):
    last_c = last[c] if last.get(c) is not None else -1
    for j in range(last_c + 1, min(i + 1, N)):
        next[j][c] = i % N
    last[c] = i

i = 0
for c in t:
    cur = i % N
    if next[cur].get(c) is None:
        print(-1)
        exit(0)
    n = next[cur][c]
    if cur < n:
        i += n - cur
    elif n < cur:
        i += N - (cur - n)
    else:
        i += N
print(i + 1)

Submission status: Wrong Answer

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

# next[i][c] = k : i文字目以降で最初にcが現れるのはk文字目 である (i < |s|)
N = len(s)
next = [dict() for _ in range(2 * N)]
last = dict()
for i, c in enumerate(s + s):
    last_c = last[c] if last.get(c) is not None else -1
    for j in range(last_c + 1, i + 1):
        next[j][c] = i
    last[c] = i

i = 0
for c in t:
    cur = i % N
    if next[cur].get(c) is None:
        print(-1)
        exit(0)
    n = next[cur][c]
    i += n - cur
print(i + 1)

Submission status: Wrong Answer

Solution code:
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    m = 0
    j = 0
    for i in t:
        ind = bisect.bisect_left(d[i], j)
        m += d[i][ind] - j + 1
        if d[i][ind] >= n:
            j = d[i][ind] - n + 1
        else:
            j = d[i][ind] + 1
    return m
print(main())

Submission status: Wrong Answer

Solution code:
def main():
    S = list(map(lambda x: ord(x) - 97, input()))
    T = list(map(lambda x: ord(x) - 97, input()))
    if not set(T) <= set(S):
        return -1

    tbl = [-1] * 26
    st = [None] * (len(S) + 1)
    for i, s in reversed(list(enumerate(S))):
        st[i + 1] = tuple(tbl)
        tbl[s] = i
    st[0] = tuple(tbl)
    r = 0
    c = 0
    for t in T:
        if st[r][t] == -1:
            c += 1
            r = 0
        r = st[r][t]
    return c * len(S) + r + 1

print(main())

Submission status: Wrong Answer

Solution code:
import bisect
INF = 10 ** 10
s = input()
t = input()
moji = [[] for _ in range(26)]

for i, m in enumerate(s):
    moji[ord(m) - ord("a")].append(i)

for i in range(26):
    moji[i].sort()

moji_o = [0 for _ in range(len(t))]

cnt = 0
ans = 1
for i, m in enumerate(t):
    if len(moji[ord(m) - ord("a")]) == 0:
        ans = -1
        break
    if i == 0:
        moji_o[i] = moji[ord(m) - ord("a")][0]
    else:
        if moji_o[i - 1] > moji[ord(m) - ord("a")][-1]:
            moji_o[i] =  moji[ord(m) - ord("a")][0]
        else:
            tmp = bisect.bisect_left(moji[ord(m) - ord("a")], moji_o[i - 1])
            if tmp == 0:
                moji_o[i] = moji[ord(m) - ord("a")][0]
            else:
                moji_o[i] = moji[ord(m) - ord("a")][tmp]

for i in range(1, len(moji_o)):
    if ans == -1:
        break
    if moji_o[i - 1] >= moji_o[i]:
        cnt += 1

if ans == -1:
    print(-1)
else:
    print(cnt * len(s) + moji_o[-1] + 1)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10
s = input()
t = input()
moji = [INF for _ in range(26)]

for i, m in enumerate(s):
    moji[ord(m) - ord("a")] = min(moji[ord(m) - ord("a")], i)

moji_o = [0 for _ in range(len(t))]
for i, m in enumerate(t):
    moji_o[i] = moji[ord(m) - ord("a")]


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

if sum(moji_o) >= INF:
    print(-1)
else:
    print(cnt * len(s) + moji_o[-1] + 1)

Submission status: Wrong Answer

Solution code:
import bisect
a = input()
b = input()
dp = [[] for _ in range(26)]
# print(dp)

for e,i in enumerate(a):
    t=ord(i)-ord('a')
    dp[t].append(e)
# print(dp)
f = 0
ans = 0
c = 0 
for e,i in enumerate(b):
    t = ord(i)-ord('a')
    if not dp[t]:
        print(-1)
        exit()
    i_i = bisect.bisect_left(dp[t],f)
    if len(dp[t])<=i_i:
        F = dp[t][0] 
        ans+=F+1
        c +=1
    else:
        F = dp[t][i_i]
        ans += F-f+1
    f = F
    # print(dp[t],f,F,ans)
    if e == len(b)-1: ans = c*len(a)+ F+1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
for i in range(N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
ans = 0
now = 0
jud = numpy.array([[0,len(lis[i])] for i in range(26)])
for i in range(len(t)):
    alp = ord(t[i])-97
    if jud[alp,0] >= jud[alp,1]:
        ans += N - now
        jud[:,0] = 0
        now = 0
    if lis[alp][jud[alp,0]] <= now:
        ans += N - now
        jud[:,0] = 0
        now = 0
    ans += lis[alp][jud[alp,0]]-now
    now = lis[alp][jud[alp,0]]
    jud[alp,0] += 1
print(ans)

Submission status: Wrong Answer

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

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

    s_indexes = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, s_c in enumerate(s):
        s_indexes[s_c].append(i)
    s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
    s_length = {c: len(s_indexes[c]) for c in "abcdefghijklmnopqrstuvwxyz"}

    power = 0
    last_index = -1
    for i, t_c in enumerate(t):
        if s_length[t_c] <= s_pointer[t_c]:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1
        elif s_indexes[t_c][s_pointer[t_c]] <= last_index:
            for j in range(last_index, s_pointer[t_c]):
                if last_index < s_indexes[t_c][j]:
                    s_pointer[t_c] = j
                    break
            else:
                # reset
                s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
                power += 1

        last_index = s_indexes[t_c][s_pointer[t_c]]
        s_pointer[t_c] += 1

    print(len(s) * power + last_index + 1)


main()

Submission status: Wrong Answer

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

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

    s_indexes = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, s_c in enumerate(s):
        s_indexes[s_c].append(i)
    s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
    s_length = {c: len(s_indexes[c]) for c in "abcdefghijklmnopqrstuvwxyz"}

    power = 0
    last_index = -1
    for i, t_c in enumerate(t):
        if s_length[t_c] <= s_pointer[t_c]:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1
        elif s_indexes[t_c][s_pointer[t_c]] <= last_index:
            for i in range(last_index, s_pointer[t_c]):
                if last_index < s_indexes[t_c][i]:
                    s_pointer[t_c] = i
                    break
            else:
                # reset
                s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
                power += 1

        last_index = s_indexes[t_c][s_pointer[t_c]]
        s_pointer[t_c] += 1

    print(len(s) * power + last_index + 1)


main()

Submission status: Wrong Answer

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

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

    s_indexes = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, s_c in enumerate(s):
        s_indexes[s_c].append(i)
    s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
    s_length = {c: len(s_indexes[c]) for c in "abcdefghijklmnopqrstuvwxyz"}

    power = 0
    last_index = -1
    for i, t_c in enumerate(t):
        if s_length[t_c] <= s_pointer[t_c]:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1
        elif s_indexes[t_c][s_pointer[t_c]] <= last_index:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1

        last_index = s_indexes[t_c][s_pointer[t_c]]
        s_pointer[t_c] += 1

    print(len(s) * power + last_index + 1)


main()

Submission status: Wrong Answer

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

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

    s_indexes = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, s_c in enumerate(s):
        s_indexes[s_c].append(i)
    s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
    s_length = {c: len(s_indexes[c]) for c in "abcdefghijklmnopqrstuvwxyz"}

    power = 0
    last_index = -1
    for i, t_c in enumerate(t):
        if s_length[t_c] <= s_pointer[t_c]:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1
        elif s_indexes[t_c][s_pointer[t_c]] <= last_index:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1

        last_index = s_indexes[t_c][s_pointer[t_c]]

    print(len(s) * power + last_index + 1)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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

    s_char_to_indexlist = defaultdict(list)
    for i in range(len(s)):
        s_char_to_indexlist[s[i]].append(i)

    power = 0
    last_i = -1
    s_index = defaultdict(int)
    for t_c in t:

        power_flg = False
        if len(s_char_to_indexlist[t_c]) <= s_index[t_c]:
            s_index = defaultdict(int)
            power_flg = True

        i = s_char_to_indexlist[t_c][s_index[t_c]]
        if i <= last_i:
            s_index = defaultdict(int)
            i = s_char_to_indexlist[t_c][s_index[t_c]]
            power_flg = True

        if power_flg:
            power += 1

        s_index[t_c] += 1
        last_i = i

    ans = len(s) * power + last_i + 1
    print(ans)
    #print("power={}, last_i={}".format(power, last_i))


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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

    s_char_to_indexlist = defaultdict(list)
    for i in range(len(s)):
        s_char_to_indexlist[s[i]].append(i)

    power = 0
    last_i = -1
    for t_c in t:
        s_index = defaultdict(int)

        if len(s_char_to_indexlist[t_c]) <= s_index[t_c]:
            s_index = defaultdict(int)
            power += 1

        i = s_char_to_indexlist[t_c][s_index[t_c]]
        if i <= last_i:
            s_index = defaultdict(int)
            i = s_char_to_indexlist[t_c][s_index[t_c]]
            power += 1

        s_index[t_c] += 1
        last_i = i

    ans = len(s) * power + last_i + 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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

    s_char_to_indexlist = defaultdict(list)
    for i in range(len(s)):
        s_char_to_indexlist[s[i]].append(i)

    power = 0
    last_i = -1
    for t_c in t:
        s_index = defaultdict(int)

        if len(s_char_to_indexlist[t_c]) <= s_index[t_c]:
            s_index = defaultdict(int)
            power += 1

        i = s_char_to_indexlist[t_c][s_index[t_c]]
        if i <= last_i:
            s_index = defaultdict(int)
            s_index[t_c] += 1
            power += 1

        last_i = i

        s_index[t_c] += 1

    ans = len(s) * power + last_i + 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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

    s_char_to_indexlist = defaultdict(list)
    for i in range(len(s)):
        s_char_to_indexlist[s[i]].append(i)

    power = 0
    last_i = -1
    for t_c in t:
        s_index = defaultdict(int)

        if len(s_char_to_indexlist[t_c]) <= s_index[t_c]:
            s_index = defaultdict(int)
            power += 1

        i = s_char_to_indexlist[t_c][s_index[t_c]]
        if i <= last_i:
            s_index = defaultdict(int)
            power += 1

        last_i = i

        s_index[t_c] += 1

    ans = len(s) * power + last_i + 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect
s = input()
t = input()
dicta = defaultdict(list)
for i in range(len(s)):
    dicta[s[i]] += [i]
snow = 0
count = 0
flag = True
for i in t:
    if i not in s:
        flag = False
        break
    nowt = dicta[i]
    snowind = bisect.bisect_right(nowt,snow)
    if snowind == len(nowt):
        count += 1
        snow = nowt[0]
    else:
        snow = nowt[snowind]
if flag:
    print(len(s)*count+snow +1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
if t[0] not in s:
    print(-1)
else:
    snow = s.index(t[0])
    while True:
        tcount += 1
        if tcount == lent:
            break
        if t[tcount] in s[snow+1:]:
            snow = s[snow+1:].index(t[tcount])+snow+1
        elif t[tcount] in s:
            snow = s.index(t[tcount])
            count += 1
        else:
            flag = False
            break
    if flag:
        print(count*len(s) + s.index(t[-1])+1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
if t[0] not in s:
    print(-1)
else:
    snow = s.index(t[0])
    while True:
        tcount += 1
        if tcount == lent:
            break
        if t[tcount] in s[snow+1:]:
            snow = s[snow+1:].index(t[tcount])+snow
        elif t[tcount] in s:
            snow = s.index(t[tcount])
            count += 1
        else:
            flag = False
            break
    if flag:
        print(count*len(s) + s.index(t[-1])+1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
if t[0] not in s:
    print(-1)
else:
    snow = s.index(t[0])
    while True:
        tcount += 1
        if tcount == lent:
            break
        if t[tcount] in s[snow+1:]:
            snow = s[snow+1:].index(t[tcount])
        elif t[tcount] in s:
            snow = s.index(t[tcount])
            count += 1
        else:
            flag = False
            break
    if flag:
        print(count*len(s) + s.index(t[-1])+1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
if t[0] not in s:
    print(-1)
else:
    while True:
        snow = s.index(t[tcount])
        tcount += 1
        if tcount == lent:
            break
        if t[tcount] not in s:
            flag = False
            break
        if t[tcount] in s[snow+1:]:
            snow = s[snow+1:].index(t[tcount])
        else:
            snow = s.index(t[tcount])
            count += 1
    if flag:
        print(count*len(s) + s.index(t[-1])+1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
def find_ge(a, x):
  i = bisect_left(a, x)
  if i != len(a):
    return a[i]
  print(-1)
  exit()

S = list(map(lambda x: ord(x) - ord("a"), input())) * 2
T = list(map(lambda x: ord(x) - ord("a"), input()))

l = [[] for i in range(26)]

for i in range(len(S)):
  l[S[i]].append(i)

ans = 1
cur = 0
for i in range(len(T)):
  fge = find_ge(l[T[i]], cur)
  ans += fge - cur
  cur = fge
  if cur >= len(S)//2:
    cur -= len(S)//2

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

REPEAT_NUM = 10 ** 100

S = input()
T = input()
lenS = len(S)
lenT = len(T)

idxes_S = {}
for idx, s in enumerate(S):
    if s not in idxes_S:
        idxes_S[s] = []
    idxes_S[s].append(idx)

idx_s = 0
idx_t = 0
while idx_t < lenT and idx_s <= lenS * REPEAT_NUM:
    if T[idx_t] not in idxes_S:
        print(-1)
        exit()
    else:
        tmp_idx = bisect.bisect_left(idxes_S[T[idx_t]], idx_s % lenS)
        if len(idxes_S[T[idx_t]]) == tmp_idx:
            idx_s += lenS - idx_s % lenS + idxes_S[T[idx_t]][0]
        else:
            idx_s += idxes_S[T[idx_t]][tmp_idx] - idx_s % lenS
        idx_t += 1

if idx_t == lenT:
    print(idx_s + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import bisect

REPEAT_NUM = 10 ** 100

S = input()
T = input()
lenS = len(S)
lenT = len(T)

idxes_S = {}
for idx, s in enumerate(S):
    if s not in idxes_S:
        idxes_S[s] = []
    idxes_S[s].append(idx)

idx_s = 0
idx_t = 0
while idx_t < lenT and idx_s < lenS * REPEAT_NUM:
    if T[idx_t] not in idxes_S:
        print(-1)
        exit()
    else:
        tmp_idx = bisect.bisect(idxes_S[T[idx_t]], idx_s % lenS)
        if len(idxes_S[T[idx_t]]) == tmp_idx:
            idx_s += lenS - idx_s % lenS + idxes_S[T[idx_t]][0]
        else:
            idx_s += idxes_S[T[idx_t]][tmp_idx] - idx_s % lenS
        idx_t += 1

if idx_t == lenT:
    print(idx_s + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import bisect

MAX_VALUE = 10**100
S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  Si[s].append(i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    if ans<=max(Si[t]):
      idx = Si[t][min(bisect.bisect(Si[t],ans),len(Si[t])-1)]
    else:
      factor = (ans-min(Si[t]))//lenS if (ans-min(Si[t]))%lenS == 0 else (ans-min(Si[t]))//lenS + 1
      idx = Si[t][min(bisect.bisect(Si[t],ans%lenS),len(Si[t])-1)] + factor*lenS
    ans = idx
    if MAX_VALUE<ans:
      print(-1)
      exit()
print(ans+1)

Submission status: Wrong Answer

Solution code:
import bisect

MAX_VALUE = 10**100
S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  Si[s].append(i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    if ans<=max(Si[t]):
      idx = Si[t][min(bisect.bisect(Si[t],ans),len(Si[t])-1)]
    else:
      factor = (ans-min(Si[t]))//lenS + 1
      idx = Si[t][min(bisect.bisect(Si[t],ans%lenS),len(Si[t])-1)] + factor*lenS
    ans = idx
    if MAX_VALUE<ans:
      print(-1)
      exit()
print(ans+1)

Submission status: Wrong Answer

Solution code:
import heapq

S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  heapq.heappush(Si[s],i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    while idx<ans:
      idx = heapq.heappop(Si[t])
      heapq.heappush(Si[t],idx+((ans-idx)//lenS+1)*(lenS))
    ans = idx
print(ans+1)

Submission status: Wrong Answer

Solution code:
sl = list(input())
tl = list(input())

n = len(sl)
from collections import defaultdict
dic = defaultdict(list) 

for idx, s in enumerate(sl):
   dic[s].append(idx)
   dic[s].append(idx+n)

for s in dic:
   dic[s] = sorted(dic[s])

import bisect

ans = 1
now = 0
for t in tl:
   if dic[t] == []:
      print(-1)
      import sys
      sys.exit()
   idx = bisect.bisect_left(dic[t], now)
   ans += dic[t][idx] - now
   now = dic[t][idx]
   if now >= n:
      now -= n
print(ans)