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):
from bisect import bisect
S = input()
T = input()

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

for c in set(T):
    if not cs[ord(c) - ord('a')]:
        print(-1)
        exit()

rnd = 0
k = -1
for t in T:
    ti = ord(t) - ord('a')
    i = bisect(cs[ti], k)
    if i == len(cs[ti]):
        k = cs[ti][0]
        rnd += 1
    else:
        k = cs[ti][i]

print(rnd*len(S) + k + 1)

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

ct = 0
k = 0
for i in t:
    f = s.find(i, k)
    if f < 0:
        ct += 1
        f = s.find(i)
        if f == -1:
            print(-1)
            break
        else:
            k = f+1
    else:
        k = f+1
else:
    print(ct*len(s)+k)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

s, t = input(), input()
se = set(s)
for c in t:
    if c not in se:
        print(-1)
        exit()
dic = defaultdict(list)
for i, c in enumerate(s, 1):
    dic[c].append(i)
n = len(s)
i = ans = dic[t[0]][0]
for c in t[1:]:
    dicc = dic[c]
    j = bisect_right(dicc, i)
    if len(dic[c]) <= j:
        ans += n-i+dicc[0]
        i = dicc[0]
    else:
        ans += dicc[j]-i
        i = dicc[j]
print(ans)

Solution (Python):
from bisect import bisect
s = input()
t = input()
def ctoi(c):
	return ord(c) - ord("a")
if not (set(s) >= set(t)):
	print(-1)
else:
	alph = [[] for _ in range(26)]
	for i in range(len(s)):
		alph[ctoi(s[i])].append(i)
	for a in alph:
		if a:
			a.append(a[0] + len(s))
	
	cur = len(s)-1
	ans = 0
	for i in range(len(t)):
		ind = bisect(alph[ctoi(t[i])], cur)
		ans += alph[ctoi(t[i])][ind] - cur
		cur = alph[ctoi(t[i])][ind] % len(s)
	print(ans)

Solution (Python):
S = [ord(s)-97 for s in input().strip()]
T = [ord(t)-97 for t in input().strip()]

ls = len(S)

inf = 2*10**9

table = [None]*(2*ls)

ss = S + S
t = [inf]*26
for i in range(2*ls-1, -1, -1):
    z = ss[i]
    t[z] = i
    table[i] = t[:]

if any(table[0][ti] == inf for ti in T):
    print(-1)

else:
    ans = -1
    for ti in T:
       j = ans%ls
       k = table[j+1][ti] % ls
       if j < k:
           ans += k - j
       else:
           ans += ls + k - j
    print(ans + 1)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return


def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return


def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return


def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return


def E():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    d = defaultdict(lambda : [])
    for i in range(n):
        d[s[i]].append(i)
    f = [-1]*m
    alp = list("abcdefghijklmnopqrstuvwxyz")
    for i in range(m):
        if not d[t[i]]:
            print(-1)
            return
        j = bisect.bisect_right(d[t[i]],f[i-1])
        if j == len(d[t[i]]):
            f[i] = d[t[i]][0]
        else:
            f[i] = d[t[i]][j]
    ans = 0
    for i in range(m-1):
        if f[i] >= f[i+1]:
            ans += 1
    print(ans*n+f[-1]+1)
    return


def F():

    return


if __name__ == "__main__":
    E()

Solution (Python):
import bisect
s = input()
t = input()
d = {}
for i in range(len(s)):
  if s[i] in d:
    d[s[i]] += [i]
  else:
    d[s[i]] = [i]
c = 0
cur = -1
for i in t:
  if i not in d:
    print(-1)
    exit()
  if cur < d[i][-1]:
    cur = d[i][bisect.bisect_right(d[i],cur)]
    continue
  else:
    cur = d[i][0]
    c += 1
print(c*len(s)+cur+1)

Solution (Python):
from collections import Counter
s = input()
t = input()

cs = Counter(s)
ct = Counter(t)

