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
from bisect import bisect_right
s = input()
t = input()
n = len(t)
index = [[] for i in range(26)]
for i in range(len(s)):
    j = ord(s[i])-97
    index[j].append(i)
tmp = -1
ans = 0
for i in range(n):
    j = ord(t[i])-97
    if len(index[j])==0:
        print(-1)
        sys.exit()
    k = bisect_right(index[j], tmp)
    if k<len(index[j]):
        tmp = index[j][k]
    else:
        ans+=1
        tmp = index[j][0]
print(ans*len(s)+tmp+1)

Solution (Python):
from bisect import bisect_left

S = input()
T = input()

memo = {}
for i, s in enumerate(S):
    if s not in memo:
        memo[s] = [i]
    else:
        memo[s].append(i)

cnt = 0
pre = -1
for t in T:
    if t not in memo:
        print(-1)
        quit()
    m = bisect_left(memo[t], pre + 1)
    if m >= len(memo[t]):
        cnt += 1
        pre = memo[t][0]
    else:
        pre = memo[t][m]

print(cnt * len(S) + pre + 1)

Solution (Python):
from bisect import bisect_left,bisect
s=input()
t=input()
n=len(s)
m=len(t)
ord_a=ord("a")
s_=[[] for i in range(26)]
for i in range(n):
  s_[ord(s[i])-ord_a].append(i)
k=ord(t[0])-ord_a  
if (not s_[k]):
    print(-1)
    exit()
ans=s_[k][0]
rep=0
for i in range(1,m):
  k=ord(t[i])-ord_a
  
  if (not s_[k]):
    print(-1)
    exit()
  if s_[k][-1]<=ans%n:
    rep+=1
    ans=rep*n+s_[k][0]
  else:
    pos=bisect(s_[k],ans%n)
    
    ans+=s_[k][pos]-ans%n
  
print(ans+1)

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

indexes = [[] for _ in range(26)]
for i, s in enumerate(S):
    indexes[s].append(i)
m = [[-1] * 26 for _ in range(ls)]
for s in range(26):
    inds = indexes[s]
    if not len(inds):
        continue
    for r in range(1, len(inds)):
        for i in range(inds[r-1], inds[r]):
            m[i][s] = inds[r] - i
    l = inds[-1]
    r = inds[0]
    i = l
    while True:
        m[i][s] = (r - i - 1) % ls + 1
        if i == (r - 1) % ls:
            break
        i = (i + 1) % ls

ans = 0
i = ls - 1
for t in T:
    cnt = m[i][t]
    if cnt == -1:
        print(-1)
        exit()
    ans += cnt
    i = (i + cnt) % ls
print(ans)

Solution (Python):
import bisect

S = input()
T = input()

idx = {}
for i, s in enumerate(S):
    if s in idx.keys():
        idx[s].append(i + 1)
    else:
        idx[s] = [i + 1]

x = 0
current = 0
impossible = 0
for i, t in enumerate(T):
    if t in idx.keys():
        idx_list = idx[t]
        j = bisect.bisect_right(idx_list, current)
        if j < len(idx_list):
            current = idx_list[j]
        else:
            x += 1
            current = idx_list[0]
    else:
        impossible = 1
        break

if impossible:
    print(-1)
else:
    print(x * len(S) + current)

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

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    return -1

s = list(input())
t = list(input())
if len(set(t)-set(s)) != 0:
    print(-1)
    exit(0)

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

index = -1
round = 0

for tt in t:
    index = find_gt(sdict[tt], index)
    if index == -1:
        index = sdict[tt][0]
        round += 1
ans = round * len(s) + index + 1
print(ans)

Solution (Python):
from collections import defaultdict
from bisect import bisect
s = input()
t = input()
S = defaultdict(list)
for i, c in enumerate(list(s)):
    S[c].append(i + 1)
now = 0
num = 0
for c in t:
    if c not in S:
        print(-1)
        exit()
    P = S[c]
    x = bisect(P, now)
    if x < len(P):
        num += P[x] - now
        now = P[x]
    else:
        num += len(s) - now
        num += P[0]
        now = P[0]
