Problem:
 Score : 500 points    Problem Statement Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.   Let s' be the concatenation of 10^{100} copies of s . t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s' ).       Notes  A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net , c , and contest .       Constraints  1 \leq |s| \leq 10^5  1 \leq |t| \leq 10^5  s and t consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  s  t       Output If there exists an integer i satisfying the following condition, print the minimum such i ; otherwise, print -1 .        Sample Input 1 contest
son      Sample Output 1 10  t =  son is a subsequence of the string contestcon (the first 10 characters in s' =  contestcontestcontest... ), so i = 10 satisfies the condition.  On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s' ), so i = 9 does not satisfy the condition.  Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10 .       Sample Input 2 contest
programming      Sample Output 2 -1  t =  programming is not a substring of s' =  contestcontestcontest... . Thus, there is no integer i satisfying the condition.       Sample Input 3 contest
sentence      Sample Output 3 33  Note that the answer may not fit into a 32 -bit integer type, though we cannot put such a case here.

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


def main():
	s = input()
	n = len(s)
	s = s + s
	t = input()
	if set(t) - set(s):
		print(-1)
		exit()
	d = defaultdict(list)
	for i in range(2 * n):
		d[s[i]] += [i]
	cur = ncnt = 0

	for c in t:
		x = d[c][bisect_left(d[c], cur)]
		if x < n:
			cur = x + 1
		else:
			cur = x - n + 1
			ncnt += 1
	print(ncnt*n + cur)


if __name__ == "__main__":
	main()

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

s = input()
n = len(s)
s = s + s
t = input()
if set(t) - set(s):
	print(-1)
	exit()
d = defaultdict(list)
for i in range(2 * n):
	d[s[i]] += [i]
cur = tot = 0
for c in t:
	x = d[c][bisect_left(d[c], cur)]
	if x < n:
		cur = x + 1
	else:
		cur = x - n + 1
		tot += n
tot += cur
print(tot)

Solution (Python):
import bisect
s=list(input())
t=list(input())
s=s+s
u=[[] for i in range(26)]
x=0
count=0

for i in range(ord('a'),ord('z')+1):
    for j in range(len(s)):
        if i==ord(s[j]):
            u[i-97].append(j+1)

for i in range(len(t)):
    if len(u[ord(t[i])-97])==0:
        print(-1)
        exit()
    b=bisect.bisect_left(u[ord(t[i])-97],x+1)
    
    if u[ord(t[i])-97][b]>len(s)//2:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]-len(s)//2
        
    else:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]
        
        
print(count)

Solution (Python):



import sys
from bisect import bisect_left

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






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


ans = p = 0
for ch in t:
    pos_list = charmap[ord(ch) - ord('a')]
    if len(pos_list) == 0:
        print('-1')
        exit(0)

    p = pos_list[bisect_left(pos_list, p)] + 1
    if len(s) <= p:
        ans += len(s)
        p -= len(s)

ans += p
print(ans)

Solution (Python):



import sys
from bisect import bisect_left

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






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


p = ans = 0
for ch in t:
    ch_position_list = s_map[ord(ch) - ord('a')]
    if len(ch_position_list) == 0:
        print('-1')
        sys.exit()

    p = ch_position_list[bisect_left(ch_position_list, p)] + 1
    if len(s) <= p:
        ans += len(s)
        p -= len(s)

ans += p
print(ans)

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

s = input()
t = input()
idxs = defaultdict(list)

for i, c in enumerate(s):
    idxs[c].append(i)
for i, c in enumerate(s):
    idxs[c].append(len(s) + i)

ans, cur_i = -1, -1
for c in t:
    if c not in idxs: print(-1); break
    a = idxs[c]
    nxt = a[bisect_right(a, cur_i)]
    ans += nxt - cur_i
    cur_i = nxt % len(s)
else: print(ans+1)

Solution (Python):
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
T = str(input())
N = len(S)
cou = int(0)
cur = int(0)
move = int(0)
S_map = [[]for _ in range(26)]

