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: Accepted

Solution code:
def main():
  s = list(map(lambda x:ord(x)-97, list(input())))
  ls = len(s)
  ss = set(s)
  t = list(map(lambda x:ord(x)-97, list(input())))
  lt = len(t)
  st = set(t)
  td = [list() for _ in range(26)]
  if not st.issubset(ss):
    print(-1)
    exit()
  for i in range(lt-1):
    td[t[i]].append(t[i+1])
  md = [None for _ in range(ls)]
  cd = [0]*26
  for i in range(ls-1,-1,-1):
    cd[s[i]] = i + ls
  for i in range(ls-1,-1,-1):
    md[i] = cd.copy()
    cd[s[i]] = i
  ans = 0
  cur = cd[t[0]]
  for i in range(lt-1):
    cur = md[cur][t[i+1]]
    ans += (cur//ls)
    cur %= ls
  print(1 + ans*ls+cur)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()
lis = [[]for _ in range(26)]

for i,j in enumerate(s):
    j = ord(j) -ord("a")
    lis[j].append(i)

lenlis = [len(lis[i]) for i in range(26)]

now = 0
ans = 0
for i in t:
    i = ord(i) -ord("a")
    if lenlis[i] == 0:
        ans = -1
        break
    insert_index = bisect.bisect_left(lis[i],now)
    if insert_index == lenlis[i]:
        ans += 1
        now = lis[i][0] +1
    else:
        now = lis[i][insert_index] + 1

if ans == -1:
    print(-1)
else:
    ans = ans*len(s) + now
    print(ans)

Submission status: Accepted

Solution code:
from bisect import*
s=input()
t=input()
d={}
for i,c in enumerate(s):
    d.setdefault(c,[]).append(i+1)
m=-1
n=len(s)
r=0
for c in t:
    if not c in d:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        r+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(r*n+m)

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin, setrecursionlimit
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return



def main():
    # まず可能かどうか
    S = str(input().rstrip())*2
    T = str(input().rstrip())
    LS = len(S)//2
    LT = len(T)
    S *= 3
    # はじめて出る位置
    char_p = dict()
    for i in range(LS):
        if not S[i] in char_p:
            char_p[S[i]] = i

    # char_pの文字が２つめのはじめて出る位置までに
    char_d = dict(zip(char_p.keys(),[[0 for __ in range(LS+char_p[c])] for c in char_p]))
    for c in char_p:
        dis = 1
        for i in range(LS+char_p[c]-1,-1,-1):
            if S[i] == c:
                char_d[c][i] = dis
                dis = 1
            else:
                char_d[c][i] = dis
                dis += 1
    # 答えの計算
    debug(char_d)
    init = True
    for t in T:
        if t not in char_p:
            print(-1)
            exit()
        else:
            debug(t,'string')
            if init:
                cur = char_p[t]
                init = False
            #それ以外なら区切りで相対的な位置を出して足す
            else:
                rel_cur = cur%LS
                debug(rel_cur,"relative_cursol")
                cur += char_d[t][rel_cur]
        debug(cur,"cur")
        # print()
    print(cur+1)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def get_answer(input_list):
    so = input_list[0]
    t = input_list[1]

    s_len = len(so)

    t_i = [-1] * len(t)
    s = so + so
    s_index = 0
    for i in range(len(t)):
        index = s.find(t[i], s_index)
        if index < 0:
            break
        index = index % s_len
        t_i[i] = index
        s_index = index + 1
        s_index = s_index % s_len

    if -1 in t_i:
        return -1

    t_len = len(t_i)
    ret = 0
    ret_i = 0
    for i in range(t_len):
        t1 = t_i[i]
        ret = t1
        if i < t_len - 1:
            t2 = t_i[i + 1]
            if t1 >= t2:
                ret_i += 1

    return ret_i * s_len + ret + 1


if __name__ == "__main__":
    input_list = []
    while True:
        try:
            input1 = input()
            if not input1:
                break
            if len(input1) == 0:
                break
            input_list.append(input1)
        except EOFError:
            break
    print(get_answer(input_list))

Submission status: Accepted

Solution code:
def get_answer(input_list):
    so = input_list[0]
    t = input_list[1]

    s_len = len(so)

    """
    contest son
    s:5
    o:1 7+2
    n:2 7+3
    
    aabbcc abca
    a:0 0
    b:2 2
    c:4 4
    a:0 0 +6
    
    aa aaaa
    a:0
    a:1
    a:0 + 2
    a:1 + 2   
    
    aabbcc abccba
    a 0
    b 2
    c 4
    c 5
    b 2 6
    a 0 12 = 13
    """

    t_i = [-1] * len(t)
    s = so + so
    s_index = 0
    for i in range(len(t)):
        index = s.find(t[i], s_index)
        if index < 0:
            break
        index = index % s_len
        t_i[i] = index
        s_index = index + 1
        s_index = s_index % s_len

    if -1 in t_i:
        return -1


    t_len = len(t_i)
    ret = 0 #len(t_i)
    ret_i = 0
    for i in range(t_len):
        t1 = t_i[i]
        ret = t1
        if i < t_len - 1:
            t2 = t_i[i + 1]
            if t1 >= t2:
                ret_i += 1


    """
    for i in range((1000 - s_index) * s_len):
        find_flag = True
        ss = s
        for tt in t:
            ii = ss.find(tt)
            if ii < 0:
                find_flag = False
                break
            ss = ss[ii + 1:]
        if find_flag:
            ret = len(s)
            break
        s += so[s_index]
        s_index = (s_index + 1) % s_len
    """
    return ret_i * s_len + ret + 1

# b33 179
if __name__ == "__main__":
    input_list = []
    while True:
        try:
            input1 = input()
            if not input1:
                break
            if len(input1) == 0:
                break
            input_list.append(input1)
        except EOFError:
            break
    print(get_answer(input_list))

Submission status: Accepted

Solution code:
import bisect
import sys
S = input()
T = input()


# sが何番目に出てくるかの辞書をついくる
s_index = {}
for i in range(len(S)):
    if S[i] in s_index:
        s_index[S[i]].append(i + 1)
    else:
        s_index[S[i]] = [i+1]


current_s_index = 0
loop_count = 0
ans = 0
for t in T:
    if not t in s_index:
        print(-1)
        sys.exit()

    if current_s_index >= s_index[t][-1]:
        current_s_index = s_index[t][0]
        loop_count += 1
    else:
        index = bisect.bisect(s_index[t], current_s_index)
        current_s_index = s_index[t][index]

print(current_s_index + loop_count * len(S))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import bisect
s = input()
t = input()



count = 0
s_len = len(s)
s_list = np.zeros(len(s))
t_list = []*len(t)
indexes = []

for i in range(26):
  
  indexes.append([j for j, x in enumerate(s) if x == chr(i + ord('a')) ])
  


for i,k in enumerate(t):

  index = indexes[ord(k)-ord('a')]
  
  if len(index) == 0:
    print(-1)
    sys.exit(0)
  else:
    t_list.insert(i,index)
    


pre = -1
for i in range(len(t)):
  
  #high = [j  for j in t_list[i] if j > pre]
  high = bisect.bisect_left(t_list[i], pre+1) 

  if high >= len(t_list[i]):
    
    count += s_len - pre  + t_list[i][0]
    pre = t_list[i][0] 
  else:
    
    count += t_list[i][high] - pre 
    pre = t_list[i][high]

print(count)

Submission status: Accepted

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

import bisect

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])
f = [[] for _ in range(26)]