print(num)

Solution (Python):
from bisect import bisect_left
import sys

input = sys.stdin.readline

s = input().strip()
n = len(s)
t = input().strip()

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

string_count = 0
cur = -1
for tt in t:
    cur += 1
    idx = ord(tt) - base
    pos_lst = d[idx]
    lst_len = len(pos_lst)

    if not lst_len:
        print(-1)
        exit()
    pos = bisect_left(pos_lst, cur)  
    if lst_len == pos:
        string_count += 1
        cur = pos_lst[0]
    else:
        cur = pos_lst[pos]

    

print(string_count * n + cur + 1)

Solution (Python):
import bisect
from collections import defaultdict


def in_sort(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


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

    c_idx = defaultdict(list)

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

    idx = -1
    ans = 0
    for c in t:
        if len(c_idx[c]) == 0:
            return -1

        idx_in_c = bisect.bisect_right(c_idx[c], idx)
        
        if idx_in_c == len(c_idx[c]):
            idx -= len(s)
            ans += len(s)
            idx_in_c = bisect.bisect_right(c_idx[c], idx)
        
        idx = c_idx[c][idx_in_c]

    return ans + idx + 1


if __name__ == "__main__":
    print(main())

Solution (Python):
from collections import Counter
S = input()
T = input()
cts = Counter(S)
ctt = Counter(T)
if set(ctt.keys()) - set(cts.keys()):
  print(-1)
  exit()

previdx = {}
L = len(S)
for i, c in enumerate(S):
  if c not in previdx:
    previdx[c] = i

keys = list(previdx.keys())
nxts = [{} for _ in range(L)]
for i in range(L-1, -1, -1):
  nxt = nxts[i]
  for k in keys:
    a = previdx[k] - i
    if a == 0:
      nxt[k] = L
    else:
      nxt[k] = a % L
  previdx[S[i]] = i

ans = previdx[T[0]]
pos = ans
for c in T[1:]:
  d = nxts[pos][c]
  ans += d
  pos = (pos + d) % L
print(ans+1)

Solution (Python):
s=input()
t=input()
s_rm = s
ans=0
for i in t:
    if i in s_rm:
        index = s_rm.index(i)
        s_rm = s_rm[index+1:]
        ans += index+1
    elif i in s:
        index = s.index(i)
        ans += len(s_rm) + index +1
        s_rm = s[index+1:]
    else:
        ans=-1
        break
print(ans)

Solution (Python):
import bisect

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

s=input()
ls=len(s)
t=input()
lt=len(t)
pos=[[] for _ in range(26)]
for i in range(ls):
  val=ctoi(s[i])
  pos[val].append(i)
larr=[0]*26
for i in range(26):
  larr[i]=len(pos[i])
pos2=[]
cnt=[0]*26
flag=True
num=-1
for i in range(lt):
  val=ctoi(t[i])
  if larr[val]==0:
    flag=False
    break
  tmp=bisect.bisect_right(pos[val],num)
  if tmp==larr[val]:
    num=pos[val][0]
  else:
    num=pos[val][tmp]
  pos2.append(num)
if flag==False:
  print(-1)
else:
  loop=0
  tmp=pos2[0]
  for i in range(1,lt):
    if pos2[i]<=tmp:
      loop+=1
    tmp=pos2[i]
  ans=loop*ls+(pos2[-1]+1)
  print(ans)

Solution (Python):
from bisect import bisect_right
s = input()
n = len(s)
t = input()
m = len(t)
tr = set(s)
for c in t:
  if c not in s:
    print(-1)
    exit(0)
d = {c:[] for c in 'abcdefghijklmnopqrstuvwxyz'}
for i, c in enumerate(s):
  d[c].append(i)
idx = -1
ans = 0
for c in t:
  tmp = bisect_right(d[c], idx)
  if tmp == len(d[c]):
    idx = d[c][0]
    ans += 1
  else:
    idx = d[c][tmp]
print(ans * n + idx + 1)

Solution (Python):
import bisect
S,T = input(),input()
lenS = len(S)
alp = [[]for i in range(26)]

for i in range(len(S)):
    alp[ord(S[i])-97].append(i)

if alp[ord(T[0])-97] == []:
    print(-1)
    exit()

l = [alp[ord(T[0])-97][0]]
for c in T[1:]:
    A = alp[ord(c)-97]
    if A == []:
        print(-1)
        exit()
    l.append(A[bisect.bisect_left(A,l[-1]+1)%len(A)])

ans = 0
for i in range(len(l)-1):
    if l[i] >= l[i+1]:
        ans += 1
print(ans*lenS+l[-1]+1)

Solution (Python):
from bisect import bisect_right

s = input()
t = input()

table = {}
for i in range(len(s)):
    if s[i] in table:
        table[s[i]].append(i)
    else:
        table[s[i]] = [i]

dup = 0
prev = -1
for i in range(len(t)):
    if t[i] not in table:
        print(-1)
        exit()

    ind_list = table[t[i]]
    if prev < ind_list[-1]:
        temp = bisect_right(ind_list, prev)
        prev = ind_list[temp]
        continue
    else:
        dup += 1
        prev = ind_list[0]

print(dup * len(s) + prev + 1)

Solution (Python):
from bisect import *
s = input()
t = input()

d = dict()
for i in range(26):
    d[chr(97+i)] = i

s_index = [[] for i in range(26)]
for i in range(len(s)):
    s_index[d[s[i]]].append(i)


flag = 1
ans = 0
index = -1
for ti in t:
    s_char = s_index[d[ti]]
    if len(s_char) == 0:
        flag = 0
        ans = -1
        break
    next = s_char[bisect_left(s_char, index) % len(s_char)]
    if next == index:
        next = s_char[(bisect_left(s_char, index)+1) % len(s_char)]

    if next == index:
        ans += len(s)
    else:
        if index == -1:
            ans += next - index
        else:
            ans += (next - index) % len(s)

    index = next


print(ans)

Solution (Python):
def hersCode(L, n):
  if n >= L[-1]:
    return -1
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] > n:
      ok = mid
    else:
      ng = mid
  return ok


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