for i in range(N):
    S_map[ord(S[i])-97].append(i+1)
for i in range(N):
    S_map[ord(S[i])-97].append(N+i+1)

for c in T:

    if S_map[ord(c)-97]==[]:
        ans = -1
        break
    move = bisect.bisect_left(S_map[ord(c)-97],cur+1)
    cur = S_map[ord(c)-97][move]
    if cur>=N:
        cou += 1
        cur -= N

if ans==0:
    ans = cou*N + cur

print(ans)

Solution (Python):
s = input()
t = input()
s_map = [[] for _ in range(26)]
import bisect
for i in range(len(s)):
    s_map[ord(s[i])-97].append(i)
for i in range(len(s)):
    s_map[ord(s[i])-97].append(len(s)+i)
cur = 0
count = 0
f = True
for c in t:
    if s_map[ord(c)-97] == []:
        f = False
        break
    np = bisect.bisect_left(s_map[ord(c)-97],cur)
    cur = s_map[ord(c)-97][np]+1
    
    if cur >= len(s):
        count += 1
        cur -= len(s)
print(count * len(s) + cur if f else -1)

Solution (Python):
import sys


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

    appear_pos = {}  
    for idx, T in enumerate(t):
        if T not in appear_pos:
            appear_pos[T] = [idx]
        else:
            appear_pos[T].append(idx)

    search_idx = {}
    for key in appear_pos.keys():
        search_idx[key] = -1

    loop_count = 0
    find_idx = -1
    for S in s:
        if S not in appear_pos:
            print(-1)
            sys.exit()

        while True:
            search_idx[S] += 1
            if len(appear_pos[S]) == search_idx[S]:
                
                loop_count += 1
                for key in appear_pos.keys():
                    search_idx[key] = -1
                find_idx = appear_pos[S][0]
                break

            idx_new = appear_pos[S][search_idx[S]]
            if idx_new > find_idx:
                find_idx = idx_new
                break

    print(find_idx+loop_count*len(t)+1)


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left

s = input()
n = len(s)
s = s + s
t = input()
m = len(t)

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

for i in range(2*n):
    ls[ord(s[i])-97].append(i)

res = 0
flg = True
ind = -1
for i in range(m):
    if ls[ord(t[i])-97] == []:
        flg = False
        break
    nind = ls[ord(t[i])-97][bisect_left(ls[ord(t[i])-97],ind+1)]
    res += nind - ind 
    if nind >= n:
        nind -= n
    ind = nind
if flg:print(res)
else:print(-1)

Solution (Python):



def main():
    from bisect import bisect_left

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    
    
    
    
    

    
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 0
    p = 0  

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        
        
        
        
        p = alpha[c][bisect_left(alpha[c], p)] + 1

        
        if p >= n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from bisect import bisect_left

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    
    
    
    
    

    
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 0
    p = 0

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        
        
        
        p = alpha[c][bisect_left(alpha[c], p)] + 1

        if p >= n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from bisect import bisect_left

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    
    
    

    
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 0
    p = 0

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        pi = bisect_left(alpha[c], p)
        p = alpha[c][pi]
        p += 1

        if p >= n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import bisect
S = input()
E = {S[i]:[] for i in range(len(S)-1)}
for i in range(len(S)-1):
  E[S[i]].append(i)
T = input()
a = len(S)-1
ans=0
now = -1
for i in range(len(T)-1):
  if not T[i] in E.keys():
    print(-1)
    exit()
  s=E[T[i]]
  b= bisect.bisect_right(s,now)
  
  if b==len(s):
    ans+=s[0]+1+a-1-now
    now=s[0]
  else:
    ans+=s[b]-now
    now=s[b]
print(ans)

Solution (Python):
def upperbound(ar, value):
    low = 0
    high = len(ar)
    while low < high:
        mid = (low + high) >> 1
        if value > ar[mid]:
            low = mid + 1
        else:
            high = mid
    return low


