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 collections import defaultdict
import bisect
def input(): return sys.stdin.readline().rstrip()


def main():
    s = list(input())
    t = list(input())
    dic = defaultdict(list)
    for index, string in enumerate(s):
        dic[string].append(index)
    cycle = 0
    ind = -1
    for string in t:
        if dic[string] == []:
            print(-1)
            exit()
        elif dic[string][-1] <= ind:
            cycle += 1
            ind = dic[string][0]
        else:  
            ind = dic[string][bisect.bisect_right(
                dic[string], ind)]  
    print(cycle*len(s)+ind+1)


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()
set_ = set()
for i in s:
    set_.add(i)
for i in t:
    if i not in set_:print(-1);exit()
dic = [[0]*26 for _ in range(len(s))]
tmp = [[] for _ in range(26)]
for i in range(len(s)):
    tmp[ord(s[i])-ord('a')].append(i)
import bisect
for i in range(len(s)):
    for nxt in set_:
        idx = bisect.bisect_right(tmp[ord(nxt)-ord('a')],i)

        if idx==len(tmp[ord(nxt)-ord('a')]):
            dic[i][ord(nxt)-ord('a')] = tmp[ord(nxt)-ord('a')][0] + len(s)-i
            
        else:
            dic[i][ord(nxt)-ord('a')] = tmp[ord(nxt)-ord('a')][idx]-i
cnt = tmp[ord(t[0])-ord('a')][0]
for i in range(1,len(t)):
    cnt += dic[cnt%len(s)][ord(t[i])-ord('a')]
print(cnt+1)

Solution (Python):
import sys
from collections import defaultdict
dic = defaultdict(list)
s = input()
t = input()
n = len(s)
for i in range(n):
    dic[s[i]].append(i+1)



for i in t:
    if dic[i]==[]:
        print(-1)
        sys.exit()
        
ans = dic[t[0]][0]

if len(t)==1:
    print(ans)
    sys.exit()

count=0

for i in range(1, len(t)):
    
    if ans >= dic[t[i]][-1]:
        count += 1
        ans = dic[t[i]][0]
    elif ans < dic[t[i]][0]:
        ans = dic[t[i]][0]
    else:
        sm = 0
        la = len(dic[t[i]])-1
        while sm+1<la:
            mi = (sm + la)//2
            if ans >= dic[t[i]][mi]:
                sm = mi
            else:
                la = mi
        ans = dic[t[i]][la]

print(ans+count*n)

Solution (Python):
key= list('abcdefghijklmnopqrstuvwxyz')
value=[[] for i in range(26)]
d = dict(zip(key,value))
import bisect    
s = input()
s = list(s)
n = len(s)
ans = 0
for i in range(len(s)):
    d[s[i]].append(i+1)
st = set(s)
t = input()
t = list(t)
b = 0
for i in range(len(t)):
    if t[i] in st:
        p = bisect.bisect(d[t[i]],b) 
        if p < len(d[t[i]]):
            b = d[t[i]][p]
        else:
            b = d[t[i]][0]
            ans += n
    else:
        ans = -1
        break
if ans != -1:
    ans += b
print(ans)

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


def main():
    s = input()
    t = input()
    len_s = len(s)
    s_all = {s: [] for s in ascii_lowercase}
    for i in range(len_s):
        s_all[s[i]].append(i + 1)
    ans = 0
    if any(s_all[tt] == [] for tt in t):
        ans = -1
    else:
        s_ind = 1
        for ss in ascii_lowercase:
            s_all[ss].sort()
        for i in range(len(t)):
            next_ind = bisect_left(s_all[t[i]], s_ind)
            if next_ind == len(s_all[t[i]]):
                ans += len_s - s_ind + 1
                ans += s_all[t[i]][0]
                s_ind = s_all[t[i]][0] + 1
            else:
                ans += s_all[t[i]][next_ind] - s_ind + 1
                s_ind = s_all[t[i]][next_ind] + 1
    print(ans)


if __name__ == '__main__':
    main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


import bisect
from collections import defaultdict