ok = 1
for k in ct:
    if k not in cs:
        ok = 0
if not ok:
    print("-1")
    exit(0)

N = len(s)
D = [-1]*26
E = [None]*(N+1)
cA = ord('a')
for i in range(N-1, -1, -1):
    E[i+1] = D[:]
    D[ord(s[i])-cA] = i
E[0] = D

ans = 0
p = -1
for c in t:
    v = ord(c) - cA
    q = E[p+1][v]
    if q == -1:
        q = E[0][v]
        ans += q + (N - p)
    else:
        ans += (q - p)
    p = q
print(ans)

Solution (Python):
from collections import Counter
s = input()
t = input()

cs = Counter(s)
ct = Counter(t)

ok = 1
for k in ct:
    if k not in cs:
        ok = 0
if not ok:
    print("-1")
    exit(0)

N = len(s)
D = [-1]*26
E = [None]*(N+1)
cA = ord('a')
for i in range(N-1, -1, -1):
    E[i+1] = D[:]
    D[ord(s[i])-cA] = i
E[0] = D

ans = 0
p = -1
for c in t:
    v = ord(c) - cA
    q = E[p+1][v]
    if q == -1:
        q = E[0][v]
        ans += q + (N - p)
    else:
        ans += (q - p)
    p = q
print(ans)

Solution (Python):

from math import sqrt
from heapq import heapify, heappop, heappush
from string import ascii_lowercase as abc
from bisect import bisect
import sys

sys.setrecursionlimit(10**9)
from fractions import gcd
def inpl(): return list(map(int, input().split()))

S = input()
T = input()

D = {k:[] for k in abc}
for i in range(len(S)):
    D[S[i]].append(i)

rap = 0
ix = -1

for j in range(len(T)):
    t = T[j]
    if len(D[t]) == 0:
        print(-1)
        break
    k = bisect(D[t], ix)
    if k == len(D[t]):
        rap += 1
        ix = D[t][0]
    else:
        ix = D[t][k]
else:
    print(len(S)*rap + ix+1)

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

n = len(s)

p = [[] for _ in range(26)]
for i in range(n):
    p[ord(s[i])-97].append(i+1) 


res = 0
b = 0
for e in t:
    k = ord(e)-97
    if len(p[k]) == 0:
        print(-1)
        exit()
    else:
        r = bisect.bisect_right(p[k],b)
        if len(p[k]) > r:
            res += p[k][r]-b
            b = p[k][r]
        else:
            res += n-b+p[k][0]
            b = p[k][0]

print(res)

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

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

for i in range(len(s)):
	a[ord(s[i]) - ord('a')].append(i)

cnt = 1

prev = -1
i = 0 
while(i < len(t)):
	l = t[i]
	indi = ord(l) - ord('a')
	li = a[indi]

	if(li == []):
		print(-1)
		exit(0)

	if li[-1] <= prev:
		prev = -1
		cnt += 1

	start = 0
	end = len(li) - 1
	ans = -1
	while(start <= end):
		mid = (start + end)//2
		if li[mid] > prev:
			ans = mid
			end = mid - 1
		else:
			start = mid + 1
	
	prev = li[ans]

	i += 1


final = cnt*len(s) - (len(s) - prev - 1)
print(final)

Solution (Python):
import bisect
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = sys.stdin.readline().rstrip()
T = sys.stdin.readline().rstrip()

pos = defaultdict(list)
for i, c in enumerate(S):
    pos[c].append(i)
for c in pos.keys():
    pos[c] += [p + len(S) for p in pos[c]]

ans = 0
i = 0
for t in T:
    if not pos[t]:
        print(-1)
        exit()
    p = bisect.bisect_left(pos[t], i)
    ans += pos[t][p] - i + 1
    i = pos[t][p] % len(S) + 1
print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

S = input()
T = input()

ALPs = defaultdict(list)

for i,s in enumerate(S):
    ALPs[s].append(i+1)