s = input()
t = input()
data = {}
for index, val in enumerate(s):
    if val not in data:
        data[val] = [index]
    else:
        data[val].append(index)
ok = True
index = 0
mod = len(s)
pos = [0] * (len(t))
for i, c in enumerate(t):
    if c not in data:
        ok = False
        break
    else:
        curr_index = upperbound(data[c], index)
        if curr_index >= len(data[c]):
            pos[i] = data[c][0]
        else:
            pos[i] = data[c][curr_index]
        index = (pos[i] + 1) % mod
if ok:
    result = pos[0] + 1
    for i in range(1, len(t)):
        if pos[i] > pos[i - 1]:
            result = result + (pos[i] - pos[i - 1])
        else:
            result = result - (pos[i - 1] + 1) + mod + pos[i] + 1
    print(result)
else:
    print(-1)

Solution (Python):
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue








def main():
    s = raw_input().strip()
    t = raw_input().strip()
    d = defaultdict(list)
    for idx, c in enumerate(s):
        d[c].append(idx)
    i, offset = 1, -1
    for c in t:
        idx = bisect.bisect_right(d[c], offset)
        if not d[c]:
            print -1
            return
        if idx == len(d[c]):
            i+=1
            offset = d[c][0]
        else:
            offset = d[c][idx]
    print (i-1)*len(s)+offset+1






main()

Solution (Python):
import bisect


s = input()
t = input()


s_len = len(s)
t_len = len(t)

index_in_s = {}
for ch in "abcdefghijklmnopqrstuvwxyz":
    index_in_s[ch] = [] 

for j in range(0, s_len):
    index_in_s[s[j]].append(j)


subtract = 0
current = s_len 
is_subsequence = True
for ch in t:
    
    if len(index_in_s[ch]) == 0:
        is_subsequence = False
        break
    else:
        pos = bisect.bisect_right(index_in_s[ch], current)
        if pos < len(index_in_s[ch]): 
            subtract += 1
            current = index_in_s[ch][pos]
        else: 
            
            current = index_in_s[ch][0]


if is_subsequence:
    i = (t_len - 1 - subtract) * s_len + current + 1
else:
    i = -1

print(i)

Solution (Python):
from collections import defaultdict
import bisect


S = input()
T = input()

if set(T) - set(S):
    print(-1)
    exit()

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

now = -1
count = 0
for t in T:
    if dic[t][-1] < now+1:
        now = -1
        count += 1
    idx = bisect.bisect_left(dic[t], now+1)
    now = dic[t][idx]

ans = count*len(S) + now + 1
print(ans)

Solution (Python):
from collections import defaultdict
import bisect


S = input()
T = input()

if set(T) - set(S):
    print(-1)
    exit()

dic = defaultdict(list)
leng_dic = defaultdict(int)

for pos, s in enumerate(S):
    dic[s].append(pos)
    leng_dic[s] += 1

length = len(S)
now = -1
count = 0
for t in T:
    if dic[t][-1] < now+1:
        now = -1
        count += 1
    idx = bisect.bisect_left(dic[t], now+1)
    now = dic[t][idx]

ans = count*length + now + 1
print(ans)

Solution (Python):
import bisect

s,t=input(),input()
ls=len(s)
lt=len(t)
A=[[] for i in range(26+1)]
L=[0 for i in range(26+1)]

for i in range(ls):
  A[ord(s[i])-96].append(i+1)
  L[ord(s[i])-96]+=1


tmp=0
ans=0
for i in range(lt):
  ii=ord(t[i])-96

  if L[ii]==0:
    print(-1)
    exit()
  else:
    iii=bisect.bisect(A[ii],tmp)
    
    if iii==L[ii]:
      ans+=ls-tmp+A[ii][0]
      tmp=A[ii][0]
    else:
      ans+=A[ii][iii]-tmp
      tmp=A[ii][iii]
print(ans)