def main():
	s=RD()
	t=RD()
	d=defaultdict(list)

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

	now=-1
	cnt=0

	for tt in t:
		if d[tt]==[]:
			print(-1)
			exit()
		else:
			i=bisect.bisect_right(d[tt],now)
			if len(d[tt])==i:
				cnt+=1
				now=d[tt][0]
			else:
				now=d[tt][i]
		
	print(len(s)*cnt+now+1)

























if __name__ == "__main__":
	main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


import bisect
from collections import defaultdict

def main():
	s=RD()
	t=RD()
	d=defaultdict(list)

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

	now=-1
	cnt=0

	for tt in t:
		if d[tt]==[]:
			print(-1)
			exit()
		else:
			i=bisect.bisect_right(d[tt],now)
			if len(d[tt])==i:
				cnt+=1
				now=d[tt][0]
			else:
				now=d[tt][i]
		
	print(len(s)*cnt+now+1)

























if __name__ == "__main__":
	main()

Solution (Python):
from bisect import bisect_left


def solve():
    S = input()
    T = input()
    if not set(T) <= set(S):
        return -1

    pos = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, c in enumerate(S):
        pos[c].append(i)
    ans = 0
    cur_pos = 0
    for t in T:
        nxt_idx = bisect_left(pos[t], cur_pos)
        if nxt_idx == len(pos[t]):
            ans += len(S)
            cur_pos = 0
            nxt_idx = bisect_left(pos[t], cur_pos)
            cur_pos = pos[t][nxt_idx] + 1
        else:
            cur_pos = pos[t][nxt_idx] + 1

    return ans + cur_pos


print(solve())

Solution (Python):
import bisect

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

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

for i in range(len(s)):
    pos[ord(s[i]) - ord('a')].append(i)

ans = 0
now = -1
for i in range(len(t)):
    c = ord(t[i]) - ord('a')
    j = bisect.bisect_right(pos[c], now)

    if j == len(pos[c]):
        print(-1)
        exit()
    now = pos[c][j]

    if now >= n:
        now -= n
        ans += n
print(ans + now + 1)

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

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

n = len(s)
q = 0
r = -1
import bisect
for c in t:
    j = ord(c)-ord('a')
    if len(X[j]) == 0:
        print(-1)
        exit()
    idx = bisect.bisect_right(X[j], r)
    
    if idx == len(X[j]):
        q += 1
        r = X[j][0]
    else:
        r = X[j][idx]
    
ans = q*n + r+1
print(ans)

Solution (Python):
import bisect
s = input()
t = input()
u = s
while len(s) <= len(t):
    s += u
p = [[] for k in range(26)]
for k in range(len(s)):
    p[ord(s[k])-97].append(k)
for e in p:
    e.append(10**6)
ans = 0
now = -1
for e in t:

    if len(p[ord(e)-97]) == 1:
        print(-1)
        exit(0)
    q = p[ord(e)-97][bisect.bisect_right(p[ord(e)-97],now)]
    if q == 10**6:
        ans += len(s)-now+p[ord(e)-97][0]
        now = p[ord(e)-97][0]
    else:
        ans += q-now
        now = q
print(ans)

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

from collections import defaultdict

nx = [defaultdict(lambda: -1) for i in range(len(S)+1)]
lastpos = defaultdict(lambda: 0)

SS = S+S
for i,c in enumerate(SS[::-1]):
    i = len(SS)-1-i
    if i < len(S):
        for k,v in lastpos.items():
            nx[i+1][k] = v-i
    lastpos[c] = i
for k,v in lastpos.items():
    nx[0][k] = v+1

ans = 0
for c in T:
    if nx[ans%len(S)][c] == -1:
        print(-1)
        exit()
    ans += nx[ans%len(S)][c]
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right

s = input()
t = input()

alp_d = {chr(ord('a') + i): [] for i in range(26)}
for i,si in enumerate(s):
    alp_d[si].append(i)



