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:
def main():
    S = input()
    T = input()
    N = len(S)

    def check(S, T):
        b = {s for s in S}
        for t in T:
            if t not in b:
                return True  # -1
        return False

    def is_ok(mid, now, ans):
        if ans < now[mid]:
            return True
        else:
            return False

    def binary_search_meguru(now, ans):
        ng = -1
        ok = len(now)-1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid, now, ans):
                ok = mid
            else:
                ng = mid
        return now[ok]

    if check(S, T):
        return print(-1)

    from string import ascii_lowercase

    dic = {a: [] for a in ascii_lowercase}
    for i, s in enumerate(S):
        dic[s].append(i)
    ans = 0
    cycle = 0
    for t in T:
        now = dic[t]
        if now[-1] < ans:
            cycle += 1
            ans = 0
        idx = binary_search_meguru(now, ans)
        ans = idx
    print(ans + N*cycle + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)

    def check(S, T):
        b = {s for s in S}
        for t in T:
            if t not in b:
                return True  # -1
        return False

    def is_ok(mid, now, ans):
        if ans <= now[mid]:
            return True
        else:
            return False

    def binary_search_meguru(now, ans):
        ng = -1
        ok = len(now)-1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid, now, ans):
                ok = mid
            else:
                ng = mid
        return now[ok]

    if check(S, T):
        return print(-1)

    from string import ascii_lowercase

    dic = {a: [] for a in ascii_lowercase}
    for i, s in enumerate(S):
        dic[s].append(i)
    ans = 0
    cycle = 0
    for t in T:
        now = dic[t]
        if now[-1] <= ans:
            cycle += 1
            ans = 0
        idx = binary_search_meguru(now, ans)
        ans = idx
    print(ans + N*cycle + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    T = input()
    N = len(2*S)

    def check(S, T):
        b = {s for s in S}
        for t in T:
            if t not in b:
                return False
        return True

    def is_ok(mid, now, ans):
        if ans <= now[mid]:
            return True
        else:
            return False

    def binary_search_meguru(now, ans):
        ng = -1
        ok = len(now)-1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid, now, ans):
                ok = mid
            else:
                ng = mid
        return now[ok]

    if not check(S, T):
        return print(-1)

    from string import ascii_lowercase

    dic = {a: [] for a in ascii_lowercase}
    for i, s in enumerate(S*2):
        dic[s].append(i)
    ans = 0
    cycle = 0
    for t in T:
        now = dic[t]
        if now[-1] < ans:
            cycle += 1
            ans = 0
        idx = binary_search_meguru(now, ans)
        ans = idx
    print(ans + N*cycle + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


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

    D = {chr(i): [] for i in range(ord("a"), ord("z") + 1)}

    for i, s in enumerate(S):
        D[s].append(i)
    
    res = 0
    p = 0
    for t in T:
        if D[t] == []:
            print(-1)
            return
        
        j = bisect.bisect_left(D[t], p)
        if j == len(D[t]):
            p = D[t][0]
            res += 1
        else:
            p = D[t][j]
        
    print(res * len(S) + p + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    N = len(S)
    INF = N + 1
    T = input()
    # S で i 番目の何番目の後で文字 c が出てくるかを計算
    next_loc = [[INF for _ in range(N)] for _ in range(26)]
    for i, s in enumerate(S):
        c = ord(s) - ord('a')
        next_loc[c][i - 1] = 1
    for c in range(26):
        n = INF
        for i in range(N - 1, -(N + 1), -1):
            n = min(next_loc[c][i], n + 1)
            next_loc[c][i] = n
    # 答えを計算
    ans = 1
    index = 0
    for t in T:
        c = ord(t) - ord('a')
        i = next_loc[c][index]
        if i == INF:
            print(-1)
            return
        ans += i
        index = (index + i) % N
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
l_s = len(s)
l_t = len(t)

s2 = s + s
l_s2 = len(s2)

next_idx = [[l_s2] * 26 for i in range(l_s2+1)]

for i in reversed(range(l_s2)):
    for j in range(26):
        next_idx[i][j] = next_idx[i+1][j]
    next_idx[i][ord(s2[i]) - ord("a")] = i

cur_idx = 0
for i in range(l_t):
    idx = next_idx[cur_idx%l_s][ord(t[i]) - ord("a")]
    if idx == l_s2:
        print("-1")
        exit()
    
    cur_idx += idx - cur_idx % l_s

print(cur_idx+1)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    T = readline().strip()
    N = len(S)
    M = len(T)

    SS = S + S

    A = [False] * 26
    for c in S:
        A[ord(c) - 97] = True

    for c in T:
        if not A[ord(c) - 97]:
            print(-1)
            return

    B = [[-1] * N for _ in range(26)]
    for c in set(T):
        code = ord(c) - 97
        row = B[code]

        left = right = 0
        while True:
            right = SS.find(c, left)
            if right < N:
                row[left : right + 1] = [right] * (right - left + 1)
                left = right + 1
            else:
                row[left:N] = [right] * (N - left)
                break

    ans = 0
    i = 0
    for c in T:
        j = B[ord(c) - 97][i]
        ans += j - i
        if j < N:
            i = j
        else:
            i = j - N

    print(ans + 1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

s = rs()
t = rs()

import collections
pos = collections.defaultdict(list)
for i, c in enumerate(s):
	pos[c].append(i)

def bisect_right(arr, x):
    # a_i <= x < a_{i+1}
    l, r = 0, len(arr)
    while r - l > 1:
        c = (r + l) // 2
        if x >= arr[c]:
            l = c+1
        else:
            r = c
    return l

num = 0
cur = -1

for c in t:
	if c not in pos:
		print(-1)
		exit()
	i = bisect_right(pos[c], cur)
	if i == len(pos[c]):
		i = 0
		num += 1
	cur = pos[c][i]
print(num*len(s)+cur+1)

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

s = rs()
t = rs()


import collections
pos = collections.defaultdict(list)
for i, c in enumerate(s):
	pos[c].append(i)

import bisect

0, 1, 2

num = 0
cur = 0

for c in t:
	if c not in pos:
		print(-1)
		exit()
	i = bisect.bisect_right(pos[c], cur)
	if i == len(pos[c]):
		i = 0
		num += 1
	cur = pos[c][i]
print(num*len(s)+cur+1)

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

s = rs()
t = rs()



pos = {}
for i, c in enumerate(s):
	if c not in pos:
		pos[c] = i

num = 0
cur = 0

for c in t:
	if c not in pos:
		print(-1)
		exit()
	if pos[c] <= cur:
		num += 1
	cur = pos[c]
print(num*len(s)+cur+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    from collections import defaultdict
    from bisect import bisect
    d = defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)
    ans, i = 0, -1
    for c in t:
        if not d[c]:
            return -1
        j = bisect(d[c], i)
        if len(d[c]) == j:
            ans += len(s) - i + d[c][0]
            i = d[c][0]
        else:
            ans += d[c][j] - i
            i = j
    return ans + 1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    print(solve(s, t))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import bisect
from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    s=input()

    ss=s*2
    d={}
    for k,v in enumerate(ss):
        if v in d:
            d[v].append(k)
        else: d[v]=[k]
    

    

    ls=len(s)
    t=input()
    cur=0
    flag=False
    for i in t:
        if i in d:
            idx=d[i][bisect.bisect_right(d[i],cur%ls)]
            dif=idx-cur%ls
            cur+=dif
        else:
            flag=True
            break
    print(cur+1 if not flag else -1)




    
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import bisect
from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    s=input()

    ss=s*2
    d={}
    for k,v in enumerate(ss):
        if v in d:
            d[v].append(k)
        else: d[v]=[k]
    

    

    ls=len(s)
    t=input()
    cur=-1
    flag=False
    for i in t:
        if i in d:
            idx=d[i][bisect.bisect_left(d[i],cur%ls)]
            dif=idx-cur%7
            cur+=dif
        else:
            flag=True
            break
    print(cur+1 if not flag else -1)




    
resolve()

Submission status: Wrong Answer

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

if len(set(t)-set(s)) > 0:
  print(-1)
  exit()

c = set(s)
dic = {}
for char in c:
  dic[char] = []

for i in range(len(s)):
  dic[s[i]] += [i]

last = -1
r = 0
for char in t:
  tmp = last
  idx = bisect.bisect_left(dic[char], last)
  if idx < len(dic[char]):
    last = dic[char][idx]

  if tmp == last:
    r += 1
    last = dic[char][0]

print(len(s)*r + last + 1)

Submission status: Wrong Answer

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

if len(set(t)-set(s)) > 0:
  print(-1)
  exit()

c = set(s)
dic = {}
for char in c:
  dic[char] = []

for i in range(len(s)):
  dic[s[i]] += [i]

last = -1
r = 0
for char in t:
  tmp = last
  for idx in dic[char]:
    if idx > last:
      last = idx
      break

  if tmp == last:
    r += 1
    last = dic[char][0]

print(len(s)*r + idx + 1)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
s = input()
n = len(s)
t = input()
if set(s) & set(t) != set(t):
    print(-1)
else:
    cnt = defaultdict(list)
    for i in range(n):
        cnt[s[i]].append(i+1)

    loop = 0
    prev = 5
    for c in t:
        x = cnt[c]
        idx = bisect.bisect_right(x, prev)
        if idx < len(x):
            prev = x[idx]
        else:
            prev = x[0]
            loop += 1
    print(loop*n+prev)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect
s = list(input())
sn = len(s)
t = list(input())
tn = len(t)
kouho = []
for i in range(26):
    kar = []
    now = chr(ord('a') + i)
    for j in range(sn):
        if s[j] == now:
            kar.append(j)
    kouho.append(kar)

cou = 0
now = 0
for i in range(tn):
    u = ord(t[i])-ord("a")
    if kouho[u]:
        tugi = bisect(kouho[u],now)
        if tugi == len(kouho[u]):
            cou += 1
            now = kouho[u][0]
        else:
            now = kouho[u][tugi]
    else:
        print(-1)
        exit()

print(cou*sn + now + 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect


S = input()
S = S + S
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

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

N = len(S) // 2
ans = 0
now = -1

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    now = At[x]
    if now >= N:
        ans += 1
    now += 1
    now %= N

print(ans * N + now)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect


S = input()
S = S + S
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

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

N = len(S) // 2
ans = 0
now = -1

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    now = At[x]
    if now >= N:
        ans += 1
        now %= N
print(ans * N + now + 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect


S = input()
S = S + S
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

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

N = len(S) // 2
ans = 0
now = -1

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    ans += At[x] - now
    now = At[x]
    now %= N


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect


S = input()
S = S + S
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

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

N = len(S) // 2
ans = 1
now = 0

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    ans += At[x] - now
    now = At[x]
    now %= N


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect


S = input()
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

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

N = len(S)
ans = 1
now = 0

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    if x == len(At):
        ans += N - now
        ans += At[0]
        now = At[0]
    else:
        ans += At[x] - now
        now = At[x]


print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
sn = len(s)
t = input()
tn = len(t)
ans = 0
nows = 0
nowt = 0
flag = False
while True:
    if t[nowt] == s[nows]:
        nowt += 1
        flag = True
    nows += 1
    ans += 1
    if nowt == tn:
        break
    if nows == sn:
        if flag:
            nows = 0
        else:
            print(-1)
            exit()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

S = input()
N_S = len(S)
T = input()
N_T = len(T)

dict_s = defaultdict(int)
dict_order = defaultdict(list)
for i in range(N_S):
    dict_s[S[i]] += 1
    dict_order[S[i]].append(i + 1)

dict_t = defaultdict(int)
for i in range(N_T):
    dict_t[T[i]] += 1

flag = True
for i in dict_t:
    if dict_s[i] == 0:
        flag = False
        break

if not flag:
    print(-1)
    exit()

now = dict_order[T[0]][0]
ans = [dict_order[T[0]][0]]

for i in range(1, N_T):
    index = bisect_right(dict_order[T[i]], now)
    if index == len(dict_order[T[i]]):
        now = dict_order[T[i]][0]
    else:
        now = dict_order[T[i]][index]
    ans.append(now)

cnt = 0
for i in range(1, N_T):
    if ans[i] < ans[i - 1]:
        cnt += 1
print(cnt * N_S + ans[-1])

Submission status: Wrong Answer

Solution code:
def main():
  s = str(input())
  s_ = set(list(s))
  t =  str(input())
  t_ =  set(list(t))
  alphabet = "abcdefghijklmnopqrstuvwxyz"
  if t_ <= s_:
    length_s = len(s)
    
    res = [[length_s]*(26)  for _ in range(length_s+1)]
    for i in range(length_s-1, -1, -1):
      for j in range(26):
        if s[i] == alphabet[j]:
          res[i][j] = i
        else:
          res[i][j] = res[i+1][j]
    
    ans = 0
    now = 0
    for i in range(len(t)):
      for j in range(26):
        if t[i] == alphabet[j]:
          ans += res[now][j]-now
          now = res[now][j]
          if now == length_s:
            ans += res[0][j]
            now = res[0][j]
    print(ans+1)
  else:
    print(-1)
if  __name__  == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(S, T):
    if len(set(c for c in T) - set(c for c in S)) > 0:
        return -1

    from collections import defaultdict
    si = defaultdict(list)
    for i, c in enumerate(S):
        si[c].append(i)

    ans = 0
    ci = 0
    from bisect import bisect_left
    for i, c in enumerate(T):
        j = bisect_left(si[c], ci)
        ci = si[c][j%len(si[c])]
        if j == len(si[c]):
            ans += 1
    return (ans)*len(S) + ci + 1





def main():
    S = read_str()
    T = read_str()
    print(slv(S, T))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
from bisect import bisect_right

s = input()
t = input()

c = Counter(s)
for e in t:
    if c[e] == 0:
        print(-1)
        exit()

ss = s + s
d = defaultdict(list)
for i, e in enumerate(ss):
    d[e].append(i)

now = 0
ans = 0
for e in t:
    i = bisect_right(d[e], now)
    nxt = d[e][i]
    ans += nxt - now
    now = nxt % len(s)

ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        if not T[i] in seen:
            print(-1)
            exit()

        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,rep)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,rep)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + counter[T[::-1][0]][0] + 1
    print(ans)




if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

    for i in range(len(s)):
        d[s[i]].append(i)
    
    round = 0
    prev = -1
    for i in range(len(t)):
        if not t[i] in st_s:
            print(-1)
            return
        now = getNextIdx(prev,d[t[i]])
        if now < prev:
            round += 1
        
        prev = now
    
    print(prev + round*len(s) + 1)


def getNextIdx(prev,idx_list):
    ret_idx = bisect.bisect_right(idx_list, prev)
    if ret_idx == len(idx_list):
        return idx_list[0]

    return idx_list[ret_idx]

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import bisect


def main() -> None:
    S = input()
    T = input()
    SS = S + S
    alphas = [[] for _ in range(26)]
    for i, s in enumerate(SS):
        alphas[ord(s) - ord('a')].append(i)
    rep, now = 0, 0
    for t in T:
        alpha = alphas[ord(t) - ord('a')]
        i = bisect.bisect_left(alpha, now + 1)
        if i == len(alpha):
            print(-1)
            return
        now = alpha[i]
        if now >= len(S):
            now -= len(S)
            rep += 1
    print(rep * len(S) + now + 1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s = input()
t = input()
alpha = [[] for _ in range(26)]
def f(c): return ord(c)-ord("a")

for i,c in enumerate(s): alpha[f(c)].append(i)
idx = -1
roop = 0
for c in t:
    lst = alpha[f(c)]
    if not lst:
        ans = -1
        break
    i = bisect_left(lst,idx)
    if i == len(lst):
        roop += 1
        idx = lst[0]
    else:
        idx = lst[i]
else:
    ans = len(s)*roop+idx+1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
S = list(input())
T = list(input())
C = {}
for i in range(97, 97+26):
    C[chr(i)] = -1

k = len(T)
for i in range(len(S)):
    if C[S[i]] == -1:
        C[S[i]] = [i]
    else:
        C[S[i]].append(i)

p = 0
now = -1
ans = 0
used = {}
L = {}
for i in range(97, 97+26):
    used[chr(i)] = 0
    if C[chr(i)] == -1:
        L[chr(i)] = 0
    else:
        L[chr(i)] = len(C[chr(i)])

while(True):
    n = T[p]
    if C[n] == -1:
        print(-1)
        sys.exit()
    else:
        if used[n] >= L[n]:
            p -= 1
            for i in range(97, 97 + 26):
                used[chr(i)] = 0
            ans += len(S) - now - 1
            now = -1
        elif C[n][used[n]] >= now:
            ans += C[n][used[n]] - now
            now = C[n][used[n]]
            used[n] += 1
        else:
            ans += len(S) - now - 1
            p -= 1
            now = -1
            for i in range(97, 97 + 26):
                used[chr(i)] = 0
    p += 1
    if p == k:
        print(ans)
        break

Submission status: Wrong Answer

Solution code:
import sys
S = list(input())
T = list(input())
C = {}
for i in range(97, 97+26):
    C[chr(i)] = -1

k = len(T)
for i in range(len(S)):
    if C[S[i]] == -1:
        C[S[i]] = [i]
    else:
        C[S[i]].append(i)

p = 0
now = -1
ans = 0
used = {}
L = {}
for i in range(97, 97+26):
    used[chr(i)] = 0
    if C[chr(i)] == -1:
        L[chr(i)] = 0
    else:
        L[chr(i)] = len(C[chr(i)])

while(True):
    n = T[p]
    if C[n] == -1:
        print(-1)
        sys.exit()
    else:
        if used[n] >= L[n]:
            p -= 1
            for i in range(97, 97 + 26):
                used[chr(i)] = 0
            ans += len(S) - now - 1
            now = -1
        elif C[n][used[n]] >= now:
            ans += C[n][used[n]] - now
            now = C[n][used[n]]
            used[n] += 1
        else:
            ans += len(S) - now - 1
            now = -1
            for i in range(97, 97 + 26):
                used[chr(i)] = 0
    p += 1
    if p == k:
        print(ans)
        break

Submission status: Wrong Answer

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

from collections import defaultdict
pos = defaultdict(list)
for i, char in enumerate(s):
    pos[char].append(i)

from bisect import bisect_left

ans = 0
before = -1
flag = True
for char in t:
    if pos[char] == []:
        flag = False
        break

    if before > pos[char][-1]:
        ans += len(s)
        before = pos[char][0]
    else:
        idx = bisect_left(pos[char], before)
        before = pos[char][idx]

if flag:
    print(ans + before + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections
s = raw_input()
t = raw_input()
sb = s + s
h = {chr(ord('a') + i):-1 for i in range(26)}
dp = []
for j in range(len(sb)-1,-1,-1):
	h[sb[j]] = j
	dp.append({k:h[k] for k in h})
dp = dp[::-1]
i = 0
j = 0
c = 0
while(j < len(t)):
	ha = dp[i]
	letter = t[j]
	if ha[letter] != -1:
		i = ha[letter]
		j += 1
	else:
		j = -1
		break

	if i >= len(s):
		i %= len(s)
		c+=1
		
print (c * len(s) + i + 1) if j != -1 else -1

Submission status: Wrong Answer

Solution code:
s=list(input())
t=list(input())
L=[]
for i in t:
    if i not in s:
        print(-1)
        exit()
    num=[j for j, x in enumerate(s) if x==i]
    L.append(num)
n=L[0][0]
loop=0
t=0
for i in range(1,len(L)):
    if L[i]!=L[i-1]:
        t=0
    else:
        t=(t+1)%len(L[i])
    if n>L[i][t]:
        loop += len(s)
    n=L[i][t]
loop += n+1
print(loop)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left

    S = input()
    T = input()

    L = len(S)

    pos = tuple(list() for _ in range(26))
    orda = ord('a')
    for i, c in enumerate(S):
        j = ord(c) - orda
        pos[j].append(i)

    rep = 0
    curr = -1
    for c in T:
        j = ord(c) - orda

        if not pos[j]:
            print(-1)
            return

        i = bisect_left(pos[j], curr)
        if i == len(pos[j]):
            rep += 1
            curr = 0
            i = bisect_left(pos[j], curr)

        curr = pos[j][i]

    print(rep * L + curr + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left

    S = input()
    T = input()

    L = len(S)

    pos = tuple(list() for _ in range(26))
    orda = ord('a')
    for i, c in enumerate(S):
        j = ord(c) - orda
        pos[j].append(i)

    rep = 0
    curr = 0
    for c in T:
        j = ord(c) - orda
        i = bisect_left(pos[j], curr)
        if i == len(pos[j]):
            rep += 1
            curr = 0
            i = bisect_left(pos[j], curr)
            if i == len(pos[j]):
                print(-1)
                return
        curr = pos[j][i]

    print(rep * L + curr + 1)


if __name__ == '__main__':
    main()