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()
l_s = len(s)
l_t = len(t)

s2 = s + s
l_s2 = len(s2)

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

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

cur_idx = 0
for i in range(l_t):
    if i == 0:
        flg = False
        for j in range(l_s):
            if t[i] == s[j]:
                cur_idx += j
                flg = True
                break
        if flg:
            continue
        else:
            print("-1")
            exit()

    else:
        idx = next_idx[cur_idx%l_s][ord(t[i]) - ord("a")]

    if idx == l_s2:
        print("-1")
        exit()

    cur_idx += idx - (cur_idx % l_s)
    
print(cur_idx+1)

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

s2 = s + s
l_s2 = len(s2)

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

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

next_idx_2 = [[l_s2] * 26 for i in range(l_s2)]

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

cur_idx = 0
for i in range(l_t):
    if i == 0:
        idx = next_idx_1[cur_idx%l_s][ord(t[i]) - ord("a")]

    else:
        idx = next_idx_2[cur_idx%l_s][ord(t[i]) - ord("a")]

    if idx == l_s2:
        print("-1")
        exit()

    cur_idx += idx - (cur_idx % l_s)
    
print(cur_idx+1)

Solution (Python):
s=list(input())
t=list(input())
ns=len(s)
nt=len(t)
t_set=list(set(t))
s_set=list(set(s))
for i in range(len(t_set)):
    if t_set[i] not in s_set:
        print(-1)
        exit()

from collections import defaultdict, deque
from bisect import bisect_right
ds=defaultdict(list)
for i in range(ns):
    ds[s[i]].append(i)

components=[0]*26
for i in range(26):
    components[i]=len(ds[chr(i+97)])
lt=[-1]*nt
ord('a')
last=-1
for i in range(nt):
    j=bisect_right(ds[t[i]],last)
    if j==components[ord(t[i])-97]:
        lt[i]=ds[t[i]][0]
    else:
        lt[i]=ds[t[i]][j]
    last=lt[i]

kuriage=0
for i in range(1,nt):
    if lt[i]<=lt[i-1]:
        kuriage+=1

print(kuriage*ns+lt[-1]+1)

Solution (Python):
import sys
from bisect import bisect_right

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


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

    SS = S + S

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

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

    B = [[] for _ in range(26)]
    for i, c in enumerate(SS):
        B[ord(c) - 97].append(i)

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import bisect
import sys
s = input()
t = input()
sb = Counter(s)
tb = Counter(t)
S = len(s)
T = len(t)

for i in range(26):
    x = chr(i+97)
    
    if sb[x] == 0 and tb[x] >= 1:
        print(-1)
        sys.exit()
        
le = [[] for i in range(26)]
for i in range(S):
    le[ord(s[i]) - 97].append(i+1)
        
loop = 0
hasu = 0

for i in range(T):
    x = ord(t[i]) - 97
    c = bisect.bisect(le[x],hasu)
    if c == len(le[x]):
        loop += 1
        hasu = le[x][0]
    else:
        hasu = le[x][c]
        
print(loop*S + hasu)

Solution (Python):
import sys

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


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

    SS = S + S

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

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

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

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

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

    print(ans + 1)
    return


if __name__ == '__main__':
    main()

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

s = rs()
t = rs()


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

import bisect

def search(arr, x):
	l, r = 0, len(arr)
	while r-l >= 1:
		mid = (r+l)//2
		if x < arr[mid]:
			r = mid
		else:
			l = mid+1
	return l

num = 0
cur = -1

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

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

s = rs()
t = rs()


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

import bisect

num = 0
cur = -1

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

Solution (Python):

import sys


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


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)  
    print(solve(s, t))

     
def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Solution (Python):
import bisect

en2asc = lambda s: ord(s) - 97

S = input()
T = input()
if not set(S) >= set(T):
    print(-1)
    exit()

lst = [[] for _ in range(26)]
for i, s in enumerate(S):
    lst[en2asc(s)].append(i)

