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











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
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()

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

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

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

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

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

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



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)

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



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)

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



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)

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

Solution (Python):

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]

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
  
else:
  print(ans)

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

Solution (Python):


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)

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



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)

Solution (Python):

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]
        


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)

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

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

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

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

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

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

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

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

Solution (Python):
import copy


def main():
    s = input()
    ss = s + s
    t = input()
    if not set(sorted(t)) <= set(sorted(s)):
        print(-1)
        return
    cnt_s = {}
    cnt_t = {}
    pos = {}  
    for i in range(len(ss)):
        c = ss[i]
        if c not in cnt_s:
            cnt_s[c] = 0
            pos[c] = []
        cnt_s[c] += 1
        pos[c].append(i)
    
    
    
    ret = 0
    tmp = -1
    for i in range(len(t)):
        c = t[i]
        if pos[c][0] > tmp:
            tmp = pos[c][0]
            continue
        l = 1
        r = len(pos[c]) - 1
        while not l == r:
            p = (l + r) // 2
            if pos[c][p] > tmp:
                r = p
            if pos[c][p] <= tmp:
                l = p + 1
        tmp = pos[c][l]
        if tmp >= len(s):
            ret += len(s)
            tmp -= len(s)
    ret += tmp + 1
    print(ret)
    return


if __name__ == "__main__":
    main()

Solution (Python):
def solve(S, T):
    from bisect import bisect_right, bisect_left
    N = len(S)
    a = ord('a')
    S_ = S
    S = [ord(c)-a for c in S]
    T_ = T
    T = [ord(c)-a for c in T]
    index = [[] for i in range((ord('z')-ord('a')+1))]
    for i, c in enumerate(S):
        index[c].append(i)

    for t in T:
        if len(index[t]) == 0:
            return -1

    prev = T[0]
    prevIndex = index[prev][0]
    find = bisect_left
    offset = 0
    for i in range(1, len(T)):
        t = T[i]
        indexT = index[t]
        found = find(indexT, prevIndex+1)
        
        if found== len(indexT):
            prevIndex = indexT[0]
            offset += 1
        else:
            prevIndex = indexT[found]
        

    
    return offset*N+prevIndex+1

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

print(solve(S, T))

Solution (Python):
import sys

def solve():
    s = input()
    t = input()
    alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"\
        , "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
    convert = dict()
    for i in range(26):
        convert[alphabet[i]] = i

    behind = [{i:-1 for i in range(26)} for _ in range(len(s) + 1)]
    canuse = set()
    for i in reversed(range(len(s))):
        for j in range(26): behind[i][j] = behind[i+1][j]
        behind[i][convert[s[i]]] = i
        canuse |= {s[i]}
    
    k = 0
    counter = 0
    for i in range(len(t)):
        if t[i] not in canuse:
            print(-1)
            break
        else:
            if behind[counter][convert[t[i]]] > -1:
                counter = behind[counter][convert[t[i]]] + 1
            else:
                k += 1
                counter = behind[0][convert[t[i]]] + 1
    else: print(k * len(s) + counter)
    

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
def counter(list_1,list_2,length):
    count = 0
    m = 0
    for n in list_1:
        if m == length:
            count += 1
            m = 0
        m = list_2[n][m]
        if m == -1 :
            count += 1
            m = list_2[n][0]
    return count * length + m
s = input()
le_s = len(s)
t = input()
l_t = [ord(x)-97 for x in t]
s_t = set(l_t)
l_s = [[-1 for p in range(le_s)] for _ in range(26)]
s_s =set()
i = 1
l_c = [0 for _ in range(26)]
for y in s:
    z = ord(y)-97
    if z in s_t:
        l_s[z][l_c[z]:i] = [i for a in range(i - l_c[z])]
        l_c[z] = i
        s_s.add(z)
    i += 1
if s_t != s_s:
    print(-1)
    exit()
print(counter(l_t,l_s,le_s))

Solution (Python):
s = input()
l = input()
     
count = 0
ind = -1
if set(l).issubset(set(s)):
    for i in range(len(l)):
        ind = s.find(l[i], ind+1)
        if ind == -1:
            count += 1
            ind = s.find(l[i], ind+1)
    print(count*len(s) + ind+1)
 
else:
    print(-1)

Solution (Python):
import sys
from collections import defaultdict