R = {}

for i in t:
  if i not in R:
    R[i] = []
    flag = True
    for j in range(len(s)):
      if i == s[j]:
        R[i].append(j)
        flag = False
    if flag:
      print(-1)
      exit()

num = -1
cnt = 0

for i in t:
  t = hersCode(R[i], num)
  if t == -1:
    num = -1
    cnt += 1
    t = hersCode(R[i], num)
  num = R[i][t]
print(cnt * len(s) + num + 1)

Solution (Python):
s=input()
t=input()
import bisect
dist=[[]for i in range(30)]


for j in range(len(s)):
    dist[ord(s[j])-ord("a")].append(j+1)

cnt=0
nw = 1

for i in range(len(t)):
    chrno=ord(t[i])-ord("a")
    if len(dist[chrno]) == 0:
        print(-1)
        exit()

    neIdx = bisect.bisect_left(dist[chrno], nw)
    if neIdx == len(dist[chrno]):
        cnt+=1
        nw = dist[chrno][0]+1
    else:
        nw=dist[chrno][neIdx]+1

print(len(s)*cnt+nw-1)

Solution (Python):
from collections import defaultdict
import bisect

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

dic = defaultdict(list)

for i in range(len(s)):
    dic[s[i]].append(i)

loop = 0
mark = -1
for i in t:
    if len(dic[i]) == 0:
        loop = -1
        break
    ind = bisect.bisect_right(dic[i], mark)
    if ind == len(dic[i]):
        ind = 0
        loop += 1
    mark = dic[i][ind]

if loop == -1 :
    print(-1)
else:
    print(loop * len(s) + mark +1)

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

S = input()
T = input()