Ls = [len(ALPs[chr(i)]) for i in range(97,97+28)]


itr = 0
cnt = 0 
for t in T:
    L = Ls[ord(t)-97]
    if L == 0:
        print(-1)
        exit()
    else:
        ind = bisect.bisect_right(ALPs[t],itr)
        if ind == L:
            itr = ALPs[t][0]
            cnt += 1
        else:
            itr = ALPs[t][ind]
        


ans = cnt*len(S) + itr

print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

s = ns()
t = ns()

hey = set(list(s))
for c in t:
    if c not in hey:
        print(-1)
        sys.exit(0)

n = len(s)
nex = [[n] * 26 for _ in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(26):
        nex[i][j] = nex[i+1][j]
    nex[i][ord(s[i])-ord("a")] = i

ans = 0
pos = 0
for i in range(len(t)):
    v = ord(t[i]) - ord("a")
    ne = nex[pos][v]
    ans += ne - pos + 1
    if ne == n:
        ne = nex[0][v]
        ans += ne
    pos = ne + 1
print(ans)

Solution (Python):

import sys, bisect
sys.setrecursionlimit(300000)


def solve(s: str, t: str):
    N = 26
    pos = [[] for _ in range(N)]
    for i, c in enumerate(s):
        pos[ord(c) - ord('a')].append(i)

    tmp = 0
    num = 0
    for C in t:
        c = ord(C) - ord('a')
        le = len(pos[c])
        if le < 1:
            print(-1)
            return
        idx = bisect.bisect_left(pos[c], tmp)
        
        if idx < le:
            tmp = pos[c][idx] + 1
        else:
            idx = bisect.bisect_left(pos[c], 0)
            tmp = pos[c][idx] + 1
            num += 1
        
    ret = num * len(s) + tmp
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  
    t = next(tokens)  
    solve(s, t)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from bisect import bisect_right
s = input()
t = input()
n = len(s)
m = len(t)


aa = set(s)
for i in t:
    if i not in aa:
        print(-1)
        exit()

d = defaultdict(list)

for i in range(n):
    d[s[i]].append(i)

pos = -1
cnt = 0
for c in t:
    j = bisect_right(d[c], pos)
    if j < len(d[c]):
        pos = d[c][j]
    else:
        cnt += 1
        pos = d[c][0]
print(cnt*n + pos+1)

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

s = list(input())
t = list(input())

L = len(s)
M = len(t)

ss = s * 2

ind_dict = defaultdict(list)
for i in range(2 * L):
    ind_dict[ss[i]].append(i)


def query_str(c, ind):
    if len(ind_dict[c]) == 0:
        return -1
    else:
        r = bisect_right(ind_dict[c], ind)
        return ind_dict[c][r]


res_total = 0
res = -1
for i in range(M):
    res = query_str(t[i], res)
    if res == -1:
        res_total = 0
        break
    if res >= L:
        res -= L
        res_total += L

if res == -1:
    print(-1)
else:
    print(res_total + res + 1)

Solution (Python):
from string import ascii_lowercase
from bisect import bisect_right
s = input()
t = input()
p = {c: [] for c in s}
for x, c in enumerate(s):
    p[c].append(x)
z = 0
l = -1
for c in t:
    if c not in p:
        print(-1)
        break
    x = bisect_right(p[c], l)
    if x == len(p[c]):
        x = 0
        z += 1
    l = p[c][x]
else:
    print(z * len(s) + l + 1)

Solution (Python):
import collections
from bisect import bisect_right
d=collections.defaultdict(list)
s=input()
t=input()
for i,S in enumerate(s,1):
    d[S].append(i)
k=0
ans=0
for i in t:
    l=d[i]
    if len(l)==0:
        print(-1)
        quit()
    if l[-1]<=ans:
        ans=l[0]
        k+=1
    else:
        ans=l[bisect_right(l,ans)]
print(len(s)*k+ans)