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
s = input()
t = input()
d = defaultdict(list)

ls = len(s)
cnt = 0

for ind,i in enumerate(s):
    d[i].append(ind)
        
if not set(s) >= set(t):
    print(-1)
else:
    now = -1
    for i in t:
        arr = d[i]
        y = (now+1) % ls
        ind = bisect_left(arr, y)
    
        if ind >= len(arr):
            now = now+1 + ls - y + arr[0]
            
        else:
            now = now+1 - y + arr[ind]
    print(now+1)

Solution (Python):
from sys import stdin
import bisect
def main():
    
    readline=stdin.readline
    s=readline().strip()
    n=len(s)
    t=readline().strip()

    d=dict()
    for i in range(len(s)):
        if s[i] not in d:
            d[s[i]]=[i]
        else:
            d[s[i]].append(i)
        
    j=-1
    cnt=0
    ans=0
    for i in range(len(t)):
        if t[i] not in d:
            print(-1)
            break
        k=bisect.bisect_right(d[t[i]],j)
        if k<len(d[t[i]]):
            j=d[t[i]][k]
        else:
            cnt+=1
            j=d[t[i]][0]
        ans=j+cnt*n
    else:
        print(ans+1)

if __name__=="__main__":
    main()

Solution (Python):
from bisect import bisect_right

def main():
    S = input()
    T = input()
    lens = len(S)
    s = set(S)
    t = set(T)
    for i in t:
        if not i in s:
            return -2
    S = S + S
    alpha = [[] for i in range(26)]
    for i, v in enumerate(S):
        alpha[ord(v)-ord('a')].append(i)
    ans = 0
    idx = -1
    cnt = 0
    for i in T:
        
        idx = bisect_right(alpha[ord(i)-ord('a')], idx)
        idx = alpha[ord(i)-ord('a')][idx]
        cnt += idx // lens
        idx %= lens
        ans = cnt * lens + idx
    return ans

print(main()+1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from bisect import bisect_left

s = readline().rstrip().decode()
t = readline().rstrip().decode()
al = defaultdict(list)
for i, ss in enumerate(s):
    al[ss].append(i + 1)
cnt = 0
tmp = 0
memo = 0
for tt in t:
    memo = bisect_left(al[tt], tmp + 1)
    if not al[tt]:
        print(-1)
        exit()
    if memo == len(al[tt]):
        memo = 0
        cnt += len(s)
    cnt += al[tt][memo] - tmp
    tmp = al[tt][memo]
print(cnt)

Solution (Python):
import sys
import heapq
import bisect
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

s=list(ns())
t=list(ns())
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}

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

for i in range(len(s)):
  order[d[s[i]]].append(i)
  
now=0
ans=0
rep=0
for i in range(len(t)):
  inds=d[t[i]]
  if(order[inds]==[]):
    print(-1)
    sys.exit(0)
  index=bisect.bisect_left(order[inds],now)
  if(index==len(order[inds])):
    now=order[inds][0]+1
    rep+=1
  else:
    now=order[inds][index]+1


print(rep*len(s)+now)

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

d = defaultdict(list)

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

ans = 0
now = -1
for t in T:
    arr = d[t]
    if len(arr) == 0:
        print(-1)
        exit()
    idx = bisect.bisect_right(arr, now) 
    if idx == len(arr):
        ans += 1
        now = arr[0]
    else:
        now = arr[idx]
print(ans * len(S) + now + 1)

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

d = defaultdict(list)

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

ans = 0
now = -1
for t in T:
    arr = d[t]
    if len(arr) == 0:
        print(-1)
        exit()
    idx = bisect.bisect_right(arr, now)
    if idx == len(arr):
        ans += 1
        now = arr[0]
    else:
        now = arr[idx]
print(ans * len(S) + now + 1)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    ds = s + s
    t = SI()

    z = [0] * 26
    nt = [[] for _ in range(len(ds))]

    for i in range(len(ds),0,-1):
        z[ord(ds[i-1])-ord('a')] = i
        nt[i-1] = copy.copy(z)

    rev = 0
    a = 0
    for x in t:
        x = ord(x) - ord('a')
        a = nt[a][x]
        if a == 0:
            print(-1)
            return
        if a >= len(s):
            a -= len(s)
            rev += 1
    print(rev*len(s)+a)