def bs(arr, val):
	l, h = 0, len(arr)-1
	ans = -1
	while l <= h:
		m = l + h >> 1
		if arr[m] > val:
			ans = m
			h = m - 1
		else:
			l = m + 1
	return ans

s = sys.stdin.readline().strip()
n = len(s)

t = sys.stdin.readline().strip()

occurence = defaultdict(list)
for i in range(n):
	occurence[s[i]].append(i+1)

def solve():
	folds = 0
	cur_ptr = 0

	for ele in t:
		indexes = occurence[ele]
		if not indexes: return -1

		idx = bs(indexes, cur_ptr)
		if idx != -1: 
			cur_ptr = indexes[idx]
		else:
			folds += 1
			cur_ptr = indexes[0]
		
	ans = folds*(n) + cur_ptr
	return ans

print(solve())

Solution (Python):
import bisect

def ctoi(char):
  return ord(char) - 97



ingredients = input()
ingredients_len = len(ingredients)

recipe = input()
recipe_len = len(recipe)

alphabets = [[] for _ in range(26)]


for i in range(ingredients_len):
  alpha_idx = ctoi(ingredients[i])
  alphabets[alpha_idx].append(i)

ingredients_counter = [0] * 26
for i in range(26):
  ingredients_counter[i] = len(alphabets[i])
  
ingredients_idx_list = []
flag = True
ingredients_pointer = -1

for i in range(recipe_len):
  alpha_idx = ctoi(recipe[i])
  if ingredients_counter[alpha_idx] == 0:
    flag = False
    break
  
  pointer_candidate_idx = bisect.bisect_right(alphabets[alpha_idx], ingredients_pointer)
  
  if pointer_candidate_idx == ingredients_counter[alpha_idx]:
    ingredients_pointer = alphabets[alpha_idx][0]
  else:
    ingredients_pointer = alphabets[alpha_idx][pointer_candidate_idx]
  ingredients_idx_list.append(ingredients_pointer)

if flag == False:
  print(-1)
else: 
  loop = 0
  idx = ingredients_idx_list[0]
  
  for i in range(1, recipe_len):
    if ingredients_idx_list[i] <= idx:
      loop += 1
    idx = ingredients_idx_list[i]
  
  print(loop * len(ingredients) + ingredients_idx_list[-1] + 1)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

s = input()
t = input()
n = len(s)
s*=2

i = ans = 0
for c in t:
    d = s[i:].find(c)
    if d == -1:
        print(-1)
        exit()
    ans += d+1
    i += d+1
    if i >= n: i -= n
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

s = input()
n = len(s)
t = input()
s*=2

ans = 0
for c in t:
    d = s[ans%n:].find(c)
    if d == -1:
        print(-1)
        exit()
    ans += d+1
print(ans)

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

s = input().rstrip()
t = input().rstrip()
d = defaultdict(list)

for i,c in enumerate(s):
    d[c].append(i)
ans = 0
ind = -1
for c in t:
    
    if not d[c]:
        ans = -1
        break
    ins = bisect.bisect_left(d[c],ind+1)
    if ins < len(d[c]):
        ind =d[c][ins]
     
    else:
      
        ans += len(s)
        ind = d[c][0]
    
    
else:
    ans += ind+1

print(ans)

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

count = 0
ind = -1
if set(t) <= set(s):
    for i in range(len(t)):
        ind = s.find(t[i], ind+1)
        if ind == -1:
            count += 1
            ind = s.find(t[i], ind+1)
    print(count*len(s) + ind+1)

else:
    print(-1)

Solution (Python):
import sys
import bisect

ss = input()
t = input()
n = len(ss)
cnt = {}
s = ss*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

idx = 0
ten = 0

for z in t:
    if z not in ss:
        print(-1)
        sys.exit()

    idx = cnt[z][bisect.bisect_left(cnt[z], idx)] + 1

    if idx>=n:
        idx -= n
        ten += 1

    

suffix = idx + ten * n

print(suffix)

Solution (Python):
import bisect

ss = input()
tt = input()

def main(ss, t):
	d = {}
	s_uq = set(ss)
	for t in set(tt):
		if t not in s_uq:
			print(-1)
			return
		d[t] = []

	
	for i, s in enumerate(ss):
		if s in d.keys():
			d[s].append(i)

	max_d = {key:max(val) for (key, val) in d.items()}
	
	loop_cnt = 0
	idx = -1
	for t in tt:
		if idx >= max_d[t]:
			loop_cnt += 1
			idx = -1
		idx = d[t][bisect.bisect_right(d[t], idx)]

	print(loop_cnt * len(ss) + idx + 1)
		
