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 bisect
s = input()*2
lens = len(s)//2
t = input()
appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
cnt = -1
bis = bisect.bisect_right
ans = 0

for i, ch in enumerate(s):
  appear[ch].append(i)
  
for j in t:
  if appear[j]:
    idx = bis(appear[j],cnt)
    ans += appear[j][idx] - cnt
    cnt = appear[j][idx]%lens
  else:
    print(-1)
    exit()
print(ans)

Solution (Python):
import sys



def sss(cc, l):
	
	if len(l)==0:
		return (-1,'no_chr')
	elif cc > l[-1]:
		return (-1,'over')
	
	
	if cc <= l[0]:
		return (l[0],'')
	
	ue=len(l) - 1 
	sita=0
	while abs(ue - sita) > 1:
		mid = (ue + sita)//2
		if l[mid] >= cc:
			ue = mid
		else:
			sita = mid
	return (l[ue],'')

def main():
	s = input()
	t = input()
	i = 0
	bbb=[[] for i in range(26)]
	ctoi=lambda c : ord(c)-97
	
	for i, c in enumerate(s):
		bbb[ctoi(c)].append(i+1)
	
	for i, b in enumerate(bbb):
		pass
		
	
	cc = 0
	kkk=0
	ret = 0
	for c in t:
		address=ord(c) - ord('a')
		l=bbb[address]
		
		
		nc, st = sss(cc, l)
		cc = nc + 1
		
		if st =='no_chr':
			print(-1)
			return 
			
		if st == 'over':
			kkk += 1
			cc = l[0] + 1
			
	
	ret = len(s) * kkk + cc - 1
	print(ret)
			
		

	
	


if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from bisect import bisect

s = input()
t = input()

if len(set(t) & set(s)) != len(set(t)):
    print(-1)
    exit()

d = dict()

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

ans = 0
res = d[t[0]][0]

for i in range(1, len(t)):
    index = bisect(d[t[i]], res)
    if index == len(d[t[i]]):
        ans += len(s)
        res = d[t[i]][0]
    else:
        res = d[t[i]][index]

ans += res + 1

print(ans)

Solution (Python):
from bisect import bisect

s = input()
t = input()

d = dict()

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

for i, si in enumerate(s):
    d[si].append(i)

ans = 0
res = -1

for i in range(len(t)):
    if d[t[i]] == []:
        print(-1)
        exit()
    index = bisect(d[t[i]], res)
    if index == len(d[t[i]]):
        ans += len(s) - res + d[t[i]][0]
        res = d[t[i]][0]
    else:
        ans += d[t[i]][index] - res
        res = d[t[i]][index]