if __name__ == '__main__':
    main()

Solution (Python):
import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l.append(G.copy())
  G[s[i]] = i
l = l[::-1]  
stG = G.copy()

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    if ind >= len(t):
      cnt += 1
      break 
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind >= len(t):
        break          
    cnt += 1


if cnt != -1:      
  print(cnt*len(s)-(len(s)-(lind+1)))
else:
  print(cnt)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def main():
    s=input()
    t=input()
    s_abc=[]
    for i in range(26):
        s_abc.append([j for j,ss in enumerate(s) if ord(ss)==ord('a')+i])
    cur=-1
    loop=0
    for tt in t:
        tt_num=ord(tt)-ord('a')
        if s_abc[tt_num]==[]:
            print(-1)
            sys.exit()
        next_idx=bisect.bisect(s_abc[tt_num],cur)
        if next_idx==len(s_abc[tt_num]) or s_abc[tt_num][next_idx]<=cur:
            loop+=1
            cur=s_abc[tt_num][0]
        else:
            cur=s_abc[tt_num][next_idx]
    print(len(s)*loop+cur+1)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def main():
    s=input()
    t=input()
    s_abc=[]
    for i in range(26):
        s_abc.append([j for j,ss in enumerate(s) if ord(ss)==ord('a')+i])
    cur=-1
    loop=0
    for tt in t:
        tt_num=ord(tt)-ord('a')
        if s_abc[tt_num]==[]:
            print(-1)
            sys.exit()
        next_idx=bisect.bisect(s_abc[tt_num],cur)
        if next_idx==len(s_abc[tt_num]) or s_abc[tt_num][next_idx]<=cur:
            loop+=1
            cur=s_abc[tt_num][0]
        else:
            cur=s_abc[tt_num][next_idx]
    print(len(s)*loop+cur+1)


if __name__=='__main__':
    main()

Solution (Python):
s = list(input()) 
t = list(input()) 
ls=len(s)

from collections import defaultdict
d = defaultdict(list)

from bisect import bisect_right

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        nex = bisect_right(index, prev)
        if nex == len(index):
            ans += (ls-prev)+index[0]
            prev = index[0]
        else:
            ans+= index[nex]-prev
            prev = index[nex]

print(ans)

Solution (Python):
s = input()
t = input()
ss = s+s
NEXT = [[-1]*(len(s)+1) for _ in range(26)]
cur = [-1]*26
for i in range(len(ss)):
    char = ord(ss[i])-97
    if cur[char] < len(s):
        for j in range(cur[char],min(i,len(s))):
            NEXT[char][j+1] = i
            cur[char] = i
ans = 0
tmp = -1
for i in range(len(t)):
    char = ord(t[i])-97
    if NEXT[char][tmp+1] == -1:
        print(-1)
        exit()
    ans += NEXT[char][tmp+1]-tmp
    tmp = NEXT[char][tmp+1]
    if tmp >= len(s):
        tmp -= len(s)
print(ans)

Solution (Python):
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i]
    else:
        ma[each_s].append(i)
t = input()
t_li = list(t)


repeat_count = 0
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    

    lee = len(s_li)
    
    
    
    bi = bisect.bisect_left(tmp_li, last_index+1)
    
    if bi>= len(tmp_li):
        repeat_count += 1
        min_index = tmp_li[0]
    else:
        min_index = tmp_li[bi]
    
    
    
    
    last_index = min_index
    
    
print(lee*(repeat_count)+last_index+1)

Solution (Python):
import bisect

s=input()
t=input()

i=1
dic=[[] for _ in range(27)]
for ss in s:
    dic[ord(ss) - 97].append(i) 
    i+=1

for index,item in enumerate(dic):
    item.sort()
    dic[index]=item