s_set = set(list(S))
t_set = set(list(T))

if not t_set <= s_set:
    print(-1)
    exit()


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


now_position = -1
t_position = [-1] * len(T)
for i, t in enumerate(T):
    ti = bisect_right(s_position[t], now_position)
    if ti >= len(s_position[t]):
        ti = 0

    t_position[i] = s_position[t][ti]
    now_position = s_position[t][ti]

ans = 0
for i in range(len(T) - 1):
    if t_position[i] >= t_position[i + 1]:
        ans += len(S)

print(ans + t_position[-1] + 1)

Solution (Python):
from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)

Solution (Python):
from bisect import bisect_left

s = input()
t = input()
ls, lt = len(s), len(t)

exsist = [[] for _ in range(26)]
for i in range(ls) :
    exsist[ord(s[i])-97].append(i)

ret = 0
now = -1
for i in range(lt) :
    ot = ord(t[i])-97
    if len(exsist[ot]) == 0 :
        print('-1')
        break
    
    a = bisect_left(exsist[ot], now + 1)
    if a == len(exsist[ot]) :
        ret += ls
        now = exsist[ot][bisect_left(exsist[ot], -1)]
    else :
        now = exsist[ot][a]
        
else :
    print(ret+now+1)

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

def main():
    idx = defaultdict(list)
    s = input()
    t = input()
    if not set(t) <= set(s):
        print(-1)
        exit()
    for i, c in enumerate(s):
        idx[c] += [i]
    pre = -1
    roop = 0
    for c in t:
        koho = idx[c]
        ki = bisect_left(koho, pre + 1)
        if ki < len(koho):
            pre = koho[ki]
        else:
            pre = koho[0]
            roop += 1
    print(len(s) * roop + pre + 1)

main()

Solution (Python):
s = input()
t = input()
N = len(s)
s2 = s + s
cs = set(t)

table = {}
for c in cs:
  if s.find(c) < 0:
    table[c] = [-1]*N
    continue
  l = [-2] * N
  p = 0
  while p < N:
    i = s2.find(c, p)
    while p <= i:
      if p < N:
        l[p] = i-p
      p += 1
  table[c] = l

r = 0
for c in t:
  d = table[c][r%N]
  if d < 0:
    print(-1)
    exit()
  r += d+1
print(r)

Solution (Python):
import bisect
S=input()
T=input()
N=len(S)
M=len(T)
chardict=dict()
for i in range(26):
    chardict[chr(i+97)]=[]
for i in range(2*N):
    chardict[S[i%N]].append(i)
dp=[0 for i in range(M+1)]
dp[0]=-1
for i in range(M):
    nowpoint=dp[i]%N
    cycle=dp[i]//N
    
    if len(chardict[T[i]])==0:
        print(-1)
        exit()
    tmp=bisect.bisect_right(chardict[T[i]],nowpoint)
    dp[i+1]=cycle*N+chardict[T[i]][tmp]
print(dp[M]+1)

Solution (Python):
import bisect


def solve(s, t):
    indexes = {}
    for i, c in enumerate(s):
        indexes.setdefault(c, []).append(i)
    index = 0
    loop_count = 0
    for c in t:
        if c not in indexes:
            return -1
        else:
            found_i = bisect.bisect_left(indexes[c], index)
            if found_i == len(indexes[c]):
                loop_count += 1
                index = indexes[c][0] + 1
            else:
                index = indexes[c][found_i] + 1
    return index + loop_count * len(s)

if __name__ == "__main__":
    s = input()
    t = input()
    print(solve(s, t))

Solution (Python):
import bisect

s = input()
t = input()

se = set(list(s))
for ti in t:
    if not ti in se:
        print(-1)
        exit()

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

ans = 0
now = 0
for i, ti in enumerate(t):
    j = bisect.bisect_left(word[ord(ti) - ord('a')], now)
    if j < len(word[ord(ti) - ord('a')]):
        j = word[ord(ti) - ord('a')][j]
        ans += j - now + 1
        now = (j + 1) % len(s)
    else:
        ans += len(s) - now
        now = 0
        j = bisect.bisect_left(word[ord(ti) - ord('a')], 0)
        j = word[ord(ti) - ord('a')][j]
        ans += j - now + 1
        now = j + 1