print(ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

S = input()
T = input()

if any(i not in sorted(list(set(S))) for i in sorted(list(set(T)))):
    print(-1)
    exit()

d = {}
for sidx, s in enumerate(S):
    if s not in d.keys():
        d[s] = []
    d[s].append(sidx+1)

if 'LOCAL' in os.environ:
    print('d', d)
current_idx = -1
round_count = 0
for tidx, t in enumerate(T):
    
    if 'LOCAL' in os.environ:
        print('t:  ', t, tidx)

    char_position_idx = bisect.bisect_right(d[t], current_idx)
    if char_position_idx >= len(d[t]):
        
        round_count += 1
        current_idx = d[t][0]
        continue

    
    
    if d[t][char_position_idx] < current_idx:
        
        current_idx = d[t][0]
        round_count += 1
    else:
        
        current_idx = d[t][char_position_idx]
print(len(S)*round_count + current_idx)

Solution (Python):
from collections import defaultdict
import bisect

s = input()
t = input()

ls = len(s)-1
cnt = 0
num = -1
di = defaultdict(list)
for ind,i in enumerate(s):
    di[i].append(ind)

for i in t:
    if(i not in di):
        print(-1)
        break
    if(di[i][-1]<=num):
        cnt += ls-num+di[i][0]+1
    else:
        x = bisect.bisect_left(di[i],num+1)
        if(num==-1):
            cnt += di[i][x]
        else:
            cnt += di[i][x]-num
    num = cnt%(ls+1)
    

else:
    print(cnt+1)

Solution (Python):
import bisect

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


dictionary = {}

tt = t[:]
ss = dict(zip(list(range(len(s * 2))), s * 2))

for i in range(len(ss)):
    c = ss[i]
    if c not in dictionary:
        dictionary[c] = []
    dictionary[c].append(i)

result = 0
current_idx = 0
sLen = len(s)

for c in t:
    if c not in dictionary:
        print(-1)
        exit(0)
    indexes = dictionary[c]
    next = dictionary[c][bisect.bisect_left(indexes, current_idx)] + 1
    result += next - current_idx
    current_idx = next
    if next >= sLen:
        current_idx -= sLen

print(result)

Solution (Python):
from collections import defaultdict
from bisect import bisect_left
 
s = input()
t = input()
s_len = len(s)
t_len = len(t)
if not set(t) <= set(s):
  print(-1)
else: 
  idx = defaultdict(list)
  for i in range(s_len):
    idx[s[i]].append(i)
  
  loop_num = 0
  current_position = -1
  for i in range(t_len):
    char = t[i]
    tmp_idx = idx[char]
    n = bisect_left(tmp_idx, current_position+1)
    if n < len(tmp_idx):
      current_position = tmp_idx[n]
    else:
      current_position = tmp_idx[0]
      loop_num += 1
  print(s_len * loop_num + current_position + 1)

Solution (Python):
import bisect

s = input()
t = input()
T = set(t)
s_num = len(s)
t_num = len(T)


dict = {}
appearing_times = {}


for w in T:
    dict[w] = []
    appearing_times[w] = 0
    index = -1
    while True:
        index = s.find(w, index + 1)
        if index == -1 and appearing_times[w] == 0:
            print(-1)
            exit()
        elif index == -1:
            break
        else:
            dict[w].append(index)
            appearing_times[w] += 1


count = 0

s_index = 0
w_pre = 'none'

for w in t:
    idx = bisect.bisect_left(dict[w], s_index)
    if w == w_pre:
        idx += 1
        if idx == appearing_times[w]:
            count += 1
            idx = 0

    if idx < appearing_times[w]:
        s_index = dict[w][idx]
    else:
        count += 1
        s_index = dict[w][0]
    w_pre = w

print(count * s_num + s_index + 1)

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    



def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    



def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

Solution (Python):
import sys
from bisect import bisect_right
input = lambda: sys.stdin.readline()[:-1]
from collections import defaultdict
s =input()
lenth=len(s)
ss=s*2
t =input()
place=defaultdict(list)

for k,l in enumerate(s):
	place[l].append(k+1)
	place[l].append(k+1+lenth)
for i in place.values():
	i.sort()
now=0
ans=0

for i in t:
	if not place[i]:
		print(-1)
		exit()
	mt=place[i][bisect_right(place[i],now)]
	if mt>lenth:
		mt-=lenth
		ans+=lenth
	now=mt
print(ans+now)

Solution (Python):
s = input()
t = input()
s_ = s[:]
cnt = 0
tlen = len(t)
ans = 0
flag = True

while cnt < tlen:
    
    num = s_.find(t[cnt])
    
    if num != -1:
        ans += (num+1)
        s_ = s_[(num+1):]
        cnt += 1
        flag = False
    else:
        if flag:
            print(-1)
            exit(0)
        ans += len(s_)
        s_ = s[:]
        flag = True
        
print(ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def num__grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]


s = input()
t = input()
ns = len(s)
nt = len(t)
alpha = "abcdefghijklmnopqrstuvwxyz"
aldi = {}
for i in alpha:
    aldi[i] = []

for i in range(ns):
    aldi[s[i]].append(i + 1)


num = []
if aldi[t[0]] == []:
    print("-1")
    exit()
mae = aldi[t[0]][0]
num.append(mae)
for i in range(1, nt):
    if aldi[t[i]] == []:
        print("-1")
        exit()
    else:
        kk = bisect_right(aldi[t[i]], mae)
        if kk == len(aldi[t[i]]):
            kk = aldi[t[i]][0]
        else:
            kk = aldi[t[i]][kk]
        mae = kk
        num.append(kk)

ans += num[0]
for i in range(1, len(num)):
    if num[i] <= num[i - 1]:
        ans += ns - num[i - 1] + num[i]
    else:
        ans += num[i] - num[i - 1]

if ans > 10 ** 100:
    print(-1)
else:
    print(ans)

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

alpha = [[] for _ in range(26)]
c2i = lambda x: ord(x) - ord('a')

for i, sl in enumerate(s):
    alpha[c2i(sl)].append(i)

pos = -1
count = 0
length = len(s)
for tl in t:
    places = alpha[c2i(tl)]
    if len(places) == 0:
        print(-1)
        break

    index = bisect_left(places, pos+1)
    if index != len(places):
        place = places[index]
        count += place - pos
        pos = place
    else:
        count += (length-pos-1) + places[0] + 1
        pos = places[0]
else:
    print(count)

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

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

ans = 0
current_idx = -1

for c in t:
    if c not in s_idx_map:
        print(-1)
        os.sys.exit()
    induces = s_idx_map[c]
    pos = bisect.bisect_left(induces, current_idx)
    if pos < len(induces) and induces[pos] == current_idx:
        pos += 1
    if pos < len(induces):
        ans += induces[pos] - current_idx
        current_idx = induces[pos]
    else:
        ans += (len(s)-1) - current_idx
        ans += induces[0] + 1
        current_idx = induces[0]

print(ans)

Solution (Python):
s=input()
t=input()
T = len(t)
num = 0
nowi = -1
nexti =-1
for i,ti in enumerate(t):
    nexti = s[nowi+1:].find(ti)
    if nexti == -1:
        num+=1
        nexti =s.find(ti)
        nowi = nexti
        if nexti ==-1:
            print(-1)
            exit()
    else:
        nowi = nexti+nowi+1
if num<= 10**100 -1:
    print(len(s)*num + nowi+1)

Solution (Python):
s = input()
t = input()
n = len(s)
nxt = [list() for x in range(n + 1)]
nxt[n] = [n for x in range(26)]
for i in range (n - 1, -1, -1):
    for v in nxt[i + 1]:
        nxt[i].append(v)
    nxt[i][ord(s[i]) - ord('a')] = i;
ans = 0
cur = 0
for i in range (len(t)):
    c = ord(t[i]) - ord('a')
    if (nxt[0][c] == n) :
        ans = 0
        cur = -1
        break
    if (nxt[cur][c] == n) :
        ans += 1
        cur = 0
    cur = nxt[cur][c] + 1
print(ans * n + cur)

Solution (Python):
s,t=([ord(c)-ord('a') for c in input()]for _ in'xx')
if set(t)-set(s):
  print(-1)
else:
  u=s+s
  nxt = [None for _ in range(len(u)+1)]
  nxt[len(u)]=[0 for _ in range(26)]
  for i in range(len(u)-1,-1,-1):
    nxt[i] = [v+1 for v in nxt[i+1]]
    nxt[i][u[i]]=0
  p = 0
  for c in t:
    p += nxt[p%len(s)][c]+1
  print(p)

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

def solve():
  s = input().strip()
  t = input().strip()
  query = [[] for _ in range(26)]
  n = len(s)
  for i in range(n):
    alphabet = ord(s[i])-97
    query[alphabet].append(i+1)

  
  place = -1
  loops = 0
  for j in t:
    tmp = ord(j)-97
    if len(query[tmp]) == 0:
      print(-1)
      exit()
    else:      
      nextplace = bisect.bisect_right(query[tmp],place)
      if nextplace == len(query[tmp]):
        loops += 1
        place = query[tmp][0]
      else:
        place = query[tmp][nextplace]

  print(loops*n +place)
solve()

Solution (Python):
s = input()
t = input()
temp = s[:]
cnt = 0
strmax = len(t)
ans = 0
flag = True

while cnt<strmax:
	num = temp.find(t[cnt])
	if num != -1:
		ans+=num+1
		temp = temp[num+1:]
		cnt+=1
		flag = False
	else:
		if flag:
			print("-1")
			exit(0)
		ans+=len(temp)
		temp = s[:]
		flag = True

print(ans)

Solution (Python):
s = input()
t = input()
temp = s[:]
cnt = 0
strmax = len(t)
ans = 0

for i in t:
	if s.find(i)==-1:
		print("-1")
		exit(0)

while cnt<strmax:
	num = temp.find(t[cnt])
	if num != -1:
		ans+=num+1
		temp = temp[num+1:]
		cnt+=1
	else:
		ans+=len(temp)
		temp = s[:]

print(ans)

Solution (Python):
s = input()
t = input()
max = 10**100
now = t[0]
cnt1 = 0
cnt2 = 0

for i in t:
	if s.find(i)==-1:
		print("-1")
		exit(0)

while True:
	temp = s[:]
	if cnt2 == len(t):
		print(cnt1)
		break
	if max == 0:
		print("-1")
		break
	while True:
		num = temp.find(now)
		if num != -1:
			cnt2+=1
			cnt1+=num+1
			if cnt2 < len(t):
				now = t[cnt2]
			else:
				break
			temp = temp[num+1:]
			continue
		else:
			cnt1+=len(temp)
			break
	max-=1

Solution (Python):
import string
import bisect
S = input()
T = input()
n = len(S)
sa = {_: [] for _ in string.ascii_lowercase}
for i, s in enumerate(S):
    sa[s] += [i]
ans = 0
i = -1
for t in T:
    if sa[t]:
        j = bisect.bisect_left(sa[t], i + 1)
        if j == len(sa[t]):
            ni = sa[t][0] + n
        else:
            ni = sa[t][j]
        ans += ni - i
        i = ni % n
    else:
        print(-1)
        exit()
print(ans)

Solution (Python):
s=input()
t=input()
length=len(s)
exi={chr(97+i): False for i in range(26)}
jump={chr(97+i): [0 for _ in range(2*length)] for i in range(26)}
cru={chr(97+i):0 for i in range(26)}
pointer=0
flag=True
for i,ch in enumerate(s*2):
    exi[ch]=True
    for j in range(cru[ch],i+1):
        jump[ch][j]=1+i-j
    cru[ch]=i+1
for ch in t:
    if exi[ch]:
        pointer+=jump[ch][pointer%length]
    else:
        flag=False
        break
if flag:
    print(pointer)
else:
    print(-1)

Solution (Python):
s=input()
n=len(s)
from collections import Counter
l=Counter()
for i in "abcdefghijklmnopqrstuvwxyz":
    l[i]=[]
for i in range(n):
    l[s[i]].append(i)
t=input()
m=len(t)
ans=0
p=-1
import bisect
for i in range(m):
    c=t[i]
    ll=l[c]
    if ll==[]:
        print(-1)
        exit()
    if ll[-1]<=p:
        ans+=n
        p=ll[0]
        if i==m-1:
            ans+=p+1
    else:
        p=ll[bisect.bisect_right(ll,p)]
        if i==m-1:
            ans+=p+1
print(ans)

Solution (Python):
def main():
    s = [ord(ss) - ord('a') for ss in input()]
    t = [ord(tt) - ord('a') for tt in input()]

    sets = set(s)
    if len([tt for tt in t if tt not in sets]) > 0:
        print(-1)
        return

    ns = len(s)
    table = [[-1] * 26 for _ in range(ns+1)]
    for i in range(ns)[::-1]:
        table[i] = table[i+1][:]
        table[i][s[i]] = i

    cur = -1
    cnt = 1
    for tt in t:
        next_cur = table[cur+1][tt]
        if next_cur == -1:
            next_cur = table[0][tt]
            cnt += 1
        cur = next_cur

    print(ns * (cnt - 1) + cur + 1)


main()

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