Solution (Python):
def slove():
    import sys
    import collections
    import bisect
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    t = str(input().rstrip('\n'))
    d = collections.defaultdict(list)
    for i in range(len(s)):
        d[s[i]] += [i]

    loop = 0
    pos = 0
    for i in range(len(t)):
        if t[i] not in d:
            print(-1)
            exit()
        else:
            pos = bisect.bisect_left(d[t[i]], pos)
            if len(d[t[i]]) == pos:
                loop += 1
                pos = 0
            pos = d[t[i]][pos] + 1
    print(loop * len(s) + pos)


if __name__ == '__main__':
    slove()

Solution (Python):
import bisect

def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)

    l = [[] for _ in range(26)]
    for i in range(n):
        l[ord(s[i]) - ord('a')].append(i)
    for i in range(n):
        l[ord(s[i]) - ord('a')].append(i+n)

    ans = 0
    p = 0
    for i in range(m):
        c = ord(t[i]) - ord('a')
        if len(l[c]) == 0:
            print(-1)
            return
        p = l[c][bisect.bisect_left(l[c], p)] + 1
        if p >= n:
            p -= n
            ans += n
    ans += p
    print(ans)
    return

main()

Solution (Python):
from bisect import bisect_right
s = input()
t = input()
d = {}

for i in range(len(s)):
    if s[i] in d:
        d[s[i]] += [i]
    else:
        d[s[i]] = [i]

count = 0
cur = -1
for i in t:
    if i not in d:
        print(-1)
        exit()
    if cur < d[i][-1]:
        cur = d[i][bisect_right(d[i], cur)]
        continue
    else:
        count += 1
        cur = d[i][0]
print(count*len(s)+cur+1)

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

S = input()
T = input()
N = len(S)


set_s = set(S)
set_t = set(T)
for c in set_t:
    if not c in set_s:
        print(-1)
        exit()


idxs = defaultdict(list)
for i in range(N):
    idxs[S[i]].append(i)

p = -1
loop_cnt = 0
for c in T:
    idx = bisect_right(idxs[c], p)
    
    if idx >= len(idxs[c]):
        loop_cnt += 1
        p = idxs[c][0]
    else:
        p = idxs[c][idx]

ans = N * loop_cnt + p + 1
print(ans)

Solution (Python):
import bisect
ai = [[] for i in range(26)]
s = list(input())
t = list(input())
n = len(s)
for i in range(n):
    ai[int(ord(s[i])-97)].append(i)
n2 = len(t)
count = 0
if len(ai[int(ord(t[0]))-97]) > 0:
    now = ai[int(ord(t[0]))-97][0]
    for i in range(1,n2):
        nex = int(ord(t[i]))-97
        n3 = len(ai[nex])
        if n3 == 0:
            count = 0
            now = -2
            break
        else:
            ni = bisect.bisect_right(ai[nex],now)
            
            if ni == n3:
                ni = 0
            if ai[nex][ni] > now:
                now = ai[nex][ni]
            else:
                count += 1
                now = ai[nex][ni]
    print(count*n+now+1)