print(ans)

Solution (Python):
import bisect
S=input()
T=input()
N=len(S)
M=len(T)
chardict=dict()
for i in range(26):
    chardict[chr(i+97)]=[]
for i in range(2*N):
    chardict[S[i%N]].append(i)
dp=[0 for i in range(M+1)]
dp[0]=-1
for i in range(M):
    nowpoint=dp[i]%N
    cycle=dp[i]//N
    
    if len(chardict[T[i]])==0:
        print(-1)
        exit()
    tmp=bisect.bisect_right(chardict[T[i]],nowpoint)
    dp[i+1]=cycle*N+chardict[T[i]][tmp]
    
print(dp[M]+1)

Solution (Python):
S = input()
T = input()
N = len(S)
def calc(s):
    ret = [0] * 26
    for ss in s:
        ret[ord(ss)-97] += 1
    return ret

X = calc(S)
Y = calc(T)
ma = 0
for i in range(26):
    ma = max(ma, -(-Y[i]//X[i])-1 if X[i] else (1<<100 if Y[i] else 0))
A = [i for i in range(26) if Y[i]]
if ma == 1<<100:
    print(-1)
else:
    NE = [[-1] * N for _ in range(26)]
    for a in A:
        b = -1
        for i in list(range(N)[::-1])*2:
            if NE[a][i] >= 0:
                break
            if b >= 0:
                NE[a][i] = b
            if ord(S[i]) - 97 == a:
                b = i
    ans = 0
    i = -1
    for t in T:
        ni = NE[ord(t)-97][i]
        ans += ni - i + (N if ni <= i else 0)
        i = ni
    print(ans)

Solution (Python):
from collections import defaultdict
from bisect import bisect_left,bisect_right
S = input()
T = input()

s_map = defaultdict(list)

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

ans = 0
current_index = 0
for t in T:
    if not s_map[t]:
        print(-1)
        exit()

    index = bisect_right(s_map[t],current_index)
    current_index = s_map[t][index]
    
    if current_index > len(S):
        ans += current_index // len(S) * len(S)
        current_index = current_index % len(S)


print(ans + current_index)

Solution (Python):
import sys

ordA = ord('a')

ss = input()
ts = input()

lenS, lenT = len(ss), len(ts)

setS = set(ss)
for t in ts:
    if t not in setS:
        print(-1)
        sys.exit()

poss = [-1] * 26
for i, s in enumerate(ss):
    ch = ord(s)-ordA
    if poss[ch] == -1:
        poss[ch] = i + lenS

nextss = [[0]*(26) for _ in range(lenS)]
for i in reversed(range(lenS)):
    ch = ord(ss[i])-ordA
    poss[ch] = i
    for ch, pos in enumerate(poss):
        nextss[i][ch] = pos-i

i = 0
ans = 1
for t in ts:
    ch = ord(t)-ordA
    d = nextss[i][ch]
    ans += d+1
    i = (i+d+1) % lenS

print(ans-1)

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



from bisect import bisect_left

s = str(input())
t = str(input())

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

i = 0
n = 1
for ch in t:
    temp = d[ch]
    if temp == []:
        print(-1)
        exit()
    place = bisect_left(temp,i)
    if place==len(temp):
        n += 1
        i = temp[0]+1
    else:
        i = temp[place]+1

print((n-1)*len(s)+i)

Solution (Python):
a_code = ord("a")

s = [ord(c) - a_code for c in input().strip()]
t = [ord(c) - a_code for c in input().strip()]

tl = len(t)
sl = len(s)

s_table = [None] * sl
index_table = [None] * 26
for i in range(sl - 1, -1, -1):
	c = s[i]
	index_table[c] = i
	s_table[i] = list(index_table)

ti = 0
si = 0
count = 0
found = False
while ti < tl:
	c = t[ti]
	index = s_table[si][c]
	if index != None:
		ti += 1
		count += index + 1 - si
		si = index + 1
		found = True
		if si >= sl:
			if not found:
				count = -1
				break
			found = False
			si = 0
	else:
		if not found:
			count = -1
			break
		found = False
		count += sl - si
		si = 0
print(count)

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

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

    dic = {}
    for i in range(len_s):
        if s[i] in dic:
            dic[s[i]].append(i)
        else:
            dic[s[i]] = [i]
    
    ok = True
    now = 0
    ans = 0
    for i in range(len(t)):
        if t[i] not in dic:
            ok = False
            break
        else:
            index = bisect.bisect_left(dic[t[i]], now)
            
            if index >= len(dic[t[i]]):
                
                ans += len_s
                now = dic[t[i]][0]+1
            else:
                now = dic[t[i]][index]+1
            
            
            
            
    if ok:
        print(ans+now)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_right

s = input()
N = len(s)
t = input()


d = {chr(i + ord('a')): [] for i in range(26)}

for i, c in enumerate(s):
    d[c].append(i + 1)

acc = 0
b = 0
for c in t:
    if len(d[c]) == 0:
        acc = -1
        break
    q = bisect_right(d[c], b)
    a = d[c][q if q != len(d[c]) else 0]
    if a > b:
        acc, b = acc + a - b, a
    else:
        acc, b = acc + N - b + a, a

print(acc)

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)

index

x = -1 
for t in T:
    arr = index[t]
    if len(arr) == 0:
        x = -2
        break
    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] - y + LS
    x = next_x