curr_i = -1
loop = 0
for ti in t:
    
    if not alp_d[ti]:
        print(-1)
        exit()
    
    ind = bisect_right(alp_d[ti], curr_i)
    ind = ind if 0 <= ind < len(alp_d[ti]) else None
    detected_i = alp_d[ti][ind] if ind is not None else None
    
    if detected_i is not None:
        curr_i = detected_i
    else:
        loop += 1
        curr_i = min(alp_d[ti])

ans = loop*(len(s)) + curr_i+1
print(ans)

Solution (Python):
from bisect import *
def alph_to_num(s):
  return ord(s)-ord('a')
def solve():
  ans = 0
  S = input()
  T = input()
  lis = [[] for _ in range(26)]
  for i,s in enumerate(S):
    lis[alph_to_num(s)].append(i)
  ind = -1
  for t in T:
    n = alph_to_num(t)
    if not len(lis[n]):
      return -1
    if ind>=lis[n][-1]:
      ans += len(S)
      ind = lis[n][0]
    else:
      ind = lis[n][bisect_right(lis[n],ind)]
  ans += ind+1
  return ans
print(solve())

Solution (Python):

from bisect import bisect_left
from collections import defaultdict
import sys
def main(S, T):
    D = defaultdict(list)
    for i, s in enumerate(S):
        D[s].append(i + 1)
    cycle = 0
    idx = 0
    N = len(S)
    for t in T:
        if not D[t]:
            return -1
        i = bisect_left(D[t], idx + 1)
        if i >= len(D[t]):
            cycle += 1
            idx = D[t][0]
        else:
            idx = D[t][i]
    return cycle * N + idx

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    t = input().rstrip()
    ans = main(s, t)
    print(ans)

Solution (Python):
from bisect import *
S=input()
T=input()
N=len(S)
M=len(T)
O=ord('a')
X=[[0]*26 for i in range(N+1)]
Y=[[] for i in range(26)]
for i in range(N):
  Y[ord(S[i])-O].append(i)
for i in range(N):
  Y[ord(S[i])-O].append(N+i)
for i in range(M):
  if len(Y[ord(T[i])-O])==0:
    print(-1)
    exit()
for i in range(-1,N):
  for j in range(26):
    if len(Y[j]):
      X[i][j]=Y[j][bisect_right(Y[j],i)]
P=0
Z=-1
for i in range(M):
  P+=X[Z][ord(T[i])-O]-Z
  Z=X[Z][ord(T[i])-O]
  if Z>=N:
    Z-=N
print(P)

Solution (Python):

import sys,os
from collections import defaultdict
from bisect import bisect_left
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    s = input()
    t = input()
    
    alphabets = defaultdict(list)
    for i,c in enumerate(s):
        alphabets[c].append(i)
    
    period = 0
    
    looking = -1
    
    alphabet_index = defaultdict(int)
    for i,c in enumerate(t):
        index = bisect_left(alphabets[c],looking+1, alphabet_index[c])
        
        if index == len(alphabets[c]):
            
            if len(alphabets[c]) == 0:
                print(-1)
                return
            
            
            period += 1
            alphabet_index = defaultdict(int)
            looking = alphabets[c][0]

        else:
            looking = alphabets[c][index]

        alphabet_index[c] += 1
    print(period * len(s) + looking + 1)






    

if __name__ == '__main__':
    main()

Solution (Python):

from bisect import bisect_right

s = input()
N = len(s)
si = [[] for _ in range(26)]
for i in range(N):
    si[ord(s[i])-ord('a')].append(i+1)

ans = 0
t = input()
M = len(t)
for j in range(M):
    ti = si[ord(t[j])-ord('a')]
    if len(ti)==0:
        print(-1)
        exit()
    d = bisect_right(ti,ans%N)
    if d == len(ti):
        ans += ti[0]+N-ans%N
    else:
        ans += ti[d]-ans%N
print(ans)

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

alpha2num = lambda c: ord(c) - ord('a')

S2 = [[] for i in range(26)]
for i in range(len(s)):
  S2[alpha2num(s[i])].append(i)
  