posi=-1
count=0
for tt in t:
    if dic[ord(tt) - 97]==[]:
        print(-1)
        exit()
    
    r=bisect.bisect_right(dic[ord(tt) - 97],posi)

    flag=0
    if r>=len(dic[ord(tt) - 97]):
        count+=1
        posi=dic[ord(tt) - 97][0]
    else:
        posi=dic[ord(tt) - 97][r]
    
print(count*len(s)+posi)

Solution (Python):
import bisect

s = input()
t = input()

d = dict()

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

ret = 0
cindex = -1

for ch in t:
    if ch not in d:
        print(-1)
        exit()
    else:
        ls = d[ch]
        index = bisect.bisect_right(ls, cindex)
        index = 0 if (index == len(ls)) else index
        if cindex < ls[index]:
            ret += (ls[index] - cindex)
            cindex = ls[index]
        else:
            ret += len(s) + ls[index] - cindex
            cindex = ls[index]

print(ret)

Solution (Python):
import bisect
S=list(input())
T=list(input())

N=len(S)
p=[[] for _ in range(26)]
for i in range(N):
    p[ord(S[i])-97].append(i+1)

res=0
b=0
for t in T:
    k=ord(t)-97
    if len(p[k])==0:
        print(-1)
        exit()
    r=bisect.bisect_right(p[k],b)
    if len(p[k])>r:
        res+=p[k][r]-b
        b=p[k][r]
    else:
        res+=N-b+p[k][0]
        b=p[k][0]

print(res)

Solution (Python):

from collections import defaultdict
from bisect import bisect_right
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    S = readline().strip()
    T = readline().strip()

    S_idx = defaultdict(list)
    for i, s in enumerate(S):
        S_idx[s].append(i)
    
    rep = 0
    last_idx = -1
    for t in T:
        t_idx_list = S_idx[t]
        if t_idx_list:
            t_idx = bisect_right(t_idx_list, last_idx)
            if t_idx < len(t_idx_list):
                last_idx = t_idx_list[t_idx]
            else:
                last_idx = t_idx_list[0]
                rep += 1
        else:
            print(-1)
            exit()
    
    ans = len(S) * rep + last_idx + 1
    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    S = readline().strip()
    T = readline().strip()

    idx_in_S = []
    last_idx = 0
    for t in T:
        t_idx = S.find(t, last_idx) + 1
        if t_idx:
            idx_in_S.append(t_idx)
            last_idx = t_idx
        else:
            t_idx = S.find(t, 0, last_idx) + 1
            if not t_idx:
                print(-1)
                exit()
            else:
                idx_in_S.append(t_idx)
                last_idx = t_idx

    
    rep = 0
    for i in range(len(T) - 1):
        if idx_in_S[i] < idx_in_S[i+1]:
            continue
        else:
            rep += 1

    ans = len(S) * rep + idx_in_S[-1]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
s=input()
t=input()
alp=[[] for _ in range(26)]
flag=1
for i in range(len(s)):
    alp[ord(s[i])-97].append(i)


idx=0
sets=0
i=0
while i<len(t):
    al=ord(t[i])-97
    if len(alp[al])==0:
        flag=0
        break
    else:
        if idx>alp[al][len(alp[al])-1]:
            sets=sets+1
            idx=-1
        else:
            idx=bisect.bisect_left(alp[al],idx)
            idx=alp[al][idx]+1
            i=i+1
    
    
if flag==1:
    print(sets*len(s)+idx)
else:
    print("-1")
"""
l=[0,1,2,3,4,5,6,7,8,9]
for i in range(10):
    idx=bisect.bisect_left(l,i)
    idx2=bisect.bisect_right(l,i)
    print(l[idx],l[idx2])
"""

Solution (Python):
from bisect import bisect_right
s=input()
t=input()
dic={}
n=len(s)
for i in range(n):
	if s[i] in dic:
		dic[s[i]].append(i)
	else:
		dic[s[i]]=[i]
k=-1
r=0
for i in t:
	if i in dic:
		a=bisect_right(dic[i],k)
		if a==len(dic[i]):
			r+=1
			k=dic[i][0]
		else:
			k=dic[i][a]
	else:
		print(-1)
		exit()