main(ss, tt)

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

temp = s[:]
count = 0
ans = 0

for i in range(len(t)):
    a = s.find(t[i])
    if a == -1:
        print(-1)
        exit()

while count < t_length:
    value = temp.find(t[count])
    if value == -1:
        ans += len(temp)
        temp = s[:]
    
    else:
        ans += value + 1
        count += 1
        temp = temp[value + 1:]

print(ans)

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

x = len(s)
y = len(t)

a = 0
b = x
c = 0
a0 = 0


for i in range(0,y):
  while True:
    
    a=s.find(t[i:i+1],a0)+1
    if a <= 0:
      a=s.find(t[i:i+1])+1
    if a <= 0:
      print("-1")
      exit()
    
    if a<=a0:
      c=c+a+b
    else:
      c=c+a-a0
    b=x-a
    a0=a
    break
    
print(c)

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

alphabet = set(s)
if any(c not in alphabet for c in t):
    print(-1)
    exit()

N = len(s)


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



next = [None for i in range(N)]
next[N - 1] = {c: N + leftmost[c] for c in alphabet}
for i in range(N - 2, -1, -1):
    next[i] = {c: i + 1 if s[i + 1] == c else next[i + 1][c]
                  for c in alphabet}

pos = leftmost[t[0]]
for c in t[1:]:
    pos = pos - (pos % N) + next[pos % N][c]

print(pos + 1)

Solution (Python):
import bisect
s = input()
t = input()
before = -1
len_s = len(s)
ans = 0
cnt = 0
moji = [[] for _ in range(26)]
for i,S in enumerate(s):
        moji[ord(S) - 97].append(i)

for T in t:
        if not moji[ord(T) - 97]:
                print(-1)
                exit()
        if moji[ord(T) - 97][-1] <= before:
                cnt += 1
                before = moji[ord(T) - 97][0]
                continue
        before = moji[ord(T) - 97][bisect.bisect_right(moji[ord(T) - 97],before)]
        
        
        
        
ans = cnt * len_s + before + 1
print(ans)

Solution (Python):
s = input()
t = input()
if not set(t) <= set(s):
  print(-1)
else:
  a = 0
  seq = s
  for k in t: 
    p = seq.find(k) + 1
    if p == 0:
      p = s.find(k) + 1
      a += len(seq)
      seq = s
    a += p
    seq = seq[p:]
  print(a)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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)

Solution (Python):
s = input()
t = input()
moji = list(set(s))
if all([k in moji for k in set(t)]) is not True:
  print(-1)
else:
  a = 0
  l = len(s)
  seq = s
  for k in t: 
    p = seq.find(k) + 1
    if p == 0:
      p = s.find(k) + 1
      a += p + len(seq)
      seq = s
    else:
      a += p
    seq = seq[p:]
  print(a)

Solution (Python):
from bisect import bisect_right

s = input()
t = input()

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

for i in range(2*len(s)):
        if i<len(s):
                char_list[ord(s[i])-97].append(i)
        else:
                char_list[ord(s[i-len(s)])-97].append(i)

INF = 10**27

for i in range(26):
        char_list[i].append(INF)

next_list = [[char_list[j][bisect_right(char_list[j],i)] for j in range(26)] for i in range(len(s))]

flag = False
for i in range(len(s)):
        if t[0]==s[i]:
                flag=True
                x = i
                y = i
                break
if flag:
        flag2 = True
        for i in range(1,len(t)):
                n = next_list[x][ord(t[i])-97]
                y += n - x
                x = n%(len(s))
                if y >= INF:
                        flag2=False
                        break
        if flag2:
                print(y+1)
        else:
                print(-1)
else:
        print(-1)

Solution (Python):
import sys
import bisect


input = sys.stdin.readline

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

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

sn = len(S)
d = dict()
for i, s in enumerate(S):
    d[s] = d.get(s, [])
    d[s].append(i)

nowidx = -1
loop = 0
for t in T:
    l = d.get(t, [])
    if len(l) == 0:
        print(-1)
        sys.exit()
    j = bisect.bisect_right(l, nowidx)
    if len(l) <= j:
        nowidx = l[0]
        loop += 1
    else:
        nowidx = l[j]