else:
    print(-1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_right

S = [ord(x)-ord('a') for x in readline().rstrip().decode('utf-8')]
T = [ord(x)-ord('a') for x in readline().rstrip().decode('utf-8')]

index = [[] for _ in range(26)]
for i,x in enumerate(S):
    index[x].append(i)

LS = len(S)
for x in index:
    if x:
        x.append(x[0] + LS)

ptr = -1 
complete = True
for t in T:
    seq = index[t]
    if not seq:
        complete = False
        break
    i = ptr%LS
    j = bisect_right(seq,i)
    ptr += seq[j]-i

if complete:
    answer = ptr + 1
else:
    answer = -1
print(answer)

Solution (Python):
import bisect

S = input()
T = input()


alp = {} 
for i,s in enumerate(S):
    alp.setdefault(s,[]).append(i)



bef_idx = -1
ans = 0
for t in T:
    
    if t not in alp:
        ans = -(bef_idx+2)
        break

    idx_list = alp[t]
    
    
    if idx_list[-1] <= bef_idx:
        ans += len(S)
        bef_idx = -1
    idx = bisect.bisect_left(idx_list,bef_idx+1)
    bef_idx = idx_list[idx]
    
    
ans += (bef_idx+1)
print(ans)

Solution (Python):
s = input()
t = input()
n = len(s)
now = -1
count = 0
if set(t) <= set(s):
  for i in t:
    now = s.find(i,now+1)
    if now == -1:
      count += 1
      now = s.find(i)
  print(now + 1 + count*n)
else:
  print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    S=input()
    T=input()
    if(set(T)-set(S)):
        print(-1)
        return
    n=len(S)
    C=[[] for _ in range(26)]
    for i,s in enumerate(S*2): C[ord(s)-97].append(i)
    from bisect import bisect_left
    ans=0
    for s in T:
        j=bisect_left(C[ord(s)-97],ans%n)
        ans+=C[ord(s)-97][j]-ans%n+1
    print(ans)
resolve()

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

if set(t).issubset(set(s)):
    p = -1
    r = 0
    
    for i in t:
        p = s.find(i, p+1)
        if p == -1:
            r += 1
            p = s.find(i)
        
    print(p + 1 + len(s)*r)
    
else:
    print(-1)

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

l = len(s)
d = dict()
for i in range(l):
    if s[i] in d.keys():
        d[s[i]].append(i+1)
    else:
        d[s[i]] = [i+1]

ans = 0
now = 0
for i in t:
    if i not in d.keys():
        print(-1)
        exit()

    a = bisect.bisect_right(d[i], now)
    if a == len(d[i]):
        now = d[i][0]
        ans += l
    else:
        now = d[i][a]

print(ans + now)

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

l = len(s)
d = dict()
for i in range(l):
    if s[i] in d.keys():
        d[s[i]].append(i+1)
    else:
        d[s[i]] = [i+1]

ans = 0
now = 0
for i in t:
    if i not in d.keys():
        print(-1)
        exit()

    a = bisect.bisect_right(d[i], now)
    if a == len(d[i]):
        now = d[i][0]
        ans += l
    else:
        now = d[i][a]

print(ans + now)

Solution (Python):
import bisect

S = input()
T = input()

Sset = set(list(S))
Tset = set(list(T))
if len(Tset-Sset) > 0:
  print(-1)
  exit()

SS = S * 2
SSpos = {}
for i in range(len(SS)):
  if SS[i] in SSpos:
    SSpos[SS[i]].append(i)
  else:
    SSpos[SS[i]] = [i]
for i in SSpos:
  SSpos[i].sort()


ans = 0
i = 0
for t in T:
  j = bisect.bisect_left(SSpos[t],i)
  ans += SSpos[t][j] - i + 1
  
  i = SSpos[t][j] + 1
  if i >= len(S):
    i -= len(S)
print(ans)

Solution (Python):
from sys import exit

s = input()
t = input()

tset = set(t)
slen = len(s)
aord = ord('a')
if len(tset - set(s)) != 0:
    print(-1)
    exit()

s2t = [i - aord for i in (s + s).encode('ascii')]
lut = [[-1] * slen for _ in range(26)]
for c in tset:
    b = ord(c) - aord
    j = 0
    for i in range(slen * 2 - 1, -1, -1):
        if s2t[i] == b:
            j = 0
        else:
            j += 1
        if i < slen:
            lut[b][i] = j

p = 0
for c in t:
    b = ord(c) - aord
    p += lut[b][p % slen] + 1
print(p)

Solution (Python):



import bisect


def ch_to_int(c):
    return ord(c) - 96


def main():
    s = input()
    t = input()
    pos = 0
    count = 0
    ch = [[] for i in range(27)]

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

    for i in range(len(t)):
        c = ch_to_int(t[i])
        li = ch[c]

        if len(li) == 0:
            pos = -1
            count = 0
            break

        next_index = bisect.bisect_left(li, pos)
        
        if next_index >= len(li):
            next_pos = li[0]
            count += 1
            pos = next_pos + 1
        else:
            if pos == li[next_index]:
                pos += 1
            else:
                pos = li[next_index] + 1
        

    print(pos + count * len(s))


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import collections

s = input().rstrip()
t = input().rstrip()

counter_s = collections.Counter(s)
counter_t = collections.Counter(t)
for c in counter_t.keys():
    if c not in counter_s.keys():
        print(-1)
        exit()

s_indices = collections.defaultdict(list)
for i, c in enumerate(s):
    if c in counter_t.keys():
        s_indices[c].append(i)

index = 0
count = 0
offset = 0
while index < len(t):
    c = t[index]
    i = bisect.bisect_left(s_indices[c], offset)
    if i == len(s_indices[c]):
        count += 1
        offset = 0
    else:
        offset = s_indices[c][i] + 1
        index += 1
print(len(s) * count + offset)

Solution (Python):

from bisect import bisect_left

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



setS = set(S)
for t in T:
    if t not in setS:
        print (-1)
        exit()

lst = [[] for _ in range(26)]
for index, x in enumerate(S):
    lst[ord(x) - 97].append(index)

tmp = 0 
roop = 0
for t in T:
    tmp = bisect_left(lst[ord(t) - 97], tmp)
    if tmp == len(lst[ord(t) - 97]):
        roop += 1
        tmp = lst[ord(t) - 97][0] + 1
    else:
        tmp = lst[ord(t) - 97][tmp] + 1



print (roop * len(S) + tmp)

Solution (Python):
from collections import defaultdict as dd
from bisect import bisect_right
s = input()
t = input()
n = len(s)
cmap = dd(list)
for i, c in enumerate(s):
    cmap[c].append(i)
for i, c in enumerate(s):
    cmap[c].append(i+n)
cmap = dict(cmap)
a = 0
pos = -1
for c in t:
    try:
        i = bisect_right(cmap[c], pos)
        ind = cmap[c][i]
    except:
        print(-1)
        exit()
    if ind >= n:
        a += n
        pos = ind - n
    else:
        pos = ind
print(a + pos + 1)

Solution (Python):
from collections import defaultdict
import bisect

s = input()
t = input()

n = len(s)
m = len(t)

d = defaultdict(list)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i)

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