for i in range(len(s)):
    f[ord(s[i])-97].append(i)

g = [-1 for _ in range(len(t))]
if len(f[ord(t[0])-97]) == 0:
    print(-1)
    sys.exit()
g[0] = f[ord(t[0])-97][0]
cnt = 0
for i in range(1,len(t)):
    if len(f[ord(t[i])-97]) == 0:
        print(-1)
        sys.exit()

    if f[ord(t[i])-97][-1] > g[i-1]:
        index = bisect.bisect_right(f[ord(t[i])-97], g[i-1])
        g[i] = f[ord(t[i])-97][index]
    else:
        g[i] = f[ord(t[i])-97][0]
    if g[i] <= g[i-1]:
        cnt += 1

print(cnt*len(s)+g[-1]+1)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
moji = {}
for i in range(len(s)):
    if s[i] in moji.keys():
        moji[s[i]].append(i)
    else:
        moji[s[i]] = [i]

now = -1
kaisu = 0
flag = True
for i in range(len(t)):
    if t[i] in moji.keys():
        basho = moji[t[i]]
        lenbasho = len(basho)
        nowindex = bisect.bisect_right(basho, now)
        if nowindex == lenbasho:
            now = basho[0]
            kaisu += 1
        else:
            now = basho[nowindex]
    else:
        flag = False
        break