answer = x+1
print(answer)

Solution (Python):


from collections import Counter
from itertools import accumulate
def main():
    s = input()
    t = input()
    S = Counter(s)
    T = Counter(t)
    N = len(t)
    M = len(s)
    d = dict()
    for i in range(26):
        d[ chr( ord("a") + i)] = i
    for key in T:
        if S[key] == 0:
            print(-1)
            return
    Al = [[0]*M for _ in range(26)]
    a = ord("a")
    for i in range(M):
        Al[d[s[i]]][i] = 1
    Ac = [[0]*M for _ in range(26)]
    for i in range(26):
        now = -1
        for j in range(M-1,-1,-1):
            Ac[i][j] = now
            if Al[i][j] == 1:
                now = j
    ans = 1
    for i in range(M):
        if t[0] == s[i]:
            now = i
            break
    first = d[s[0]]
    for cnt in range(1,N):
        g = d[t[cnt]]
        if Ac[g][now] == -1:
            ans += 1
            if g == first:
                now = 0
            else:
                now = Ac[g][0]
        else:
            now = Ac[g][now]
    print(M*(ans-1)+now+1)
    
if __name__ == '__main__':
    main()

Solution (Python):

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools

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

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

    abc_123_dic = defaultdict(int)
    for i in range(26):
        aaa = chr(97 + i)
        abc_123_dic[aaa] = i + 1
        abc_123_dic[i + 1] = aaa


    str_dic = [[] for i in range(27)]

    for i in range(len(s)):
        now_ind = abc_123_dic[s[i]]
        str_dic[now_ind].append(i + 1)


    ans_list = [0 for i in range(len(t))]
    pre_ind = 0
    for i in range(len(t)):
        now_str = t[i]
        now_ind = abc_123_dic[now_str]
        insert_ind = bisect.bisect_right(str_dic[now_ind], pre_ind)
        if insert_ind == len(str_dic[now_ind]):
            ans_list[i] = str_dic[now_ind][0]
        else:
            ans_list[i] = str_dic[now_ind][insert_ind]
        pre_ind = ans_list[i]

    pre_ind = 0
    ans = 0
    
    for i in range(len(t)):
        if pre_ind >= ans_list[i]:
           ans += len(s)
        pre_ind = ans_list[i]
        
    ans += ans_list[len(t) - 1]
    print(ans)