pos = -1
ans = 0

for c in t:
    l = d[c]
    if l:
        i = bisect.bisect_right(l, pos)
        ind = l[i]
        if ind >= n:
            pos = ind - n
            ans += n
        else:
            pos = ind    
    else:
        ans = -1
        break

print(ans if ans==-1 else ans+pos+1)

Solution (Python):
from collections import defaultdict
import bisect

s = input()
t = input()

n = len(s)
m = len(t)

d = defaultdict(list)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i)

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

pos = -1
ans = 0

for c in t:
    l = d[c]
    if l:
        ind = bisect.bisect_right(l, pos)
        ans += l[ind]-pos
        if l[ind] >= n:
            pos = l[ind] - n
        else:
            pos = l[ind]    
    else:
        ans = -1
        break

print(ans)

Solution (Python):
import bisect
s = input()
t = input()
d = { c: [] for c in t }
for i, c in enumerate(s):
  if c in d:
    d[c].append(i)

n = -1
ans = 0


for j, c in enumerate(t):
  l = d[c]
  if l:
    i = bisect.bisect_right(l, n)
    if i == len(l):
      ans += len(s)
      n = l[0]
    else:
      n = l[i]
    if j == len(t) - 1:
      if i == len(l):
        ans += l[0] + 1
      else:
        ans += l[i]+1
  else:
    ans = -1
    break

print(ans)

Solution (Python):
import bisect
s = input()
t = input()
d = { c: [] for c in t }
for i, c in enumerate(s):
  if c in d:
    d[c].append(i)
for dc in d.values():
  dc.sort()

n = -1
ans = 0