time = 0
place = -1
for i in range(len(t)):
  now = alpha2num(t[i])
  if S2[now] == []:
    print(-1)
    quit()
  else:
    index = bisect.bisect_left(S2[now], place)
    
    
    

    
    if index == len(S2[now]):
      place = S2[now][0]
      time += 1
    else:  
      if S2[now][index] == place:
        index += 1
        if index == len(S2[now]):
          place = S2[now][0]
          time += 1
        else:
          place = S2[now][index]
      else:  
        place = S2[now][index]
  
    
    
ans = len(s) * time + place + 1
print(ans)

Solution (Python):
import bisect

s,t = input(),input()
n,nx,r = len(s),{},0

for i,c in enumerate(s+s):
	if nx.get(c) is None:
		nx[c] = []
	nx[c].append(i+1)

for c in t:
	l = nx.get(c)
	if l is None:
		print(-1)
		exit()
	r += l[bisect.bisect(l,r%n)]-r%n
print(r)

Solution (Python):
from bisect import bisect

s,t = input(),input()
n,x,nx,r = len(s),s+s,{},0

for i,c in enumerate(x):
	if nx.get(c) is None:
		nx[c] = []
	nx[c].append(i+1)

for c in t:
	l = nx.get(c)
	if l is None:
		print(-1)
		exit()
	r += l[bisect(l,r%n)]-r%n
print(r)

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

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

prev = 10**10
cycle = 0
for i,c in enumerate(t):
  if c not in counter:
    print(-1)
    exit()

  idx = counter[c]
  found = bisect.bisect_right(idx, prev)

  if found >= len(idx):
    cycle += 1
    prev = idx[0]
  else:
    prev = idx[found]

print( (cycle-1)*len(s) + prev+1 )

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq


import bisect
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
s=list(input())
n=len(s)
t=input()
m=len(t)
dic={}
ans=0
for i in range(len(s)):
    if s[i] not in dic:
        dic[s[i]]=[i]
    else:
        dic[s[i]].append(i)
b=-1
for i in range(m):
    if t[i] not in dic:
        print(-1)
        exit()
    res=dic[t[i]]
    if res[-1]<=b:
        ans+=res[0]+1+(n-b-1)
        b=res[0]
    else:
        idx=bisect.bisect_right(res,b)
        ans+=res[idx]-b
        b=res[idx]
print(ans)

Solution (Python):
from collections import defaultdict

f = defaultdict(list)
d = {}


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

len_s = len(s)

for i in range(len_s):
    f[s[i]].append(i)

next_char = [[0] * len_s for _ in range(len(f))]

j = 0
for k, v in f.items():
    d[k] = j
    l = 0
    for i in range(len_s):
        if v[l] == i:
            l += 1
            if l == len(v):
                l = 0
        next_char[j][i] = v[l]
    j += 1

m = 0

for i in range(len(t)):
    x = t[i]
    if i == 0 and t[i] == s[i]:
        continue 
    if d.get(x) == None:
        m = -2
        break
    else:
        j = d[x]
        r = m % len_s
        n = next_char[j][r]
        if r >= n:
            m += len_s - (r-n)
        else:
            m += n - r

print(m+1)

Solution (Python):
from bisect import bisect_right
s = input()
t = input()
n = len(s)

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

for tt in set(t):
    if not position[ord(tt)-ord("a")]:
        print(-1)
        exit(0)

count = 0
idx = -1
for tt in t:
    t_i = ord(tt)-ord("a")
    pos = bisect_right(position[t_i], idx)
    if pos == len(position[t_i]):
        idx = position[t_i][0]
        count += 1
    else:
        idx = position[t_i][pos]

print(count*n+idx+1)

Solution (Python):
from bisect import bisect
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
alp = []

for i in range(26):
  array = []
  now = chr(ord('a') + i)
  for j in range(lenS):
    if s[j] == now:
      array.append(j+1)
  alp.append(array)

count,now = 0,0

for i in range(lenT):
  j = ord(t[i])-ord('a')
  if alp[j]:
    next = bisect(alp[j],now)
    if next == len(alp[j]):
      count += 1
      now = alp[j][0]
    else:
      now = alp[j][next]
  else:
    print(-1)
    exit()