L = len(S)
cur = 0
for t in T:
    t = en2asc(t)
    b = bisect.bisect_left(lst[t], cur % L)
    if b == len(lst[t]):
        cur = (cur // L + 1) * L
        b = bisect.bisect_left(lst[t], cur % L)
    cur = cur // L * L + lst[t][b] + 1
print(cur)

Solution (Python):

import bisect
from collections import Counter, deque, OrderedDict, defaultdict














import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    s=input()

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

    

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




    
resolve()

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

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

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

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

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

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

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

Solution (Python):
import bisect
from collections import defaultdict
s = input()
n = len(s)
t = input()
if set(s) & set(t) != set(t):
    print(-1)
else:
    cnt = defaultdict(list)
    for i in range(n):
        cnt[s[i]].append(i+1)
    loop = 0
    prev = 0
    for c in t:
        x = cnt[c]
        idx = bisect.bisect_right(x, prev)
        if idx < len(x):
            prev = x[idx]
        else:
            prev = x[0]
            loop += 1
    print(loop*n+prev)

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

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

print(cou*sn + now + 1)

Solution (Python):
from collections import Counter
import bisect


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

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

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

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

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

print(ans * N + now)

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

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

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

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






def rand_letter(size):
    ascii_original='programing'
    digits_original='01'

    digits='0123456789'
    ascii_lowercase='abcdefghijklmnopqrstuvwxyz'
    ascii_uppercase='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    
    psuedo = ascii_original

    return ''.join([random.choice(psuedo) for i in range(size)])


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

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

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

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

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

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

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

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

Solution (Python):
def f():
    import sys
    input=sys.stdin.buffer.readline
    sys.setrecursionlimit(10**9)
    from collections import defaultdict
    table=defaultdict(list)
    
    s,t=input().rstrip(),input().rstrip()
    n=len(s)
    for j in range(n):
        table[s[j]-97].append(j)
    now=0
    ind=0
    if set(t)-set(s):print(-1);exit()
    from bisect import bisect_left as bl
    for p in t:
        if ind>table[p-97][-1]:now+=1;ind=0
        ind=table[p-97][bl(table[p-97],ind)]+1

    print(now*n+ind)
if __name__ == "__main__":
    f()

Solution (Python):
def f():
    s,t=input(),input()
    n,m=len(s),len(t)
    table=[[]for i in  range(26)]
    d={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

    for j in range(n):
        table[d[s[j]]].append(j)
    now=0
    ind=0
    if set(list(t))-set(list(s)):print(-1);exit()
    from bisect import bisect_left as bl
    for p in t:
        if ind>table[d[p]][-1]:now+=1;ind=0
        ind=table[d[p]][bl(table[d[p]],ind)]+1

    print(now*n+ind)
if __name__ == "__main__":
    f()

Solution (Python):
import sys
import math
from collections import deque
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    S = SI()
    T = SI()
    if set(S) | set(T) != set(S):
        print(-1)
        exit()
    s2i = {}

    for i, s in enumerate(S):
        if s in s2i:
            s2i[s].append(i)
        else:
            s2i[s] = [i]

    now = 0
    digit = -1
    for t in T:
        target = bisect.bisect_right(s2i[t], digit)
        if target == len(s2i[t]):
            digit = s2i[t][0]
            now += 1
        else:
            digit = s2i[t][target]

    print(now * len(S) + digit + 1)


if __name__ == "__main__":
    main()

Solution (Python):



from collections import defaultdict
import bisect

def main():
  s = input().strip()
  t = input().strip()
  ns = len(s)
  
  if len(set(list(t)) - set(list(s))):
    print(-1)
    return
  
  ichs = defaultdict(list)  
  for i, c in enumerate(s):
    ichs[c].append(i)
    
  ic = -1
  cnt = 0
  for c in t:
    ix = bisect.bisect_right(ichs[c], ic)
    
    if ix >= len(ichs[c]):
      cnt += 1
      ix = 0
    else:
      if ic == ichs[c][ix]:
        if ix + 1 >= len(ichs[c]):
          cnt += 1
          ix = 0
        else:
          ix += 1
    ic = ichs[c][ix]
  print(cnt*ns + ic + 1)
    
      
    
  

if __name__=='__main__':
  main()

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

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

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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

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

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


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

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

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





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


if __name__ == '__main__':
    main()

Solution (Python):
def atoNum(s):
    return ord(s)-97
where = [[]for i in range(0,26,1)]
from bisect import bisect_right

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

for i in range(0,len(s),1):
    where[atoNum(s[i])].append(i)
ans = 0
cersol = -1

for i in range(0,len(t),1):
    if len(where[atoNum(t[i])])==0:
        print(-1)
        exit()
    tmpCersol = bisect_right(where[atoNum(t[i])],cersol)
    if tmpCersol < len(where[atoNum(t[i])]):
        cersol = where[atoNum(t[i])][tmpCersol]
    else:
        ans += len(s)
        cersol = where[atoNum(t[i])][0]
ans += cersol
print(ans+1)

Solution (Python):
from collections import Counter
import bisect

s = input()
t = input()
"""
TLE問題なのは間違いないが、工夫も結構厳しい必要がありそう
二分探索を用いれば, O(|t| log|s|)の定数倍で解ける？
"""


sc = Counter(s)
tc = Counter(t)
for i, j in tc.most_common():
	if sc[i] == 0:
		print(-1)
		exit()

"""
O(|t| |s|)で解けるが、TLE確実.
bisectを使う。
"""

target = ord("a")
ordl = [[] for _ in range(26)]
for i, j in enumerate(s):
	ordl[ord(j)-target].append(i)
ordllen = [len(ordl[i]) for i in range(26)]



times = 0
cnt = -1
ans = 0
for i in t:
	k = ord(i)-target
	m = bisect.bisect_right(ordl[k], cnt)
	if m == ordllen[k]:
		times += 1
		cnt = ordl[k][0]
	else:
		cnt = ordl[k][m]

ans = times * len(s) + cnt + 1
print(ans)

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

s = input()
t = input()

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

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

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

print(ans)

Solution (Python):

import sys
import bisect

s = input()
t = input()

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

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

numbered_t = [0]*len(t)
for i in range(len(t)):
    numbered_t[i] = (ord(t[i])-97)


all_necessary_alphabets = set()
for i in range(len(t)):
    all_necessary_alphabets.add(numbered_t[i])

for necessary_alphabet in all_necessary_alphabets:
    if len(existing_alphabets[necessary_alphabet])==0:
        print(-1)
        sys.exit()


now = -1
cycled = 0
for i in range(len(numbered_t)):
    existing_alphabet = existing_alphabets[numbered_t[i]]
    can_insert = bisect.bisect_right(existing_alphabet,now)
    if can_insert == len(existing_alphabet):
        can_insert = 0
        cycled += 1
    now = existing_alphabet[can_insert]

ans = len(s) * cycled + now + 1
print(ans)

Solution (Python):
from collections import Counter,defaultdict
import bisect

s = input()
t = input()
ss = s*2

S = Counter(s)
T = Counter(t)

for i in T.keys():
    if i not in S:
        print(-1)
        exit()

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

for i,j in enumerate(ss):
    alpha[ord(j)-ord("a")].append(i)

rep,now = 0,-1

for i in t:
    alp = alpha[ord(i) - ord('a')]
    i = bisect.bisect_left(alp,now+1)
    now = alp[i]
    if now >= len(s):
        now -= len(s)
        rep += 1

print(rep*len(s)+now+1)

Solution (Python):
def solve():
  s = input()
  t = input()
  ans = 0
  alp = [[] for _ in range(27)]
  length_s = len(s)
  for i in range(length_s):
    char = ord(s[i]) - ord('a')
    alp[char].append(i + 1)
  length_t = len(t)
  import bisect
  for i in range(length_t):
    char = ord(t[i]) - ord('a')
    if alp[char]:
      if ans % length_s >= alp[char][-1]:
        ans = (ans // length_s + 1) * length_s
      index = bisect.bisect_right(alp[char], ans % length_s)
      ans += alp[char][index] - ans % length_s
    else:
      return -1
  return ans
print(solve())

Solution (Python):
from bisect import bisect_right
s = tuple(map(lambda c: ord(c) - ord("a"), input()))
t = tuple(map(lambda c: ord(c) - ord("a"), input()))
S, T = set(s), set(t)
if T & S != T:
    print(-1)
    quit()
d, l = [[] for _ in range(26)], [0] * 26
for idx, c in enumerate(s):
    d[c].append(idx)
    l[c] += 1
prev = -1
loop = 0
for c in t:
    idx = bisect_right(d[c], prev)
    if idx >= l[c]:
        loop += 1
        prev = d[c][0]
    else:
        prev = d[c][idx]
print((loop) * len(s) + prev + 1)

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

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

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) 
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

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

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

    pre = counts[0]
    rep = 1

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

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

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

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

        
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        

    
    rep -= 1
    ans = rep * len_of_S  + pre + 1
    print(ans)




if __name__ == "__main__":
  main()

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

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

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

    return idx_list[ret_idx]

if __name__ == '__main__':
    solve()

Solution (Python):
from bisect import bisect_left
from string import ascii_lowercase


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

    set_s = set(tuple(s))
    set_t = set(tuple(t))

    if not(set_t <= set_s):
        print(-1)
        exit()

    ans = 0
    d = {c:[] for c in ascii_lowercase}
    
    for i, c in enumerate(s):
        d[c].append(i+1)
    
    now = 0
    for c in t:
        
        idx = bisect_left(d[c], now+1)

        if idx == len(d[c]):
            ans += len(s)
            now = 0
            idx = bisect_left(d[c], now+1)
            
        now = d[c][idx]

    ans += now
    print(ans)

        
if __name__ == "__main__":
    main()

Solution (Python):
import bisect


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



if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
import bisect
s, t = [x.strip() for x in open(0).readlines()]
if set(t) - set(s) != set():
    print(-1)
else:
    d = defaultdict(list)
    n = len(s)
    for i, c in enumerate(s, 1):
        d[c].append(i)
    for k in d:
        d[k].append(d[k][0] + n)
    ans = 0
    for c in t:
        q, r = divmod(ans, n)
        x = d[c][bisect.bisect(d[c], r)]
        ans = n*q + x
    print(ans)

Solution (Python):
import collections

s = input()
t = input()
s_len = len(s)
s_idx = dict([])
for i, key in enumerate(s):
    try:
        s_idx[key].append(i + 1)
    except KeyError:
        s_idx[key] = [i + 1]

def binary_search(li, tmp, ng, ok):
    mid = (ng + ok) // 2
    if ok - ng < 2:
        if ok == len(li):
            return s_len + li[0]
        else:
            return li[ok]
    if li[mid] <= tmp: return binary_search(li, tmp, mid, ok)
    else: return binary_search(li, tmp, ng, mid)

ans = 0
ex_i = 0
for key in t:
    try:
        i = binary_search(s_idx[key], ex_i, -1, len(s_idx[key]))
        ans += i - ex_i
        ex_i = i % s_len
    except KeyError:
        ans = -1
        break
print(ans)

Solution (Python):
import collections

s = input()
t = input()
mod = len(s)
s_idx = dict([])
for i, key in enumerate(s):
    try:
        s_idx[key].append(i + 1)
    except KeyError:
        s_idx[key] = [i + 1]

def binary_search(li, tmp, ng, ok):
    mid = (ng + ok) // 2
    if ok - ng < 2:
        if ok == len(li):
            return mod + li[0]
        else:
            return li[ok]
    if li[mid] <= tmp: return binary_search(li, tmp, mid, ok)
    else: return binary_search(li, tmp, ng, mid)

ans = 0
tmp = 0
for key in t:
    try:
        i = binary_search(s_idx[key], tmp, -1, len(s_idx[key]))
        ans += i - tmp
        tmp = i % mod
    except KeyError:
        ans = -1
        break
print(ans)

Solution (Python):
S = list(str(input()))
T = list(str(input()))

S_ = set(list(S))
T_ = set(list(T))
for c in T:
    if c not in S_:
        print(-1)
        exit()

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


q = 0
pre = -1
import bisect
for t in T:
    j = ord(t)-ord('a')
    idx = bisect.bisect_right(d[j], pre)
    if idx == len(d[j]):
        q += 1
        pre = d[j][0]
    else:
        pre = d[j][idx]
print(q*len(S)+pre+1)

Solution (Python):
S = list(str(input()))
T = list(str(input()))

S_ = set(list(S))
T_ = set(list(T))
for c in T:
    if c not in S_:
        print(-1)
        exit()

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


q = 0
pre = -1
import bisect
for t in T:
    j = ord(t)-ord('a')
    idx = bisect.bisect_right(d[j], pre)
    if idx == len(d[j]):
        q += 1
        pre = d[j][0]
    else:
        pre = d[j][idx]
print(q*len(S)+pre+1)

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

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

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

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

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


for i,c in enumerate(s): alpha[f(c)].append(i)

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