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.

Solution (Python):
s = input()
t = input()
N, M = len(s), len(t)

schr, indchr = dict(), dict()
for i in range(N):
    if s[i] in schr:
        schr[s[i]].append(i+1) 
    else:
        schr[s[i]] = [i+1]
        indchr[s[i]] = 0

schrset = set(schr)
ans, pos, pre, back = 0, 0, set(), True
for i in range(M):
    if t[i] in schrset:
        c = schr[t[i]]
        if c[-1] <= pos:
            ans += N - pos + c[0]
            pos = c[0]
            if not back:
                for x in indchr.keys():
                    indchr[x] = 0
                back, pre = True, set()
        else:
            j = indchr[t[i]]
            while c[j] <= pos:
                j += 1
            if j > 0:
                pre.add(t[i])
            ans += c[j] - pos
            pos, back, indchr[t[i]] = c[j], False, j
    else:
        print(-1)
        exit()
print(ans)

Solution (Python):
from bisect import bisect_right

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

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

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        next_index = bisect_right(obj[char], temp_num)
        if next_index == len(obj[char]):
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = obj[char][next_index]

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

Solution (Python):

"""
Created on Mon Feb 17 09:13:00 2020

@author: msaleh1
"""

def upper_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = int(l + (r - l) / 2)
        if nums[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return l


mx = pow(10,100)

s = input()
t = input()

    
cnt_s = dict()
cnt_t = dict()

for c in t:
    if c in cnt_t:
        cnt_t[c]+=1
    else:
        cnt_t[c] = 1


for idx in range(len(s)):
    if s[idx] in cnt_s:
        cnt_s[s[idx]].append(idx)  
    else:
       cnt_s[s[idx]] = [idx]


for x in cnt_t:
    if x not in cnt_s:
        print(-1)
        exit(0)
    else:
        if(cnt_t[x] > mx*len(cnt_s[x])):
            print(-1)
            exit(0)
            
cur_indx =-1
skp =0
ans = 0

for x in t:
    temp_idx = upper_bound(cnt_s[x],cur_indx)
    if(temp_idx == len(cnt_s[x])):
        skp+=1
        cur_indx = cnt_s[x][0]
    else:
        cur_indx = cnt_s[x][temp_idx];
if(skp >= mx):
    print(-1)
else:
    print(skp*len(s)+cur_indx+1)

Solution (Python):

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

s = read()[:-1]
t = read()[:-1]

if set(t) - set(s):
    print(-1)
    exit()



mojiidx = defaultdict(lambda: [])
for i, ss in enumerate(s + s):
    mojiidx[ss].append(i)



for i, ss in enumerate(s):
    if ss == t[0]:
        now = i
        break

for tt in t[1:]:
    idx = now % len(s)
    
    ls = mojiidx[tt]
    tmp = ls[bisect_right(ls, idx)] - idx
    now += tmp
print(now + 1)

Solution (Python):

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

s = read()[:-1]
t = read()[:-1]

if set(t) - set(s):
    print(-1)
    exit()



mojiidx = defaultdict(lambda: [])
for i, ss in enumerate(s + s):
    mojiidx[ss].append(i)



for i, ss in enumerate(s):
    if ss == t[0]:
        now = i
        break

for tt in t[1:]:
    idx = now % len(s)
    
    ls = mojiidx[tt]
    tmp = ls[bisect_right(ls, idx)] - idx
    now += tmp
print(now + 1)

Solution (Python):
from bisect import bisect_right
from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]

if set(t) - set(s):
    print(-1)
    exit()





mojiidx = defaultdict(lambda: [])
for i, ss in enumerate(s + s):
    mojiidx[ss].append(i)


skiptable = []
for i in range(0, len(s)):
    tmp = {}
    for c, ls in mojiidx.items():
        tmp[c] = ls[bisect_right(ls, i)] - i
    skiptable.append(tmp)





for i, ss in enumerate(s):
    if ss == t[0]:
        now = i
        break

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

Solution (Python):
from bisect import bisect_right
from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]

if set(t) - set(s):
    print(-1)
    exit()





mojiidx = defaultdict(lambda: [])
for i, ss in enumerate(s + s):
    mojiidx[ss].append(i)