print(r*n+k+1)

Solution (Python):
from bisect import bisect_left
s=input()
t=input()
al=[[] for i in range(26)]
for i in range(len(s)):
    al[ord(s[i])-97].append(i)
ans=0
now=-1
ok=True
for i in range(len(t)):
    c=t[i]
    o=ord(c)-97
    b=bisect_left(al[o],now+1)
    if(b==len(al[o])):
        ans+=len(s)-now-1
        now=-1
        b=bisect_left(al[o],now)
        if(b==len(al[o])):
            ok=False
    if ok:
        ans+=al[o][b]-now
        now=al[o][b]
    else:
        print(-1)
        exit()
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
import sys

def solve():
    numChar = 26
    ordA = ord('a')

    Ss = input().rstrip()
    Ts = input().rstrip()

    lenS = len(Ss)
    Ss = [ord(S)-ordA for S in Ss]
    Ts = [ord(T)-ordA for T in Ts]

    setS, setT = set(Ss), set(Ts)
    for T in setT:
        if T not in setS:
            print(-1)
            sys.exit()

    posChs = [[] for _ in range(numChar)]
    for i, S in enumerate(Ss+Ss):
        posChs[S].append(i)

    ans = 0
    i = -1
    for T in Ts:
        iPos = bisect_right(posChs[T], i)
        i2 = posChs[T][iPos]
        ans += i2 - i
        i = i2 % lenS

    print(ans)


solve()

Solution (Python):
import sys

numChar = 26
ordA = ord('a')

Ss = input().rstrip()
Ts = input().rstrip()

setS, setT = set(Ss), set(Ts)
for T in setT:
    if T not in setS:
        print(-1)
        sys.exit()

def getDistNextss(As, numChar):
    lenA = len(As)
    poss = [-1] * numChar
    for i, A in enumerate(As):
        if poss[A] == -1:
            poss[A] = i + lenA
    distNextss = [[0]*(numChar) for _ in range(lenA)]
    for i in reversed(range(lenA)):
        poss[As[i]] = i
        distNextss[i] = [pos-i for pos in poss]
    return distNextss

As = [ord(S)-ordA for S in Ss]
distNextss = getDistNextss(As, numChar)

lenS = len(Ss)
i = 0
for T in Ts:
    T = ord(T) - ordA
    i += distNextss[i%lenS][T]
    i += 1

print(i)

Solution (Python):
import sys

numChar = 26
ordA = ord('a')

Ss = input().rstrip()
Ts = input().rstrip()

setS, setT = set(Ss), set(Ts)
for T in setT:
    if T not in setS:
        print(-1)
        sys.exit()

def getDistNextss(As, numChar):
    lenA = len(As)
    poss = [-1] * numChar
    for i, A in enumerate(As):
        if poss[A] == -1:
            poss[A] = i + lenA
    distNextss = [[0]*(numChar) for _ in range(lenA)]
    for i in reversed(range(lenA)):
        poss[As[i]] = i
        distNextss[i] = [pos-i for pos in poss]
    return distNextss

As = [ord(S)-ordA for S in Ss]
distNextss = getDistNextss(As, numChar)

lenS = len(Ss)
i = 0
for T in Ts:
    T = ord(T) - ordA
    i += distNextss[i%lenS][T]
    i += 1

print(i)

Solution (Python):
from bisect import bisect_left
S = input()
T = input()

set_s = set(S)
set_t = set(T)
len_t = len(T)
if len(set_s & set_t) != len(set_t):
  print(-1)  
else:  
  dic = {c:[] for c in set_s}
  dic_len = {}
  for i,s in enumerate(S):
    dic[s].append(i)
    
  for k in dic:
    dic_len[k] = len(dic[k])
  
  si = 0
  cnt = 0
  for t in T:    
    i = bisect_left(dic[t],si)
    if i == dic_len[t]:
      si = 0
      cnt += 1
      i = bisect_left(dic[t],si)
        
    if dic[t][i] == si:
      si += 1
    else:      
      si = dic[t][i] + 1
              
  print(cnt * len(S) + si)

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