print(loop * sn + nowidx + 1)

Solution (Python):
import sys
input=sys.stdin.readline
import string
import bisect

def main():

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

    dS = {c:[] for c in string.ascii_lowercase}
    for i, s in enumerate(S):
        dS[s].append(i)
    
    ans = 0
    pos = 0
    ls = len(S)
    for c in T:
        if not dS[c]:
            print(-1)
            return
        if dS[c][-1] < pos:
            pos = 0
            ans += ls
        bi = bisect.bisect_left(dS[c], pos)
        pos = dS[c][bi] + 1

    print(ans + pos)

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect
S = input()
T = input()
LS = len(S)
LT = len(T)

H = {chr(i): [] for i in range(ord('a'), ord('z')+1)}
for i, s in enumerate(S):
    H[s].append(i)

dp = [0] * (LT+1)
dp[0] = -1
valid = True

for i in range(1,LT+1):
    t = T[i-1]
    p = dp[i-1] % LS if i > 1 else -1
    if len(H[t]) == 0:
        valid = False
        break
    q = bisect(H[t], p)
    if q == len(H[t]):
        dp[i] = dp[i-1] + LS - p + H[t][0]
    else:
        dp[i] = dp[i-1] + H[t][q] - p

print(dp[-1] + 1 if valid else -1)

Solution (Python):
import sys
input=sys.stdin.readline
import string
import bisect

def main():

    S = input().strip()
    T = input().strip()
    if any(S.find(c) < 0 for c in T):
        print(-1)
        return

    dS = {c:[] for c in string.ascii_lowercase}
    for i, s in enumerate(S):
        dS[s].append(i)
    
    ans = 0
    pos = 0
    ls = len(S)
    for c in T:
        if dS[c][-1] < pos:
            pos = 0
            ans += ls
        bi = bisect.bisect_left(dS[c], pos)
        pos = dS[c][bi] + 1

    print(ans + pos)

if __name__ == '__main__':
    main()

Solution (Python):
def lower_bound(a, x, index=False):
    from bisect import bisect_left
    i = bisect_left(a, x)
    if (i != len(a)):
        if (index):
            return i
        else:
            return a[i]
    raise ValueError

import sys
import string
s = input()
t = input()
s2 = s*2
lc = string.ascii_lowercase
cd = {}
for c in lc:
    cd[c] = []
for i in range(len(s2)):
    cd[s2[i]].append(i)
p = 0
ans = 0
for c in t:
    if (len(cd[c]) == 0):
        print('-1')
        sys.exit()
    p = lower_bound(cd[c],p)+1
    if (p >= len(s)):
        p -= len(s)
        ans += len(s)
ans += p
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
import string
import bisect

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

    if not all(s.find(c) >= 0 for c in t):
        print(-1)
        exit()
    
    sa = [[] for _ in string.ascii_lowercase]
    ai = ord('a')
    for i,c in enumerate(s):
        sa[ord(c)-ai].append(i+1)


    ls = len(s)
    ans = 1 
    i = 1 
    for c in t:
        a = sa[ord(c)-ai]
        if len(a) == 0 or i > a[-1]:
            ans += ls-i+1
            i = 1
        bi = bisect.bisect_left(a,i)
        if bi < len(a):
            ans += a[bi]-i+1
            i = a[bi]+1

    print(ans-1)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from bisect import bisect_right

alp = [[] for _ in range(26)]

s = input()
t = input()



for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = [0 for _ in range(26)]
        loop += 1

    ind = bisect_right(letter, ind_prev)
    ind_prev = letter[ind]

if flag:
    print(loop * len(s) + ind_prev + 1)

Solution (Python):
import collections
import bisect

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

print(len(s)*k+ans)

Solution (Python):
from collections import deque
import bisect

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

pos_S = {}
for i, s in enumerate(S):
  if s in pos_S:
    pos_S[s].append(i)
  else:
    pos_S[s] = deque([i])
x = 0
start = 0
for t in T:
  if t in pos_S:
    poss = pos_S[t]
    pos = bisect.bisect_left(poss, start)
    if pos >= len(poss):
      x += 1
      start = poss[0]+1
    else:
      start = poss[pos]+1
  else:
    x = -1
    break
if x == -1:
  print(-1)
else:
  print(x*len(S)+start)