if __name__ == '__main__':
    main()

Solution (Python):
import bisect


s = input()
t = input()

memo = {}
alph = "abcdefghijklmnopqrstuvwxyz"

for i, char in enumerate(alph):
    memo[char] = i

li = [[] for i in range(26)]
for i, char in enumerate(s):
    li[memo[char]].append(i)

ans = 0
now_here = -1

i = 0
while i < len(t):
    char = t[i]
    if not li[memo[char]]:
        print(-1)
        exit()
    if now_here < li[memo[char]][0]:
        now_here = li[memo[char]][0]
        i += 1
    elif now_here < li[memo[char]][-1]:
        now_here = li[memo[char]][bisect.bisect_right(li[memo[char]], now_here)]
        i += 1
    else:
        ans += 1
        now_here = -1
print(ans*len(s) + now_here + 1)

Solution (Python):
import unittest
import collections
import bisect


def solve(s, t):
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)
    i = 0
    n = 0
    for c in t:
        if len(d[c]) == 0:
            return - 1
        k = bisect.bisect_left(d[c], i)
        if k == len(d[c]):
            n += 1
            k = bisect.bisect_left(d[c], 0)
        i = d[c][k]+1
    return len(s)*n+i


def main():
    s = input()
    t = input()
    print(solve(s, t))


class TestAbc138_e(unittest.TestCase):
    def test_abc138_e(self):
        self.assertEqual(solve('contest', 'son'), 10)
        self.assertEqual(solve('contest', 'programming'), -1)
        self.assertEqual(solve('contest', 'sentence'), 33)
        self.assertEqual(solve('abc', 'abccccac'), 15)


if __name__ == "__main__":
    
    main()

Solution (Python):
from collections import defaultdict
from bisect import bisect
s = input()
t = input()
d = defaultdict(list)
for i in range(len(s)):
    d[s[i]].append(i)
for i in range(len(s)):
    d[s[i]].append(d[s[i]][0]+len(s))

ans = 0
idx = -1
for i in range(len(t)):
    if d[t[i]] == []:
        ans = -1
        break
    idx = d[t[i]][bisect(d[t[i]],idx)]
    if idx >= len(s):
        ans += 1
        idx %= len(s)
if ans != -1:
    ans *= len(s)
    ans += idx+1
print(ans)

Solution (Python):
from bisect import bisect_left
S = input()
T = input()
Ns = len(S)
S = S + S
ABC = [[] for _ in range(26)]
for i, s in enumerate(S):
    s = ord(s) - 97
    ABC[s].append(i)
ans = 0
l_s = 0
for t in T:
    t = ord(t) - 97
    abc = ABC[t]
    l = bisect_left(abc, l_s)
    if l == len(abc):
        print(-1)
        exit()
    l_s = abc[l]
    l_s += 1
    
    if l_s >= Ns:
        ans += Ns
        l_s -= Ns
print(ans + l_s)

Solution (Python):
from collections import defaultdict
from bisect import bisect_right
S=input()
T=input()
ls=len(S); lt=len(T)
S_dict=defaultdict(list)
for i,s in enumerate(S):
    S_dict[s].append(i+1)
T_list=[[] for _ in range(lt)]
for i,t in enumerate(T):
    if not S_dict[t]:
        print(-1)
        exit()
    T_list[i]=S_dict[t]

ans=T_list[0][0]
prev=T_list[0][0]
cycles=0

for i in range(1,lt):
    idx=bisect_right(T_list[i],prev)
    if idx==len(T_list[i]):
        cycles+=1
        prev=T_list[i][0]
    else:
        prev=T_list[i][idx]
    ans=prev+(cycles*ls)
    
print(ans)

Solution (Python):
from bisect import bisect_left