if flag:
    ans = kaisu * len(s) + now + 1
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
s = input()
t = input()
cnt = 0
last = 0
b = [{} for i in range(len(s))]
b[-1][s[-1]] = len(s) - 1
for i in range(len(s)-1)[::-1]:
    b[i] = b[i + 1].copy()
    b[i][s[i]] = i
if t[0] in b[0]:
    last = b[0][t[0]]
else:
    print(-1)
    exit()
for i in t[1:]:
    if last < len(s) - 1 and i in b[last + 1]:
        last = b[last + 1][i]
    else:
        if i not in s:
            print(-1)
            exit()
        last = b[0][i]
        cnt +=1
print(cnt*len(s) + last + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

s = input()
t = input()

len_s = len(s)
set_s = set(s)
set_t = set(t)

if len(set_t - set_s) != 0:
    print(-1)
    sys.exit()

ss = s + s
indexes_c = {}
for c in set_t:
    indexes = list()
    index = 0
    index_sum = 0
    word = ss
    while index_sum < len_s:
        index = word.index(c)+1
        index_sum += index
        indexes.append(index_sum)
        word = word[index:]
    indexes_c[c] = indexes

from bisect import bisect_right
ans = 0
for c in t:
    i = ans % len_s
    indexes = indexes_c[c]
    ans += indexes[bisect_right(indexes, i)] - i

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

s = input()
t = input()

len_s = len(s)
set_s = set(s)
set_t = set(t)

if len(set_t - set_s) != 0:
    print(-1)
    sys.exit()

n = {}
ss = s + s
ans = 0
for c in t:
    i = ans % len_s
    if not c in n:
        n[c] = [0] * len_s
    if n[c][i] == 0:
        n[c][i] = ss[i:].find(c) + 1
    ans += n[c][i]

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

s = input()
t = input()

t_set = set(t)

if len(t_set -set(s)) != 0:
    print(-1)
    sys.exit()

s_len = len(s)
def index_list(char):
    word = s
    ret = list()
    sum = 0
    try:
        while True:
            index = word.index(char)+ 1        
            sum+=index
            ret.append(sum)
            word = word[index:]
    except:
        if sum == 0:
            ret.append(-1)
    return ret

alpha_dict = dict()
for char in t_set:
    alpha_dict[char] = index_list(char)

index_old = 0
n_s = 0
for char in t:
    index = alpha_dict[char]
    
    flg = True
    
    if index[-1] <= index_old:
        pass
    else:
        index_old = index[bisect_right(index, index_old)]
        flg =False
    if flg:
        index_old = index[0]
        n_s += 1
        
print(n_s*s_len + index_old)

Submission status: Accepted

Solution code:
import sys
s = input()
t = input()
tset = set(t)
slen = len(s)
if len(tset - set(s)) != 0:
    print(-1)
    sys.exit()
s2t = [i - ord('a') for i in (s + s).encode('ascii')]
lut = [[-1 for _ in range(slen)] for _ in range(26)]
for c in tset:
  b = ord(c) - ord('a')
  j = 0
  for i in range(slen * 2 - 1, -1, -1):
    if s2t[i] == b:
      j = 0
    else:
      j += 1
    if i < slen:
      lut[b][i] = j
p = 0
for c in t:
  b = ord(c) - ord('a')
  p += lut[b][p % slen] + 1
print(p)

Submission status: Accepted

Solution code:
from bisect import bisect_left
 
ALPHABET = "abcdefghijklmnopqrstuvwxyz"
 
 
def main(s, t):
    positions = {char: [] for char in ALPHABET}
    for i, char in enumerate(s):
        positions[char].append(i)
 
    current = 0
    answer = 0
    for char in t:
        pos_num = len(positions[char])
        if pos_num < 1:
            return -1
        idx = bisect_left(positions[char], current)
        if idx < pos_num:
            current = positions[char][idx] + 1
        else:
            answer += len(s)
            idx = bisect_left(positions[char], 0)
            current = positions[char][idx] + 1
 
    answer += current
    return answer
 
 
s = input()
t = input()
print(main(s, t))

Submission status: Accepted

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

def func(S, T):

    merge_S = list(set(S))
    merge_T = list(set(T))
    for t in merge_T:
        if t not in merge_S:
            return -1

    S_2 = S+S
    len_s = len(S)

    ans = -1

    for t in T:
        ans += S_2[(ans+1)%len_s:].index(t) + 1

    return ans + 1

print(func(S,T))

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
#print(ord('a'))
#print(chr(98))
ss = []
ss1 = [[] for _ in range(26)]
ss2 = [[] for _ in range(26)]
for i in range(ls):
  ss1[ord(s[i]) - 97].append(i)
  ss2[ord(s[i]) - 97].append(i+ls)
for k in range(26):
  ss.append(ss1[k] + ss2[k])
ans = 0
mans = 0
import bisect
for j in range(lt):
  now = ord(t[j]) - 97
  if ss[now] == []:
    print(-1)
    break
  here = bisect.bisect_left(ss[now],mans)
  ans += ss[now][here] - mans + 1
  mans = ans % ls
else:
  print(ans)

Submission status: Accepted

Solution code:
#E問題
import math
import bisect
from collections import defaultdict

S = list(str(input()))
T = list(str(input()))

index = defaultdict(list)
for i,s in enumerate(S):
    index[s].append(i)

flag = 0
x = -1
loop = 0
for t in T:
    tindl = index[t]
    if len(tindl) == 0:
        print(-1)
        flag = 1
        break
    j = bisect.bisect(tindl,x)
    if j == len(tindl):
        loop+=1
        x = tindl[0]
    else:
        x = tindl[j]


if flag == 0:
    print(loop*len(S)+x+1)

Submission status: Accepted

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

for s in T:
  if not s in S:
    pos = -1
    break
  if s in S[pos%len(S):]:
    pos += S[pos%len(S):].index(s)+1
  else:
    pos += S.index(s)+len(S[pos%len(S):])+1
print(pos)

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    s2 = s * 2
    sett = list(set((t)))
    settindex = {}
    for i in sett:
        settindex[i] = sett.index(i)
        if i not in s:
            print(-1)
            return
    lens = len(s)
    # index[i文字目以降][settのindex]に何文字目にあるかが格納される
    index = [[-1] * len(sett) for _ in range(lens)]
    ans = 0
    n = 0
    for i in t:
        j = settindex[i]
        if index[n][j] == -1:
            index[n][j] = s2[n:].index(i)
        ans += index[n][j] + 1
        n += index[n][j] + 1
        n %= lens
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    T=ST()

    N = len(S)

    chr_where = defaultdict(list)
    for i,s in enumerate(S):
        chr_where[s].append(i)
    
    cnt = 0 #何度先頭に戻ったか
    now = -1
    for t in T:
        if not chr_where[t]:
            print(-1)
            exit()
        index = bisect_right(chr_where[t], now)
        if index >= len(chr_where[t]):
            now = chr_where[t][0]
            cnt += 1
        else:
            now = chr_where[t][index]
        
    print(cnt*N + now + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import *
 
S = input().rstrip()
T = input().rstrip()
 
LS = len(S)
index = defaultdict(list)
 
for i, s in enumerate(S):
  index[s].append(i)

x = -1
loop = 0
for t in T:
  arr = index[t]  
  if len(arr) == 0:
    print(-1)
    exit()  
  i = bisect(arr, x)  
  if i == len(arr):
    loop += 1
    x = arr[0]
  else:
    x = arr[i]

print(loop*LS+x+1)

Submission status: Accepted

Solution code:
from bisect import bisect_left

s = input()
t = input()

oa = ord('a')

l = [[] for _ in range(26)]
for i,c in enumerate(s):
    l[ord(c) - oa].append(i)

x = -1
p = 0
for c in t:
    ll = l[ord(c)-oa]
    if len(ll)==0:
        print(-1)
        exit()

    y = bisect_left(ll, x)
    if y==len(ll):
        p += 1
        x = ll[0]+1
    else:
        x = ll[y]+1

print(p*len(s)+x)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s = list(input())
t = list(input())
ds = defaultdict(int)
dsl = defaultdict(list) 
for i in range(len(s)):
    ds[s[i]] += 1
    dsl[s[i]].append(i)


ans = 0
now = -1  # ここが-1じゃないと、最初の遷移でsの最初の文字を使えない
for i in range(len(t)):
    if ds[t[i]] == 0:
        print("-1")
        exit()
    else:
        index = bisect.bisect_right(dsl[t[i]], now)
        if index == len(dsl[t[i]]):
            index = -1
        if dsl[t[i]][index] > now:
            ans += (dsl[t[i]][index] - now)
            now = dsl[t[i]][index]
        else:
            ans += dsl[t[i]][0] + (len(s) - now)
            now = dsl[t[i]][0]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s = list(input())
t = list(input())
ds = defaultdict(int)  # ｓに含まれる文字のそれぞれの数
dsl = defaultdict(list)  # ｓの文字のindex
for i in range(len(s)):
    ds[s[i]] += 1
    dsl[s[i]].append(i)


ans = 0
now = -1  # ここが-1じゃないと、最初の遷移でsの最初の文字を使えない
for i in range(len(t)):
    if ds[t[i]] == 0:  # ｓにｔを構成する文字がない場合
        print("-1")
        exit()
    # elif ds[t[i]] == 1:
    #     if dsl[t[i]][0] > now:  # ｔの次の文字が現在地より右にある場合
    #         ans += (dsl[t[i]][0] - now)
    #     else:  # ｔの次の文字が現在地より左にある場合
    #         ans += dsl[t[i]][0] + (len(s) - now)
    #     now = dsl[t[i]][0]
    else:
        index = bisect.bisect_right(dsl[t[i]], now)
        if index == len(dsl[t[i]]):
            index = -1
        if dsl[t[i]][index] > now:  # ｔの次の文字が現在地より右にある場合
            ans += (dsl[t[i]][index] - now)
            now = dsl[t[i]][index]
        else:  # ｔの次の文字が現在地より左にある場合
            ans += dsl[t[i]][0] + (len(s) - now)
            now = dsl[t[i]][0]

print(ans)

Submission status: Accepted

Solution code:
import bisect
s = list(input())
t = list(input())
from collections import defaultdict
ds = defaultdict(int)  # ｓに含まれる文字それぞれの数
dsl = defaultdict(list)  # ｓの文字の位置
for i in range(len(s)):
    ds[s[i]] += 1
    dsl[s[i]].append(i)


ans = 0
now = -1#ここが-1じゃないと、最初の遷移でsの最初の文字を使えない
for i in range(len(t)):
    if ds[t[i]] == 0:  # ｓにｔを構成する文字がない場合
        print("-1")
        exit()
    elif ds[t[i]] == 1:
        if dsl[t[i]][0] > now:  # ｔの次の文字が現在地より右にある場合
            ans += (dsl[t[i]][0] - now)
        else:  # ｔの次の文字が現在地より左にある場合
            ans += dsl[t[i]][0] + (len(s) - now)
        now = dsl[t[i]][0]
    else:
        index = bisect.bisect_right(dsl[t[i]], now)
        if index == len(dsl[t[i]]):
            index = -1
        if dsl[t[i]][index] > now:  # ｔの次の文字が現在地より右にある場合
            ans += (dsl[t[i]][index] - now)
            now = dsl[t[i]][index]
        else:  # ｔの次の文字が現在地より左にある場合
            ans += dsl[t[i]][0] + (len(s) - now)
            now = dsl[t[i]][0]

print(ans)

Submission status: Accepted

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

ds = {}  # ｓに含まれる文字それぞれの数
dsl = {}  # ｓの文字の位置
for i in range(len(s)):
    if s[i] not in ds.keys():
        ds[s[i]] = 0
        dsl[s[i]] = []
    ds[s[i]] += 1
    dsl[s[i]].append(i)

for i in range(len(t)):
    if t[i] not in ds.keys():
        ds[t[i]] = 0

#print(ds, dsl)

ans = 0
now = -1#ここが-1じゃないと、最初の遷移でsの最初の文字を使えない
for i in range(len(t)):
    if ds[t[i]] == 0:  # ｓにｔを構成する文字がない場合
        print("-1")
        exit()
    elif ds[t[i]] == 1:
        if dsl[t[i]][0] > now:  # ｔの次の文字が現在地より右にある場合
            ans += (dsl[t[i]][0] - now)
        else:  # ｔの次の文字が現在地より左にある場合
            ans += dsl[t[i]][0] + (len(s) - now)
        now = dsl[t[i]][0]
    else:
        index = bisect.bisect_right(dsl[t[i]], now)
        if index == len(dsl[t[i]]):
            index = -1
        if dsl[t[i]][index] > now:  # ｔの次の文字が現在地より右にある場合
            ans += (dsl[t[i]][index] - now)
            now = dsl[t[i]][index]
        else:  # ｔの次の文字が現在地より左にある場合
            ans += dsl[t[i]][0] + (len(s) - now)
            now = dsl[t[i]][0]

print(ans)

Submission status: Accepted

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

ds = {}  # ｓに含まれる文字それぞれの数
dsl = {}  # ｓの文字の位置
for i in range(len(s)):
    if s[i] not in ds.keys():
        ds[s[i]] = 0
        dsl[s[i]] = []
    ds[s[i]] += 1
    dsl[s[i]].append(i)

for i in range(len(t)):
    if t[i] not in ds.keys():
        ds[t[i]] = 0

#print(ds, dsl)

ans = 0
now = -1
for i in range(len(t)):
    if ds[t[i]] == 0:  # ｓにｔを構成する文字がない場合
        print("-1")
        exit()
    elif ds[t[i]] == 1:
        if dsl[t[i]][0] > now:  # ｔの次の文字が現在地より右にある場合
            ans += (dsl[t[i]][0] - now)
        else:  # ｔの次の文字が現在地より左にある場合
            ans += dsl[t[i]][0] + (len(s) - now)
        now = dsl[t[i]][0]
    else:
        index = bisect.bisect_right(dsl[t[i]], now)
        if index == len(dsl[t[i]]):
            index = -1
        if dsl[t[i]][index] > now:  # ｔの次の文字が現在地より右にある場合
            ans += (dsl[t[i]][index] - now)
            now = dsl[t[i]][index]
        else:  # ｔの次の文字が現在地より左にある場合
            ans += dsl[t[i]][0] + (len(s) - now)
            now = dsl[t[i]][0]

print(ans)

Submission status: Accepted

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

#contest
#son
wrap = 0
index = -1
for  i in t:
    index = s.find(i,index+1)
    if index != -1:
        continue
    wrap +=1
    index = s.find(i)
    if index ==  -1:
        print(-1)
        exit()
print(len(s)*wrap+index+1)

Submission status: Accepted

Solution code:
s = input()
t = input()
index = -1
Wrap = 0

for a in t:
  index = s.find( a, index+1)
  if index != -1:
    continue
  Wrap += 1
  index = s.find(a)
  if index == -1:
    print(-1)
    exit()
print(len(s)*Wrap + index +1)

Submission status: Accepted

Solution code:
#解説解答
S = input()
T = input()
ls = len(S)
lt = len(T)
s1 = [[] for _ in range(26)]
s2 = [[] for _ in range(26)]
for i in range(ls):
  s1[ord(S[i])-97].append(i)
  s2[ord(S[i])-97].append(i+ls)
s = [[] for _ in range(26)]
for k in range(26):
  s[k] = s1[k] + s2[k]
#print(s)
ans = 0
mans = 0
import bisect
for j in range(lt):
  now = ord(T[j])-97
  if s[now] == []:
    print(-1)
    break
  here = bisect.bisect_left(s[now],mans)
  ans = ans - mans + s[now][here] + 1
  mans = (s[now][here] + 1) % ls
  #print(now,here,s[now],s[now][here],ans,mans)
else:
  print(ans)

Submission status: Accepted

Solution code:
import collections
import bisect

s = input()
t = input()
s_index = {}
	
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		if cursor > s_index[target][-1]:
			find = False
		else:
			j = bisect.bisect_left(s_index[target], cursor)
			find = True
		diff = s_index[target][j] - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def lower_bound(l,k):
    def isOk(i):
        return l[i]>k

    ok = len(l)
    ng = -1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2

        if isOk(mid):
            ok = mid
        else:
            ng = mid
    return ok

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

d = {}
for c in t:
    if c in d:
        continue
    else:
        d[c] = []
    for i in range(2*n):
        if s[i%n]==c:
            d[c].append(i)
res = -1
for i in range(m):
    c = t[i]
    if len(d[c])==0:
        print(-1)
        exit()

    j = lower_bound(d[c],res%n)
    res += d[c][j] - res%n

print(res+1)

Submission status: Accepted

Solution code:
import sys
s = input()
t = input()
#s = "contest"
#t = "son"

wrap_count = 0
index = -1

for c in t:
    index = s.find(c, index+1)
    if index != -1:
        continue
    wrap_count += 1
    index = s.find(c)
    if index == -1:
        print(-1)
        sys.exit()

print(len(s) * wrap_count + index + 1)

Submission status: Accepted

Solution code:
#E
import bisect

s = input()
t = input()
lens = len(s)

s_n = {}
for i in range(len(s)):
    if s[i] in s_n:
        s_n[s[i]].append(i+1)
    else:
        s_n[s[i]] = [i+1]
        
#print(s_n)

d1=0
d2=0
for i in t:
    if not(i in s_n):
        print(-1)
        break
    else:
        if d1 >= s_n[i][-1]:
            d1 = s_n[i][0]
            d2 += lens
        else:
            index = bisect.bisect(s_n[i],d1)
            d1 = s_n[i][index]
else:
    print(d1+d2)

Submission status: Accepted

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

index = -1
rep = 0
length = len(s)
ans = 0
for tar in t:
    if index+1 == length:
        rep += 1
        index = -1
        
    kari_index = s[index+1:].find(tar)

    if kari_index == -1:
        tmp = s.find(tar)
        if  tmp == -1:
            ans = -1
        else:
            rep += 1
            index = tmp
    else:
        index += kari_index + 1

if ans != -1:
    ans = rep * len(s) + index + 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

S = input().rstrip()
T = input().rstrip()

LS = len(S)
index = defaultdict(list)

for i, s in enumerate(S):
  index[s].append(i)
  
x = -1
for t in T:
  arr = index[t]
  if len(arr) == 0:
    print(-1)
    exit()
  y = (x+1)%LS
  i = bisect_left(arr, y)
  if i < len(arr):
    next_x = (x+1) + arr[i] - y
  else:
    next_x = (x+1) + arr[0] + LS - y
  x = next_x
ans = x+1
print(ans)

Submission status: Accepted

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

dic = dict()

for i in range(len(s)):
    w = s[i]
    if not w in dic:
        dic[w] = [i]
    else:
        dic[w].append(i)

ans = 0
last = 0

import bisect
for i in range(len(t)):
    w = t[i]
    if not w in dic:
        print(-1)
        exit()
    index = bisect.bisect_left(dic[w], last)
    
    if index < len(dic[w]):
        num = dic[w][index]
        ans -= last
        ans += num + 1
        last = num + 1
    else:
        ans -= last
        ans += len(s)
        ans += dic[w][0] + 1
        last = dic[w][0] + 1

print(ans)

Submission status: Accepted

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


for ch in t:
    if ch not in s:
        print('-1')
        exit()

x = s
for ch in t:
    p = x.find(ch) + 1
    if p == 0:
        ans += len(x)
        p = s.find(ch) + 1
        x = s
    ans += p
    
    x = x[p:]

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right
s=sys.stdin.readline().strip()
t=sys.stdin.readline().strip()

len_s=len(s)


C={}
for i,a in enumerate(s*2):
		if a not in C:
			C[a]=[i]
		else:
			C[a].append(i)


pointer=-1
mul=0

for x in t:
	try:
		idx=bisect_right(C[x],pointer)
	except:
		print -1
		quit()

	pointer=C[x][idx]

	if len_s<=pointer:
			mul+=1
			pointer-=len_s


print mul*len_s+pointer+1

Submission status: Accepted

Solution code:
s = input()
t = input()
if set(t).issubset(set(s)):
    i = 0
    x = s
    for k in t: 
        p = x.find(k) + 1
        if p == 0:
            i += len(x)
            p = s.find(k) + 1
            x = s
        i += p
        x = x[p:]
    print(i)
else:
    print(-1)

Submission status: Accepted

Solution code:
from bisect import bisect


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

    pos = {}
    for i, c in enumerate(S):
        if c not in pos.keys():
            pos[c] = []
        pos[c].append(i)

    ret = 0
    tmp = -1
    for c in T:
        if c not in pos.keys():
            print(-1)
            return
        idx = bisect(pos[c], tmp)
        if idx == len(pos[c]):
            ret += len(S)
            tmp = pos[c][0]
        else:
            tmp = pos[c][idx]

    ret += tmp + 1
    print(ret)
    return


if __name__ == "__main__":
    main()