S = input()
T = input()

count = defaultdict(list)
for i, s in enumerate(S):
    count[s] += [i]

idx = 0
cnt = 0
for t in T:
    idxs = count[t]
    if not idxs:
        print(-1)
        exit()
    i = bisect_left(idxs, idx)
    if i < len(idxs):
        idx = idxs[i] + 1
    else:
        idx = idxs[0] + 1
        cnt += 1

ans = cnt * len(S) + idx
print(ans)

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
t = ins()
oa = ord('a')
ls = len(s)
nxt = [[-1]*26 for i in range(ls)]
nx = [-1]*26
for i in range(2*ls-1,-1,-1):
    c = ord(s[i%ls])-oa
    for j in range(26):
        if i<ls and nx[j]>=0:
            nxt[i][j] = nx[j]-i
    nx[c] = i
if DBG:
    for i in range(ls):
        
        print(nxt[i])

prevpos = nxt[ls-1][ord(t[0])-oa]-1
if prevpos<0:
    print(-1)
    exit()
for i in range(1,len(t)):
    c = ord(t[i])-oa
    nx = nxt[prevpos%ls][c]
    if nx<0:
        print(-1)
        exit()
    prevpos += nx
    
print(prevpos+1)

Solution (Python):
s=input()
t=input()
cnt=0
mod=-1
tmp_s=""
for cha in t:
    if cha not in s:
        print(-1)
        exit()
    elif cha in tmp_s:
        idx=tmp_s.find(cha)
        mod+=idx+1   
    else:
        idx=s.find(cha)
        if idx<=mod:
            cnt+=1  
        mod=idx
    
    if mod==len(s)-1:
        tmp_s=" "
    else:
        tmp_s=s[mod+1:]

print(len(s)*cnt+mod+1)

Solution (Python):

from collections import defaultdict
import bisect

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

ans=0
pos=-1

d = defaultdict(list)
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i)
        
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i+n)
        
for v in t:
    l = d[v]
    ind = bisect.bisect_right(l, pos)
    if l:
        ans += l[ind]-pos
        if l[ind]<n:
            pos = l[ind]
        else:
            pos = l[ind] - n
    else:
        ans = -1
        break
        
print(ans)

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

d = {char:[] for char in 'abcdefghijklmnopqrstuvwxyz'}
for i in range(len(s)):
    d[s[i]].append(i)

cnt = 0
index = 0
for char in t:
    if not d[char]:
        print(-1)
        sys.exit()
    i = bisect_left(d[char], index)
    if i == len(d[char]):
        cnt += 1
        index = d[char][0]
    else:
        index = d[char][i]
    index += 1

ans = cnt * len(s) + index
print(ans)

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

d = {char:[] for char in 'abcdefghijklmnopqrstuvwxyz'}
for i in range(len(s)):
    d[s[i]].append(i)

cnt = 0
index = 0
for char in t:
    if not d[char]:
        print(-1)
        sys.exit()
    i = bisect_left(d[char], index)
    if i == len(d[char]):
        cnt += 1
        index = d[char][0]
    else:
        index = d[char][i]
    index += 1

ans = cnt * len(s) + index
print(ans)

Solution (Python):
def sn(a):
    return ord(a) - ord("a")

def isok(idx,prev):
    return prev>=idx+n*loops


def bisect(ls,val): 
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok 

S = input()
T = input()
lt = list(T)
ls = list(S)
set_s = set(list(S))
set_t = set(lt)
if not set_t <= set_s:
    print(-1)
    exit()
cnts = [[] for i in range(26)]
cnts_idx = [0]*26
for i,w in enumerate(ls):
    cnts[sn(w)].append(i)

loops = 0
n = len(S)
prev = -1
for t in lt:
    idx = bisect(cnts[sn(t)],prev)+1
    if idx==len(cnts[sn(t)]):
        loops+=1
        idx = 0
    prev = cnts[sn(t)][idx] + loops*n

print(prev+1)