ans = count*lenS+now

print(ans)

Solution (Python):
from bisect import bisect
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
alp = []

for i in range(26):
  array = []
  now = chr(ord('a') + i)
  for j in range(lenS):
    if s[j] == now:
      array.append(j)
  alp.append(array)

count,now = 0,-1

for i in range(lenT):
  j = ord(t[i])-ord('a')
  if alp[j]:
    next = bisect(alp[j],now)
    if next == len(alp[j]):
      count += 1
      now = alp[j][0]
    else:
      now = alp[j][next]
  else:
    print(-1)
    exit()

ans = count*lenS+now+1

print(ans)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]

def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
s=SI()
t=SI()
a=len(s)
b=len(t)

alphasm=[chr(i) for i in range(97, 97+26)]
alphadic={}
for i in range(26):
    alphadic[alphasm[i]]=i
strlis=[[] for i in range(26)]


for i in range(a):
    strlis[alphadic[s[i]]].append(i)

rd=0
pos=-1

i=0
while i<b:
    if len(strlis[alphadic[t[i]]])==0:
        print(-1)
        sys.exit()
        
    if pos==-1:
        pos=strlis[alphadic[t[i]]][0]
        i+=1
        
    elif strlis[alphadic[t[i]]][-1]<=pos:
        rd+=1
        pos=-1
        
    else:
        pos=strlis[alphadic[t[i]]][bisect_right(strlis[alphadic[t[i]]],pos)]
        i+=1
        
    
print(rd*a+pos+1)

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

char_dic = dict()
for i in range(len(s)):
    if not s[i] in char_dic:
        char_dic[s[i]] = []
    char_dic[s[i]].append(i)

m = len(s)
i = 0
last_idx = -1
counter = dict()
for c in t:
    if not c in char_dic:
        print(-1)
        quit()
    j = bisect_right(char_dic[c], last_idx)
    if j == len(char_dic[c]):
        i += 1
        last_idx = char_dic[c][0]
    else:
        last_idx = char_dic[c][j]
print(i * len(s) + last_idx + 1)

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

S = input().rstrip()
T = input().rstrip()
L = len(S)

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


s0 = -1
cnt = 0
for t in T:
    if not dic[t]:
        print(-1)
        exit()
    p = bisect_right(dic[t],s0)
    if p >= len(dic[t]):
        cnt += 1
        s0 = min(dic[t])
    else:
        s0 = dic[t][p]

print(L*cnt+s0 +1)

Solution (Python):
def find(base, indexes):
    n = len(indexes)
    ng = -1
    ok = n

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if indexes[mid] > base:
            ok = mid
        else:
            ng = mid

    return indexes[0] if ok == n else indexes[ok]


s = input()
t = input()

s_set = set(s)
t_set = set(t)

if t_set.issubset(s_set) is False:
    print(-1)
    exit(0)

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

for i in range(len(s)):
    c = s[i]
    idx = ord(c) - ord("a")
    s_indxes[idx].append(i)

base = -1
loop = 0
for i in range(len(t)):
    c = t[i]
    idx = ord(c) - ord("a")
    n_base = find(base, s_indxes[idx])

    if n_base <= base:
        loop += 1

    base = n_base

print(loop * len(s) + base + 1)

Solution (Python):

from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

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

i = -1
cnt = 0
flag = False
for t in T:
    if t not in ctr:
        flag = True
        break

    j = bisect_right(ctr[t], i)
    if j == len(ctr[t]):
        idx = ctr[t][0]
    else:
        idx = ctr[t][j]

    if i >= idx:
        cnt += 1
    i = idx

if flag:
    print(-1)