skiptable = []
for i in range(0, len(s)):
    tmp = {}
    for c, ls in mojiidx.items():
        tmp[c] = ls[bisect_right(ls, i)] - i
    skiptable.append(tmp)





for i, ss in enumerate(s):
    if ss == t[0]:
        now = i
        break

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

Solution (Python):





'''
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

tmp = {}  
skiptable = [None] * (len(s) + 1)


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] = tmp.copy()  
    tmp[moji] = 0  




for i, ss in enumerate(s):
    if ss == t[0]:
        now = i + 1
        break

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

Solution (Python):
import bisect


def bisect_search(f, val=0, l=0, r=10**6):

    

    eps = 10**(-5)
    while True:

        c = (l+r)//2
        print(l, c, r)
        input()
        if f(c) == val and f(c-1) != val:
            return c
        
        

        if f(c) > val:
            r = c

        else:
            l = c

        if l == r:
            return False



def next(ch,k):
    global N,dcs
    k_=k%N
    
    
    
    
    
    val = dcs[ch][k_-1]+1
    if k_==0:
        val=1

    A=bisect.bisect_left(dcs[ch],val,k_,min(k_+N,2*N-1))
    B = N*((k//N))
    

    return A+B


import numpy as np

s=input()
t=input()

td=list(set(t))

N=len(s)
d={}

import sys

R = set(list(s))
L = set(list(t))

if not(L <= R):
    print(-1)
    sys.exit()

for std in td:
    d[std] =[0]*(2*N)



for i in range(len(s)*2):
    

    for std in td:            
        if s[i%N]==std:
            d[std][i]=1



dcs={}
for std in td:
    dcs[std]=np.cumsum(d[std])


last=-1
for ts in t:
    
    last=next(ts,last+1)


print(last+1)

Solution (Python):
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
T = sr()
len_S = len(S)
indexes_S = defaultdict(list)
for i, s in enumerate(S):
    indexes_S[s].append(i)

x = -1 
for t in T:
    if len(indexes_S[t]) == 0:
        print(-1); exit()
    arr = indexes_S[t]
    y = (x+1) % len_S
    next_i = bisect.bisect_left(arr, y) 
    if next_i < len(arr):
        x = (x+1) + arr[next_i] - y
    else:
        x = (x+1) + arr[0] + len_S - y 

print(x+1)

Solution (Python):
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
pc = ''
for c in T:
  if pc==c:
    p += 1
    ans += 1
  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]
  pc = c
print(ans)

Solution (Python):
from collections import defaultdict
from bisect import bisect_right
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 = -1
for t in T:
    target_char_appeared_indexes = D[t]
    bi = bisect_right(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]



print(ans + marker + 1)

Solution (Python):



import bisect

s = input()
t = input()

s_dict = {c:[] for c in s}
for i, c in enumerate(s):
  s_dict[c].append(i)

len_s = len(s)

ans = 0
prev_i = -1
for c in t:
  if c not in s_dict:
    ans = -1
    prev_i = -1
    break;
  else:
    if s_dict[c][-1] <= prev_i:
      ans += len_s 
      prev_i = s_dict[c][0]
    else:
      prev_i = s_dict[c][bisect.bisect_right(s_dict[c], prev_i, lo=0, hi=len(s_dict[c]))]


print(ans + prev_i + 1)

Solution (Python):
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()

if set(s) >= set(t):
    d = defaultdict(list)
    for i, x in enumerate(s * 2):
        d[x].append(i)
    
    ans = 0
    cur = 0
    N = len(s)
    for x in t:
        cur_new = d[x][bisect_left(d[x], cur)]
        ans += cur_new - cur + 1
        cur = (cur_new + 1) % N

    print(ans)
else:
    print(-1)

Solution (Python):
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


cnt = 0
tmp = 0
for i in range(m):
    
    if tmp == n or res[tmp][ord(T[i])-ord("a")] == n:
        cnt += n
        tmp = 0
    tmp = res[tmp][ord(T[i])-ord("a")]  
    tmp += 1  
cnt += tmp  
print(cnt)

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


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  









set_S = set(list(S))
for i in range(len(T)):
    if T[i] not in set_S:
        print(-1)
        exit()
cnt = 0
tmp = 0
for i in range(len(T)):
    
    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")]  
    tmp += 1
cnt += tmp
print(cnt)

Solution (Python):
from collections import defaultdict
from bisect import bisect_right

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_right(d[t],pre)
        if index > len(d[t])-1:
            pre = 0
            loop += 1
            index = bisect_right(d[t],pre)
        pre = d[t][index]
        
    ans = loop * len_S + pre
    print(ans)






if __name__ == "__main__":
    main()

Solution (Python):
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] + 1
        else:
            p = d[i][0] + 1
            ans += orig_size
    
    print(ans+p)

Solution (Python):
from bisect import bisect_left
from collections import defaultdict

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

grid = defaultdict(list)
for idx, s in enumerate(S + S):
    grid[s].append(idx)

ans = 0
cur = 0
lenS = len(S)
for t in T:
    if t in grid:
        tList = grid[t]
        ncur = tList[bisect_left(tList, cur)]
        ans += ncur - cur + 1
        cur = (ncur + 1) % lenS
    else:
        ans = -1
        break

print(ans)

Solution (Python):
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]:
        idx = bisect_left(grid[t], cur)
        if idx == glen[t]:
            cnt += 1
            ncur = grid[t][0] + 1
        else:
            ncur = grid[t][idx] + 1
            cnt = cnt + (ncur <= idx)
        cur = ncur
    else:
        cnt = 0
        cur = -1
        break

print(cur + len(S) * cnt)

Solution (Python):


import bisect

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


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


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

loc=-1
count=0

for index,item in enumerate(t):
    temp=bisect.bisect(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+1+count*len(s))

Solution (Python):
from collections import defaultdict
import bisect
s = input()
t = input()
ns = len(s)
nt = len(t)
word = defaultdict(int)
wordnum = defaultdict(int)
for i in range(ns):
  if word[s[i]] != 0:
    word[s[i]].append(i+1)
  else:
    word[s[i]] = [i+1]
  wordnum[s[i]] += 1
cnt = 0
pnt = 0
for i in range(nt):
  x = t[i]
  if word[x] != 0:
    pos = bisect.bisect_right(word[x],pnt)
    if pos == wordnum[x] or pnt>word[x][pos]:
      cnt += 1
    if pos == wordnum[x]:
      pnt = word[x][0]
    else:
      pnt = word[x][pos]
  else:
    print(-1)
    exit()
print(cnt*ns+pnt)

Solution (Python):
from collections import defaultdict
import bisect
s = input()
t = input()
ns = len(s)
nt = len(t)
word = defaultdict(int)
wordnum = defaultdict(int)
for i in range(ns):
  if word[s[i]] != 0:
    word[s[i]].append(i+1)
  else:
    word[s[i]] = [i+1]
  wordnum[s[i]] += 1
cnt = 0
pnt = 0
for i in range(nt):
  x = t[i]
  if word[x] != 0:
    pos = bisect.bisect_right(word[x],pnt)
    if pos == wordnum[x] or pnt>word[x][pos]:
      cnt += 1
    if pos == wordnum[x]:
      pnt = word[x][0]
    else:
      pnt = word[x][pos]
  else:
    print(-1)
    exit()
print(cnt*ns+pnt)

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


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
    cur1 = (i + 1) % N
    if next[cur1].get(c) is None:
        print(-1)
        exit(0)
    n = next[cur1][c]
    if cur < n:
        i += n - cur
    elif n < cur:
        i += N - (cur - n)
    else:
        i += N
print(i + 1)

Solution (Python):
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]
    for i in d:
        d[i] = sorted(d[i])
    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())

Solution (Python):
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] + 1
    return c * len(S) + r

print(main())

Solution (Python):
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    m = 0
    st = s
    for i in t:
        if i in st:
            j = st.index(i)
            m += j + 1
            st = st[j+1:]
        else:
            m += len(st)
            st = s
            j = st.index(i)
            st = st[j+1:]
            m += j + 1
    return m
print(main())

Solution (Python):
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_right(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)

Solution (Python):
s = input()
t = input()
d = {i:[] for i in "abcdefghijklmnopqrstuvwxyz"}
for i in range(len(s)):
    d[s[i]].append(i)
for i in t:
    if len(d[i]) == 0:
        print(-1)
        exit()

def binary_search(arr, k):
    l, r = 0, len(arr)-1
    while l <= r:
        m = l+r >> 1
        if arr[m] < k:
            l = m+1
        else:
            r = m-1
    return l

a, b = 0, 0
for i in t:
    j = binary_search(d[i], a)
    if len(d[i]) <= j:
        a = 0
        b += 1
        j = binary_search(d[i], 0)
    a = d[i][j] + 1
print(b * len(s) + a)

Solution (Python):
s = input()
t = input()
d = {i:[] for i in "abcdefghijklmnopqrstuvwxyz"}
for i in range(len(s)):
    d[s[i]].append(i)
for i in t:
    if len(d[i]) == 0:
        print(-1)
        exit()

def binary_search(arr, k):
    l, r = 0, len(arr)-1
    while l <= r:
        m = l+r >> 1
        if arr[m] < k:
            l = m+1
        else:
            r = m-1
    return l

a, b = 0, 0
for i in t:
    j = binary_search(d[i], a)
    if len(d[i]) <= j:
        a = 0
        b += 1
        j = binary_search(d[i], 0)
    a = d[i][j] + 1
print(b * len(s) + a)

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


for e,i in enumerate(a):
    t=ord(i)-ord('a')
    dp[t].append(e)

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+1
    
    if e == len(b)-1: ans = c*len(a)+ F+1
print(ans)

Solution (Python):


S = input()
T = input()
if not set(T) <= set(S):
    print(-1)
    exit()
now = -1
rep = 0
for t in T:
    now = S.find(t,now+1)
    if now == -1:
        rep += 1
        now = S.find(t)
print(rep*len(S)+now+1)

Solution (Python):
from bisect import bisect_left
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
s = s+s
for i in range(2*N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
nex = [[0]*N for _ in range(26)]
for now in range(N):
    for alp in range(26):
        if not lis[alp]:
            continue
        i = bisect_left(lis[alp],now+1)
        
        nex[alp][now] = lis[alp][i] - now
ans = 0
now = 0
tN = len(t)
for i in range(tN):
    alp = ord(t[i])-97
    ne = nex[alp][now]
    ans += ne
    if now+ne >= N:
        now += ne-N
    else:
        now += ne
    
print(ans)

Solution (Python):
from bisect import bisect

def indexes(L, x):
    INDEXES = []
    for i in range(len(L)):
        if L[i] == x:
            INDEXES.append(i)
    return INDEXES


s = input()
t = input()

ss = s * 2
alphabets = "abcdefghijklmnopqrstuvwxyz"
INDEXES = {c:indexes(ss, c) for c in alphabets}

def index(i, c):
    return INDEXES[c][bisect(INDEXES[c], i)]

if not INDEXES[t[0]]:
    print(-1)
    exit()
now = INDEXES[t[0]][0]

answer = now + 1
mod = len(s)
for c in t[1:]:
    if not INDEXES[c]:
        print(-1)
        exit()
    next = index(now, c)
    answer += next - now
    now = next % mod

print(answer)

Solution (Python):
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]:
            
            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(s_pointer[t_c], s_length[t_c]):
                if last_index < s_indexes[t_c][j]:
                    s_pointer[t_c] = j
                    break
            else:
                
                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()

Solution (Python):
from collections import defaultdict
import bisect
s = input()
t = input()
dicta = defaultdict(list)
for a,b in enumerate(s):
    dicta[b] += [a]
snow = -1
count = 0
flag = True
for i in t:
    if not dicta[i]:
        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)

Solution (Python):
from collections import defaultdict
import bisect
s = input()
t = input()
dicta = defaultdict(list)
for a,b in enumerate(s):
    dicta[b] += [a]
snow = -1
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)

Solution (Python):
from collections import defaultdict
import bisect
s = input()
t = input()
dicta = defaultdict(list)
for i in range(len(s)):
    dicta[s[i]] += [i]
snow = -1
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)

Solution (Python):
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) + snow+1)
    else:
        print(-1)

Solution (Python):
from bisect import bisect_right
def find_gt(a, x):
  i = bisect_right(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 = 0
cur = -1

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline









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

s = set(S)
t = set(T)
f = True
for v in t:
    if v not in s:
        f = False
        break
if f == False:
    print(-1)
    exit()

m = defaultdict(list)
for i in range(len(S)):
    m[S[i]].append(i)

counter = 0
before = -1
for v in T:
    c = m[v]
    index = bisect.bisect_left(c, before+1)
    if index >= len(c):
        before = -1
        index = bisect.bisect_left(c, before+1)
        before = c[index]
        counter += 1
    else:
        before = c[index]

print(counter * len(S) + before + 1)

Solution (Python):
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 = -1
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)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

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

NX=[[-1]*26 for _ in range(len(S))]

for i in range(len(S)*2-1)[::-1]:
    idx = i%lenS
    idx2 = (i+1)%lenS
    for j in range(26):
        if NX[idx2][j] != -1:
            NX[idx][j] = NX[idx2][j] + 1
    NX[idx][ord(S[idx2])%26] = 1







res = 0
prev=lenS-1
for c in T:
    v = NX[prev][ord(c)%26]
    if v == -1:
        print(-1)
        exit()
    else:
        res += v
        prev = (prev + v)%lenS

print(res)

Solution (Python):
import sys
import bisect
def input():
    return sys.stdin.readline()[:-1]
s=input()
t=input()
ss=s+s
al=[-1]*26
for i in range(len(ss)):
    tmp=ord(ss[i])-ord("a")
    if al[tmp]==-1:
        al[tmp]=[i]
    else:
        al[tmp].append(i)
ans=0
now=0
for i in range(len(t)):
    tmp=ord(t[i])-ord("a")
    if al[tmp]==-1:
        print(-1)
        exit()
    tmp2=bisect.bisect_left(al[tmp],now)
    
    ans+=al[tmp][tmp2]-now+1
    now=al[tmp][tmp2]+1
    if now>=len(s):
        now-=len(s)
    
print(ans)

Solution (Python):
from bisect import bisect_right
s = input().strip()
t = input().strip()
D = {}
for i in range(len(s)):
    a = s[i]
    if a not in D:
        D[a] = []
    D[a].append(i+1)
A = sorted(list(set(list(s))))
A.append(chr(123))
B = sorted(list(set(list(t))))
cur = 0
flag = 0
for i in range(len(B)):
    while True:
        if A[cur]<B[i]:
            cur += 1
        elif A[cur]==B[i]:
            break
        else:
            flag = 1
            break
    if flag==1:break
if flag==1:
    print(-1)
else:
    C = []
    cur = -1
    for i in range(len(t)):
        b = t[i]
        ind = bisect_right(D[b],cur)%len(D[b])
        C.append(D[b][ind])
        cur = D[b][ind]
    cnt = 0
    for j in range(1,len(C)):
        if C[j]<=C[j-1]:
            cnt += 1
    print(len(s)*cnt+C[-1])

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


def n(i):
    return ord(i) - 97


ss = set(s)
ts = set(t)
if not ts.issubset(ss):
    print(-1)
else:
    
    sp = s + s
    mp = [[-1] * 26 for _ in range(len(sp) + 1)]
    for i in range(len(sp) - 1, -1, -1):
        for j in range(26):
            if mp[i + 1][j] > -1:
                mp[i][j] = mp[i + 1][j] + 1
            mp[i][n(sp[i])] = 0
    i = 0
    im = 0
    for c in t:
        cn = n(c)
        i += mp[im][cn] + 1
        im = i % len(s)
    print(i)

Solution (Python):
import collections
import bisect
S = input()
T = input()
N = len(S)
 
d = collections.defaultdict(list)
for i, s in enumerate(S):
  d[s].append(i + 1)

ans = 0
end = 0
isOK = True
i = 0

for t in T:
  if len(d[t])==0: 
    isOK = False
    break
  dic = d[t]
  idx = bisect.bisect_right(dic, i) 
  if len(dic) == idx:
    i = dic[0]  
    end += 1    
  else:
    i = dic[idx]

if isOK:
  ans = N * end + i
else:
  ans = -1
    
print(ans)

Solution (Python):
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
  exit()

ss=s*2
ind=-1
ans=0
for c in t:
  nex=ss[ind+1:].find(c)
  ind=(ind+1)+nex
  if ind>=len(s):
    ind-=len(s)
    ans+=len(s)

print(ans+ind+1)