Solution (Python):
import bisect
s = list(input())
t = list(input())
n = len(s)
m = len(t)
alphabet = [[] for _ in range(26)]
for i in range(n):
  alphabet[ord(s[i])-ord('a')] += [i] 
loop = 0
pre = -1
for i in range(m):
  c = ord(t[i]) - ord('a')
  if len(alphabet[c]) == 0:
    print(-1)
    exit()
  idx = bisect.bisect_left(alphabet[c], pre+1)
  if idx == len(alphabet[c]):
    loop += 1
    pre = alphabet[c][0]
  else:
    pre = alphabet[c][idx]

print(pre + loop * n + 1)

Solution (Python):
import sys
input = sys.stdin.readline
s = input().strip()
t = input().strip()
chk = [[] for i in range(26)]
ma = [0]*26
ex = [False]*26
for i,si in enumerate(s):
  num = ord(si)-97
  chk[num].append(i+1)
  if not ex[num]:
    ex[num] = True
  ma[num] = i+1
  
import math,bisect
now = 0
ans = 0
l = len(s)
for i,ti in enumerate(t):
  ans += 1
  j = i+1
  n = ord(ti)-97
  if not ex[n]:
    ans = -1
    break
  if ans > now*l + ma[n]:
    now = math.ceil((ans-ma[n])/l)
  ind = bisect.bisect_left(chk[n],ans-now*l)
  ans = chk[n][ind] + now*l
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = input()
t = input()

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

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

from bisect import bisect_left as bl
'''index  =  bl(list,num)'''
nagasa = len(s)
ans = 0
ima = 0
mae = 0
for i in range(len(t)):
    tmp = bl(A[ord(t[i]) -ord("a")],ima+1)
    if tmp == len(A[ord(t[i]) -ord("a")]):
        ans += nagasa - ima
        ima = 0
        tmp = bl(A[ord(t[i]) -ord("a")],ima+1)
        if tmp == len(A[ord(t[i]) -ord("a")]):
            print(-1)
            exit()
    mae = ima
    ima = A[ord(t[i]) -ord("a")][tmp]
    ans += ima - mae
print(ans)

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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    T = input()
    N = len(S)
    idx = defaultdict(list)
    for i, s in enumerate(S):
        idx[s].append(i)

    
    x = -1
    n_loop = 0
    for t in T:
        arr = idx[t]
        if len(arr) == 0:
            print(-1)
            return

        x += 1
        i = bisect.bisect_left(arr, x)
        if i < len(arr):
            x = arr[i]
        else:
            n_loop += 1
            x = arr[0]

    print(n_loop * N + x + 1)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
	s=input()
	t=input()
	n=len(s)
	now=-1
	ans=1
	if not set(t)<=set(s):
		print(-1)
		exit()
	for x in t:
		now=s.find(x,now+1)
		if now==-1:
			ans+=n
			now=s.find(x)
	print(ans+now)
if __name__ == '__main__':
	main()

Solution (Python):
s=input()
t=input()
s*=2
next=[[-1]*26 for _ in range(len(s))]
alph=[[]for _ in range(26)]
for i in range(len(s)):
	alph[ord(s[i])-ord("a")].append(i)