def solve(s,t):
    indices = [list() for _ in range(26)]
    for i,v in enumerate(s):
        indices[v].append(i)

    loop = 0
    cur = 0
    for c in t:
        l = indices[c]

        if not l:
            loop = 0
            cur = -1
            break
        if l[-1] < cur:
            cur = l[0]+1
            loop += 1
        else:
            cur = l[bisect_left(l, cur)]+1
            if cur == len(s):
                loop += 1
                cur = 0
    return loop*len(s)+cur

s,t = input(),input()
s = [ord(v)-ord('a') for v in s]
t = [ord(v)-ord('a') for v in t]
print(solve(s,t))

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

def bs(tl, i, l, r):
  while l < r:
    mid = (l + r) // 2
    if tl[mid] <= i:
      l = mid + 1
    else:
      r = mid
  return r


def main():
  s = input().strip()
  t = input().strip()
  sd = defaultdict(lambda: [])
  for i, _s in enumerate(s):
    sd[_s].append(i)

  for k, v in sd.items():
    sd[k] = list(sorted(v))

  ans = 0
  prev = -1
  for _t in t:
    if _t not in sd:
      break
    else:
      idx = bs(sd[_t], prev, 0, len(sd[_t]))
      if idx == len(sd[_t]):
        idx = sd[_t][0]
      else:
        idx = sd[_t][idx]
      if idx <= prev:
        ans += len(s) - prev + idx
      else:
        ans += idx - prev
      prev = idx
  else:
    print(ans)
    sys.exit(0)

  print(-1)


if __name__ == '__main__':
  main()

Solution (Python):
s=input()
t=input()
n=len(s)
import bisect
import collections
Chk=[False]*26
Fst=collections.defaultdict(int)
Pos=collections.defaultdict(list)
for i in range(n):
  ss=s[i]
  ns=ord(ss)-97
  if not Chk[ns]:
    Fst[ss]=i+1
    Chk[ns]=True
  Pos[ss]+=[i+1]
ans=0
prev=0
for i in range(len(t)):
  tt=t[i]
  if Fst[tt]==0:
    ans=-1
    break
  else:
    f,l=Fst[tt],Pos[tt][-1]
    if prev>=l:
      ans+=n-prev+f
      prev=f
    else:
      P=Pos[tt]
      next=P[bisect.bisect_right(P,prev)]
      ans+=next-prev
      prev=next
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import bisect

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

pos = [[] for i in range(26)]
for i, c in enumerate(s):
    pos[ord(c) - ord("a")].append(i)

poslen = [len(p) for p in pos]

syu = 0
tmp = -1
fin = False
for c in t:
    tgt = pos[ord(c) - ord("a")]
    tlen = poslen[ord(c) - ord("a")]
    if not tgt:
        print(-1)
        sys.exit()
    else:
        ins = bisect.bisect_left(tgt, tmp+1)
        if ins == tlen:
            syu += 1
            tmp = tgt[0]
            fin = True
        else:
            
            tmp = tgt[ins]
            fin = False

        


print(syu*n + tmp + 1)

Solution (Python):
import bisect
from collections import defaultdict
S = input()

s_dic = defaultdict(lambda: [])

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

start_index = -1
repeat_count = 0

T = input()
for t in T:
    if t not in s_dic:
        print(-1)
        exit()
    next_index = bisect.bisect_right(s_dic[t], start_index)
    if next_index == len(s_dic[t]):
        repeat_count += 1
        start_index = s_dic[t][0]
    else:
        start_index = s_dic[t][next_index]

print(repeat_count*len(S) + start_index + 1)

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

s=input().strip()
t=input().strip()

L=len(s)

NLIST=[[float("inf")]*26 for i in range(2*L+1)]

s2=s*2

for i in range(2*L-1,-1,-1):
    for j in range(26):
        if j==ord(s2[i])-97:
            NLIST[i][j]=i
            continue
            
        NLIST[i][j]=NLIST[i+1][j]
        


NOW=-1
ANS=0
for al in t:
    x=NLIST[NOW+1][ord(al)-97]
    if x==float("inf"):
        print(-1)
        sys.exit()

    else:
        ANS+=(x-NOW)
        NOW=x%L

print(ANS)