else:
    print(cnt * len(S) + i + 1)

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    s = input()
    ls = len(s)
    t = input()
    if t[0] in s:
        idx = s.find(t[0])
    else:
        print(-1)
        exit()
    for i in t[1::]:
        nt = s.find(i,idx%ls+1)
        ntl = s.find(i)
        if ntl == -1:
            print(-1)
            exit()
        elif nt == -1:
            idx = (idx//ls)*ls+ls+ntl
        else:
            idx = (idx//ls)*ls+nt
    print(idx+1)
    return None

if __name__ == '__main__':
    main()

Solution (Python):
"""
Tの文字にたいして、Sのインデックスをリストで持たせる
Tの頭から順繰りにたし上げていく（Loop数を数えること）
自分よりも大きい要素があれば、それを使うし、
なければ最も小さい要素を使いつつ、Loop数をCountUp
bisect_left()かな？

0123456
contest

01234567
sentence

s=[5]   -> 5  (6moji)
e=[4]   -> 7*1+4 (12moji)
n=[2]   -> 7*2+2 = 16
t=[3,6] -> 7*2+3 = 17
e=[4]   -> 7*2+4 = 18
n=[2]   -> 7*3+2 = 23
c=[0]   -> 7*4+0 = 28
e=[4]   -> 7*4+4 = 32 ( 33moji)
"""

from bisect import bisect_right, bisect_left
S = input()
T = input()

def calc(ch):
  return ord(ch) - ord('a')


LST = [[] for _ in range(26)]
for t in T:
  nt = calc(t)
  if len(LST[nt]) > 0:
    continue
  for i in range(len(S)):
    if t == S[i]:
      LST[nt].append(i)
  if len(LST[nt]) == 0:
    print(-1)
    exit(0)
    
NS = len(S)

NofLoop = 0
now = 0
for i in range(len(T)):
  t = T[i]
  nt = calc(t)
  rel_now = now - NofLoop * NS
  if rel_now < LST[nt][0] :
    
    now = NofLoop * NS + LST[nt][0] + 1
  elif LST[nt][-1] < rel_now :
    
    NofLoop += 1
    now = NofLoop * NS + LST[nt][0] + 1
  else:
    idx = bisect_left(LST[nt], rel_now)
    
    now = NofLoop * NS + LST[nt][idx] + 1
    
print(now)

Solution (Python):
def main():
    import sys
    import copy
    from bisect import bisect_right
    from collections import defaultdict
    input = sys.stdin.readline
    s, t = input().strip(), input().strip()
    lens = len(s)
    index_list = defaultdict(list)
    leng = defaultdict(int)
    for i, ss in enumerate(s):
        index_list[ss].append(i)

    for s, i in index_list.items():
        if i:
            leng[s] = len(index_list[s])

    prev = -1
    ans = 0
    for tt in t:
        if tt not in leng:
            print(-1)
            return False
        p = bisect_right(index_list[tt], prev)
        
        if p < leng[tt]:
            prev = index_list[tt][p]
        else:
            prev = index_list[tt][0]
            ans += lens

    print(ans+prev+1)

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
S = input()
T = input()
D = dict()
for i in range(len(T)):
    if T[i] in D:
        continue
    else:
        D[T[i]] = []
for i in range(len(S)):
    if S[i] in D:
        D[S[i]].append(i)

if len(set(T)-set(S))>0:
    print(-1)
else:
    r = -1
    cnt = 0
    for i in range(len(T)):
        m = bisect.bisect_right(D[T[i]], r)
        if m < len(D[T[i]]):
            r = D[T[i]][m]
        else:
            r = D[T[i]][0]
            cnt += 1
    print(len(S)*cnt+r+1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



s = input()
t = input()

if not set(s) >= set(t):
	print(-1)
	exit()

dic = defaultdict(list)
for i, char in enumerate(s, 1):
	dic[char].append(i)

loop = 0
index = -1
for i in range(len(t)):
	idx = bisect(dic[t[i]], index)
	if idx < len(dic[t[i]]):
		index = dic[t[i]][idx]
	else:
		idx = dic[t[i]][0]
		index = idx
		loop += 1

print(len(s)*loop+index)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



s = input()
t = input()

t_kinds = set(t)
dic = defaultdict(list)

for i, char in enumerate(s, 1):
	if char in t_kinds:
		dic[char].append(i)

if len(dic.keys()) < len(t_kinds):
	print(-1)
	exit()

dic_lim = defaultdict(int)
for key in dic.keys():
	dic_lim[key] = len(dic[key])

tmp = -1
ans = 0
loop_cnt = 0
for x in t:
	idx = bisect(dic[x], tmp)
	if idx == dic_lim[x]:
		tmp = dic[x][0]
		loop_cnt += 1
	else:
		tmp = dic[x][idx]
print(len(s)*loop_cnt + tmp)

Solution (Python):
INF = 1000000007
s = list(input())
t = list(input())
lis = [[0] for i in range(26)]
for i in range(len(s)):
    lis[ord(s[i])-ord('a')].append(i+1)

for i in range(26):
    lis[i].append(INF)


def binary_search(val,lis):
    ng = 0
    ok = len(lis)-1
    while abs(ng-ok) > 1:
        mid = (ok+ng)//2
        if lis[mid] > val:
            ok = mid
        else:
            ng = mid
        
    return lis[ok]


ans = 0
p = 0
for i in t:
    j = ord(i) - ord('a')
    if len(lis[j]) == 2:
        print(-1)
        exit()
    val = binary_search(p,lis[j])
    p = val
    if val == INF:
        ans += len(s)
        p = binary_search(0,lis[j])
    
print(ans + p)

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    s = list(input())
    t = collections.deque(list(input()))

    jump = [[0] * 26 for _ in range(len(s) + 1)]

    for i in range(len(s) - 1, -1, -1):
        jump[i] = jump[i + 1].copy()
        jump[i][ord(s[i]) - 97] = i + 1

    ans = 0
    point = 0
    while len(t) > 0:
        tmp = t.popleft()
        character = ord(tmp) - 97
        if jump[point][character] == 0 and point == 0:
            print(-1)
            exit(0)
        point = jump[point][character]
        if point == 0:
            t.appendleft(tmp)
            ans += 1

    print(ans * len(s) + point)


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
s=input()
t=input()
dic={}
for i in range(len(t)):
  if t[i] in dic:
    continue
  if t[i] not in dic:
    dic[t[i]]=[]
for i in range(len(s)):
  if s[i] in dic:
    dic[s[i]].append(i)
for k,v in dic.items():
  if v==[]:
    print(-1)
    exit()
n=-1
k=0

for i in range(len(t)):
  l=bisect.bisect_right(dic[t[i]],n)
  if l<len(dic[t[i]]):
    n=dic[t[i]][l]
  else:
    n=dic[t[i]][0]
    k+=1
print(len(s)*k+n+1)

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

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

dict_s = {c: [] for c in ascii_lowercase}
for i, c in enumerate(s * 2):
    dict_s[c].append(i)

for c in ascii_lowercase:
    if not dict_s[c]:
        del dict_s[c]


dict_next_i = {
    c: [dict_s[c][bisect_left(dict_s[c], i + 1)] for i in range(n)]
    for c in dict_s.keys()
}


def next_i(i, c):
    return n * (i // n) + dict_next_i[c][i % n]


def answer():
    if not all(c in s for c in t):
        return -1
    i = -1
    for c in t:
        i = next_i(i, c)
    return i + 1  


print(answer())

Solution (Python):
import sys
from string import ascii_lowercase as a2z

input = sys.stdin.readline


def main():
    S = input().rstrip()
    T = input().rstrip()

    N = len(S)
    memo = [None] * N
    memo[-1] = {alphabet: -1 for alphabet in a2z}
    memo[-1][S[-1]] = N - 1
    for i in reversed(range(N - 1)):
        memo[i] = memo[i + 1].copy()
        memo[i][S[i]] = i

    ans = 0
    idx_S = 0
    for t in T:
        i = memo[idx_S][t]
        if i == -1:
            ans += (N - idx_S)
            idx_S = 0
            i = memo[idx_S][t]
            if i == -1:
                ans = -1
                break
            else:
                ans += i - idx_S + 1
                if i == N - 1:
                    idx_S = 0
                else:
                    idx_S = i + 1
        else:
            ans += i - idx_S + 1
            if i == N - 1:
                idx_S = 0
            else:
                idx_S = i + 1

    print(ans)


if __name__ == "__main__":
    main()