from bisect import bisect_right
for i in range(len(s)//2):
	for j in range(26):
		if len(alph[j])>bisect_right(alph[j],i):
			next[i][j]=alph[j][bisect_right(alph[j],i)]
ans=1
now=len(s)//2-1
for x in t:
	r=ord(x)-ord("a")
	now=next[now][r]
	if now==-1:
		print(-1)
		exit()
	if now>=len(s)//2:
		ans+=len(s)//2
		now-=len(s)//2
print(ans+now-len(s)//2)

Solution (Python):
s=input()
t=input()
from bisect import bisect
points=[[]for i in range(26)]
a=ord("a")
for i,c in enumerate(s):
    points[ord(c)-a].append(i)
for p in points:
    p.append(10**9)

n=len(s)
idx=-1
stage=0
for c in t:
    c=ord(c)-a
    p=points[c]
    if len(p)==1:
        stage=0
        idx=-2
        break
    idx = p[bisect(p,idx)]
    if idx>10**6:
        idx=p[0]
        stage+=1
print(stage*n+idx+1)

Solution (Python):


import sys














from bisect import bisect_left, bisect_right 




def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    t = input()

    
    set_s = set(s)
    for char_t in t:
        if char_t not in set_s:
            print(-1)
            exit()

    
    
    s_table = [[] for _ in range(ord('z') - ord('a') + 1)]
    for i, s_char in enumerate(s):
        s_table[ord(s_char) - ord('a')].append(i)
    
    
    loop_count = 0
    prev = -1
    for t_char in t:
        candidate = s_table[ord(t_char) - ord('a')]
        j = bisect_left(candidate, prev+1)    
        if j == len(candidate):
            loop_count += 1
            prev = candidate[0]
        else:
            prev = candidate[j]
    print(prev + loop_count * len(s) + 1)


if __name__ == "__main__":
    main()

    """
    解説
    俺の二分探索の方針以外にも「ある index 以降で次に char(a-z) が出現する index を O(alpha)*O(|s|) で求めておく」と言った方法がある。
    こちらは O(|s|) + O(alpha) * O(|s|) + O(|t|)
    二分探は O(|s|) + O(lg|s|) * O(|t|)
    O(alpha) = 26, O(lg|10**5|) = 16, O(|s|) = O(|t|) より今回最悪計算量に変わりはない

    s を二つ連結した文字列を用意して調べると楽らしい。確かに。(必ず探索場所がヒットするので)
    """

Solution (Python):


import sys














from bisect import bisect_left, bisect_right 




def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    t = input()

    
    set_s = set(s)
    for char_t in t:
        if char_t not in set_s:
            print(-1)
            exit()

    
    
    s_table = [[] for _ in range(ord('z') - ord('a') + 1)]
    for i, s_char in enumerate(s):
        s_table[ord(s_char) - ord('a')].append(i)
    
    
    loop_count = 0
    prev = -1
    for t_char in t:
        candidate = s_table[ord(t_char) - ord('a')]
        j = bisect_left(candidate, prev+1)    
        if j == len(candidate):
            loop_count += 1
            prev = candidate[0]
        else:
            prev = candidate[j]
    print(prev + loop_count * len(s) + 1)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    

    s = input().rstrip()
    ls = len(s)
    t = input().rstrip()
    lt = len(t)
    alphabet = 'abcdefghijklmnopqrstuvwxyz' 
    moji = [[] for _ in range(26)]
    for i in range(ls):
        idx = alphabet.index(s[i])
        moji[idx].append(i+1)
    
    cnt = 0
    res = 0
    while cnt < lt:
        for i in range(cnt, lt):
            idx = alphabet.index(t[i])
            if not moji[idx]:
                print(-1)
                exit()
            if i == cnt:
                now = moji[idx][0] + 1
            else:
                nex = bisect_left(moji[idx], now)
                if nex == len(moji[idx]):
                    res += ls
                    cnt = i
                    break
                now = moji[idx][nex] + 1
        else:
            res += now - 1
            break
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    

    s = input().rstrip()
    ls = len(s)
    t = input().rstrip()
    lt = len(t)
    alphabet = 'abcdefghijklmnopqrstuvwxyz' 
    dic = {}
    for i in range(26):
        dic[alphabet[i]] = i
    moji = [[] for _ in range(26)]
    for i in range(ls):
        moji[dic[s[i]]].append(i+1)
    
    cnt = 0
    res = 0
    while cnt < lt:
        for i in range(cnt, lt):
            if not moji[dic[t[i]]]:
                print(-1)
                exit()
            if i == cnt:
                now = moji[dic[t[i]]][0] + 1
            else:
                nex = bisect_left(moji[dic[t[i]]], now)
                if nex == len(moji[dic[t[i]]]):
                    res += ls
                    cnt = i
                    break
                now = moji[dic[t[i]]][nex] + 1
        else:
            res += now - 1
            break
    print(res)

if __name__ == '__main__':
    main()