for j, c in enumerate(t):
  l = d[c]
  if l:
    i = bisect.bisect_right(l, n)
    if i == len(l):
      ans += len(s)
      n = l[0]
    else:
      n = l[i]
    if j == len(t) - 1:
      if i == len(l):
        ans += l[0] + 1
      else:
        ans += l[i]+1
  else:
    ans = -1
    break

print(ans)

Solution (Python):
from bisect import bisect



s = input()
t = input()
a = 'abcdefghijklmnopqrstuvwxyz'
d = {}
for ch in a:
  d[ch] = []
for ch,n in zip(s,range(len(s))):
  d[ch].append(n)

rep = 0
p = -1
for ch in t:
  if len(d[ch])==0:
    print("-1")
    exit()
  else:
    i = bisect(d[ch],p)
    if i!=len(d[ch]):p=d[ch][i]
    else:
      p = d[ch][0]
      rep+=1

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

Solution (Python):
from bisect import bisect


def search_alphabet_index(string):
    cs = [[] for i in range(26)]
    for i, s in enumerate(string):
        j = ord(s) - ord("a")
        cs[j].append(i)
    return cs


def main():
    S = input()
    T = input()
    N = len(S)

    cs = search_alphabet_index(S)

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

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


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect


def search_alphabet_index(string):
    cs = [[] for i in range(26)]
    for i, s in enumerate(string):
        j = ord(s) - ord("a")
        cs[j].append(i)
    return cs


def main():
    S = input()
    T = input()
    N = len(S)

    cs = search_alphabet_index(S)

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

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


if __name__ == "__main__":
    main()

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

def main():
    s = input()
    t = input()
    dictPos = defaultdict(list)
    N = len(s) - 1
    for i in range(N):
        ch = s[i]
        dictPos[ch].append(i+1)
    countLoop = 0
    lastPos = -1
    M = len(t) - 1
    for i in range(M):
        ch = t[i]
        listPos = dictPos[ch]
        if len(listPos) == 0:
            print(-1)
            exit()
        if listPos[-1] <= lastPos:
            lastPos = listPos[0]
            countLoop += 1
        else:
            lastPos = listPos[bisect_right(listPos, lastPos)]
    ans = N * countLoop + lastPos
    print(ans)

if __name__ == '__main__': main()

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

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

count_loop = 0
last_pos = -1
for ch in t:
    list_pos = dict_pos[ch]
    if len(list_pos) == 0:
        print(-1)
        quit()
    if list_pos[-1] <= last_pos:
        last_pos = list_pos[0]
        count_loop += 1
    else:
        last_pos = list_pos[bisect.bisect_right(list_pos, last_pos)]

print(count_loop * len(s) + last_pos)

Solution (Python):
def main():
    s = str(input())
    t = str(input())
    if set(t) <= set(s):
        x = -1
        counter = 0
        for i in t:
            x = s.find(i, x+1)
            if x == -1:
                counter += 1
                x = s.find(i)
        print(x+1+counter*len(s))
    else:
        print(-1)
if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()
ls = len(s)
lt = len(t)
D = {}
for i, item in enumerate(s):
    try:
        D[item].append(i)
    except:
        D[item] = [i]

for i in D.keys():
    
    D[i].append(D[i][0] + ls)



import bisect

def e():
    ans = 0
    ind = -1
    for i in range(lt):
        try:
            L = D[t[i]]
            
            bs = L[bisect.bisect_right(L, ind)]
            
            ans += bs - ind
            ind = bs % ls
        except:
            return -1
    return ans

print(e())

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

N = len(s)

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

for c in set_t:
    if c not in set_s:
        print(-1)
        exit()


idxs = defaultdict(list)
for i in range(N):
    idxs[s[i]].append(i)


current_idx = -1 
total = 0
for c in t:
    next_idx = bisect.bisect(idxs[c], current_idx) 

    if next_idx == len(idxs[c]):
        total += N
        current_idx = idxs[c][0]
    else:
        current_idx = idxs[c][next_idx]


print(total + current_idx + 1)