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 bisect import bisect_left

S = input()
T = input()

ss = set(list(S))
st = set(list(T))
if not (st <= ss):
    print(-1)
    exit()
alpha = {chr(97+i): [] for i in range(26)}
for i, s in enumerate(S):
    alpha[s].append(i+1)
n = len(S)
now = 0
ans = 0
for t in T:
    if alpha[t][-1] <= now:
        ans += (n - now) + alpha[t][0]
        now = alpha[t][0]
    else:
        i = bisect_left(alpha[t], now+1)
        ans += alpha[t][i] - now
        now = alpha[t][i]
print(ans)

Solution (Python):

import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
from bisect import bisect_left, bisect_right

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

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

    chars = {ch: [] for ch in alphabets}

    for i, ch in enumerate(s):
        chars[ch].append(i)

    ans = 0
    last = -1
    for ch in t:
        if len(chars[ch]) == 0:
            print(-1)
            return

        idx = bisect_right(chars[ch], last)
        idx = idx if idx < len(chars[ch]) else 0
        if chars[ch][idx] > last:
            ans += chars[ch][idx] - last
        else:
            ans += len(s) - last + chars[ch][idx]
        last = chars[ch][idx]

    print(ans)



if __name__ == '__main__':
    main()

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

s = input()
ns = len(list(s))
t = input()
nt = len(list(t))

jisho = defaultdict(list)



for i in range(ns):
    jisho[s[i]].append(i)





now = -1  
cnt = 0  
for i in range(nt):
    lis = jisho[t[i]]
    if not lis:
        print(-1)
        exit()
    pos = bisect_right(lis, now)
    
    
    if pos == len(lis):
        now = -1
        cnt += 1
        pos = bisect_right(lis, now)
    now = lis[pos]
print(cnt * ns + now + 1)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
from collections import Counter, defaultdict
from bisect import bisect_left


def read():
    S = input().strip()
    T = input().strip()
    return S, T


def have_ahswer(S, T):
    cs = Counter(S)
    ct = Counter(T)
    for k in ct.keys():
        if cs[k] == 0:
            return False
    return True


def solve(S, T):
    Z = "abcdefghijklmnopqrstuvwxyz"
    if not have_ahswer(S, T):
        return -1
    D = defaultdict(list)
    for i, s in enumerate(S):
        D[s].append(i)
    ans = 0
    prev_index = -1
    N = len(S)
    for t in T:
        a = D[t]
        i = bisect_left(a, prev_index + 1)
        if i < len(a):
            next_index = a[i]
            ans += next_index - prev_index
        else:
            next_index = a[0]
            ans += N + next_index - prev_index
        prev_index = next_index
    return ans


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Solution (Python):
from collections import Counter
import bisect

S = input()
T = input()

ls = len(S)
lt = len(T)

cons = Counter(S)
cont = Counter(T)
dics = {}
dicc = {}

for i in range(ls):
  if S[i] not in dics:
    dics[S[i]] = [i+1]
    dicc[S[i]] = 1
  else:
    dics[S[i]].append(i+1)
    dicc[S[i]] += 1
idx = 0
cic = 0
for t in T:
  if t not in dics:
    print(-1)
    exit()
  i = bisect.bisect_left(dics[t], idx)
  if i == dicc[t]:
    idx = dics[t][0] + 1
    cic += 1
  else:
    idx = dics[t][i] + 1
    
print(cic*ls+idx-1)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





s = input()
t = input()


p = {c: [] for c in s}
for i in range(len(s)):
    p[s[i]].append(i)

z = 0
l = -1
for c in t:
    if c not in p:
        print(-1)
        break
    
    x = bisect_right(p[c], l)
    
    if x == len(p[c]):
        x = 0
        z += 1
    l = p[c][x]
else:
    print(z * len(s) + l + 1)

Solution (Python):
import bisect
ind = {}
s = input()
t = input()
for i, c in enumerate(s):
    if c in ind:
        ind[c].append(i+1)
    else:
        ind[c] = [i+1]
k = len(s)
nk = 0
if not t[0] in ind:
    print(-1)
    exit()
nw = ind[t[0]][0]
pv = nw
for i in range(1, len(t)):
    c = t[i]
    if not c in ind:
        print(-1)
        exit()
    if ind[c][-1]>pv:
        pv = ind[c][bisect.bisect_left(ind[c], pv+1)]
    else:
        nk += k
        pv = ind[c][0]
    nw = pv + nk
print(nw)

Solution (Python):
from bisect import bisect_left as bisect

s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

alp = [[] for i in range(26)]
for i, si in enumerate(s):
    alp[ord(si) - 97].append(i)

ans, cnt = 1 - lens, 0
for i in t:
    li = alp[ord(i) - 97]
    ans += lens * (cnt == 0)
    num = bisect(li, cnt)
    ans += lens * (num == len(li))
    cnt = (li[num % len(li)] + 1) % lens
print(ans + (cnt - 1) % lens)

Solution (Python):
from bisect import bisect_left as bisect

s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

alp = [[] for i in range(26)]
for i, si in enumerate(s):
    alp[ord(si) - 97].append(i)

ans, cnt = 1 - lens, 0
for i in t:
    li = alp[ord(i) - 97]
    ans += lens * (cnt == 0)
    num = bisect(li, cnt)
    ans += lens * (num == len(li))
    cnt = (li[num % len(li)] + 1) % lens 
print(ans + (cnt - 1) % lens)

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


s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

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

ans, cnt = 1 - lens, 0
for i in t:
    ans += lens * (cnt == 0)
    num = bisect(alp[i], cnt)
    ans += lens * (num == len(alp[i]))
    cnt = (alp[i][num % len(alp[i])] + 1) % lens 
print(ans + (cnt - 1) % lens)

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


s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

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

ans, cnt = 1 - lens, 0
for i in t:
    ans += lens * (cnt == 0)
    num = bisect(alp[i], cnt)
    ans += lens * (num == len(alp[i]))
    cnt = (alp[i][num % len(alp[i])] + 1) % lens 
print(ans + (cnt - 1) % lens)

Solution (Python):
def solve():
    import bisect
    S = input()
    T = input()
    dic = {}
    length = {}

    for i, s in enumerate(S, 1):
        if s not in dic:
            dic[s] = []
        dic[s].append(i)

    for k, v in dic.items():
        if k not in length:
            length[k] = 0
        length[k] = len(v)

    l, turn, prov = len(S), 0, 0

    for t in T:
        if t not in dic:
            print(-1)
            exit()
        x = bisect.bisect(dic[t], prov)
        if x < length[t]:
            prov = dic[t][x]
        else:
            turn += 1
            prov = dic[t][0]
    print(turn * l + prov)

solve()

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

s = input()
S = len(s)
t = input()
T = len(t)
D = defaultdict(list)
Dc = defaultdict(int)
Exists = True

for i in range(S):
  D[s[i]].append(i+1)
  Dc[s[i]] += 1

ans = 0
temp = 0
for i in range(T):
  if D[t[i]] == []:
    Exists = False
    break
  j = bisect(D[t[i]], temp)
  if j == Dc[t[i]]:
    ans += S - temp + D[t[i]][0]
    temp = D[t[i]][0]
  else:
    ans += D[t[i]][j] - temp
    temp = D[t[i]][j]

if Exists:
  print(ans)
else:
  print(-1)

Solution (Python):
import bisect

def ctoi(char):
  return ord(char)-ord('a')

s=input()
l=len(s)
t=input()
if len(set(t)-set(s))!=0:
  print(-1)
  exit()
pos=[[] for _ in range(26)]
for i in range(2*l):
  pos[ctoi(s[i%l])].append(i+1)
index=0
loop=0
for i in range(len(t)):
  tmp=bisect.bisect_right(pos[ctoi(t[i])],index)
  next_index=pos[ctoi(t[i])][tmp]
  if next_index>=l:
    loop+=1
  index=next_index%l
print(l*loop+index)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
flag = [False] * 26
for si in s:
    flag[ord(si) - ord('a')] = True
for ti in t:
    if not flag[ord(ti) - ord('a')]:
        print(-1)
        quit()
n = len(s)
S = s + s
idx = [[] for _ in range(26)]
for i in range(2*n):
    idx[ord(S[i]) - ord('a')].append(i)

dp = [[inf] * 26 for _ in range(n)]
for i in range(n):
    for j in range(26):
        if idx[j]:
            r = br(idx[j], i)
            dp[i][j] = idx[j][r]
c = ord(t[0]) - ord('a')
i = idx[c][0]
ans = i + 1
for ti in t[1:]:
    c = ord(ti) - ord('a')
    ni = dp[i][c] % n
    ans += dp[i][c] - i
    i = ni
print(ans)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

s = sr()
t = sr()
n = len(s)
dic = {chr(ord('a')+i):[] for i in range(26)}
for i,c in enumerate(s):
    dic[c].append(i+1)
for c in t:
    if not dic[c]:
        print('-1')
        sys.exit()
ans = 0
pre = 0
for c in t:
    ind = bisect.bisect_left(dic[c],pre+1)
    if ind == len(dic[c]):
        ans+=(n-pre)
        pre = dic[c][0]
        ans+=pre
    else:
        ans+=(dic[c][ind]-pre)
        pre = dic[c][ind]
print(ans)

Solution (Python):
import copy

s = input()
t = input()

sn = len(s)
tn = len(t)
a = [[] for i in range(26)]
for i in range(sn):
    num = ord(s[i]) - 97
    a[num].append(i)

table = [[0]*sn for i in range(26)]
for i in range(26):
    if a[i]:
        table[i][:] = [copy.deepcopy(a[i][0])]*sn
    f = 0
    for j in a[i]:
        table[i][f:j] = [copy.deepcopy(j)]*(j-f)
        f = copy.deepcopy(j)

flg = True
cnt = 0 
x = -1 
for i in range(tn):
    num = ord(t[i]) - 97
    
    if not a[num]:
        flg = False
        break
    
    xx = copy.deepcopy(x)
    x = table[num][x]
    if xx >= x:
        cnt += 1
print(cnt*sn + x+1) if flg else print(-1)

Solution (Python):
import copy

s = input()
t = input()

sn = len(s)
tn = len(t)
a = [[] for i in range(26)]
for i in range(sn):
    num = ord(s[i]) - 97
    a[num].append(i)

table = [[0]*sn for i in range(26)]
for i in range(26):
    if a[i]:
        table[i][:] = [copy.deepcopy(a[i][0])]*sn
    f = 0
    for j in a[i]:
        table[i][f:j] = [copy.deepcopy(j)]*(j-f)
        f = copy.deepcopy(j)

flg = True
cnt = 0 
x = -1 
for i in range(tn):
    num = ord(t[i]) - 97
    
    if not a[num]:
        flg = False
        break
    
    xx = copy.deepcopy(x)
    x = table[num][x]
    if xx >= x:
        cnt += 1
print(cnt*sn + x+1) if flg else print(-1)

Solution (Python):
from bisect import bisect_right
s=input()
t=input()
ns=len(s)
nt=len(t)
alp=[[] for i in range(26)]
for i in range(ns):
    alp[ord(s[i])-97].append(i)
alpl=[len(alp[i]) for i in range(26)]
ans=0
now=-1
for i in range(nt):
    if alpl[ord(t[i])-97]==0:
        exit(print(-1))
    b=bisect_right(alp[ord(t[i])-97],now)
    if b==alpl[ord(t[i])-97]:
        now=alp[ord(t[i])-97][0]
        ans+=ns
        if i==nt-1:
            ans+=(now+1)
    else:
        now=alp[ord(t[i])-97][b]
        if i==nt-1:
            ans+=(now+1)
print(ans)

Solution (Python):
def resolve():
    s = input()
    t = input()
    d = {}
    for i, c in enumerate(list(s)):
        d.setdefault(c, [])
        d[c].append(i)
    
    import bisect
    nloops = 0
    prev = -1
    for c in list(t):
        if c not in d:
            print(-1)
            return
        
        cidx = bisect.bisect_left(d[c], prev)
        if cidx < len(d[c]) and prev == d[c][cidx]:
            cidx += 1
        nearc = d[c][cidx] if cidx < len(d[c]) else None
        if nearc is None:
            nloops += 1
            nearc = d[c][0]
        prev = nearc
    print(nloops*len(s)+prev+1)



if '__main__' == __name__:
    resolve()

Solution (Python):
import sys

def LS2(): return list(sys.stdin.readline().rstrip())

s = LS2()
t = LS2()

from collections import defaultdict

dict_s = defaultdict(list)

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

r = 0  
u = -1  
for a in t:
    if len(dict_s[a]) == 0:
        print(-1)
        exit()
    else:
        left = -1
        right = len(dict_s[a])
        while left + 1 < right:
            mid = (left + right)//2
            if dict_s[a][mid] > u:
                right = mid
            else:
                left = mid
        if right == len(dict_s[a]):
            r += 1
            u = dict_s[a][0]
        else:
            u = dict_s[a][right]

print(len(s)*r+u+1)

Solution (Python):
import sys

def LS2(): return list(sys.stdin.readline().rstrip())

s = LS2()
t = LS2()

from collections import defaultdict

dict_s = defaultdict(list)

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

d = {}
for a in dict_s.keys():
    d[a] = 0

r = 0
u = -1
for a in t:
    if len(dict_s[a]) == 0:
        print(-1)
        exit()
    else:
        left = -1
        right = len(dict_s[a])
        while left + 1 < right:
            mid = (left + right)//2
            if dict_s[a][mid] > u:
                right = mid
            else:
                left = mid
        if right == len(dict_s[a]):
            r += 1
            u = dict_s[a][0]
        else:
            u = dict_s[a][right]

print(len(s)*r+u+1)

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

n = len(s)

if set(list(t)) != (set(list(s)) & set(list(t))): ans = -1
else:
    dct = {}

    for i, ss in enumerate(s):
        if ss in dct:
            dct[ss].append(i)
        else: dct[ss] = [i]
    idx = -1
    ans = 0
    for tt in t:
        m = bisect_right(dct[tt], idx)
        if m == len(dct[tt]):
            idx = dct[tt][0]
            ans += n
        else:
            idx = dct[tt][m]
    ans += idx + 1

print(ans)

Solution (Python):
import bisect
from collections import defaultdict

s = input()
t = input()
if set(s) & set(t) != set(t):
    print(-1)
    exit()
cnt = defaultdict(list)
for i, c in enumerate(s, 1):
    cnt[c].append(i)
loop = 0
prev = 0
for w in t:
    l = cnt[w]
    idx = bisect.bisect_right(l, prev)
    if idx < len(l):
        prev = l[idx]
    else:
        prev = l[0]
        loop += 1
ans = loop*len(s) + prev
print(ans)

Solution (Python):
from collections import defaultdict
from bisect import bisect_right
s,t=input(),input()
m=len(s)

dictionary=defaultdict(list)
for i,j in enumerate(s):
    dictionary[j] +=[i+1]

index,ans=0,0
for i in t:
    try:
        point=bisect_right(dictionary[i],index)
        if point==len(dictionary[i]):num=dictionary[i][0]
        else:num=dictionary[i][point]

        if index>=num:
            ans +=m
        index=num
    except:print(-1);exit()

print(ans+index)

Solution (Python):
from bisect import bisect_left

s = list(input())

t = list(input())

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

for i in range(len(s)):
    alf[ord(s[i])-97].append(i)

now_alf = -1
sets = 0
i = 0

while i < len(t):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    if now_alf > alf[next_alf][-1]:
        now_alf = -1
        sets += 1
    else:
        serch_next_alf = bisect_left(alf[next_alf], now_alf)
        now_alf = alf[next_alf][serch_next_alf]+1
        i += 1

print(sets*len(s)+now_alf)

Solution (Python):
from bisect import bisect_left

s = list(input())

total_s = len(s)

t = list(input())

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

for i in range(len(s)):
    alf[ord(s[i])-97].append(i+1)

coti_alt = 0
now_alf = 0
ans = 0

for i in range(len(t)):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    if 0 < i and t[i-1] == t[i]:
        now_alf += 1
        ans += 1
        if now_alf == total_s and t[i] == s[now_alf-1]:
            continue

    serch_next_alf = bisect_left(alf[next_alf], now_alf)

    if now_alf < alf[next_alf][-1]:
        ans += alf[next_alf][serch_next_alf] - now_alf
        now_alf = alf[next_alf][serch_next_alf]
    else:
        ans += total_s - now_alf + alf[next_alf][0]
        now_alf = alf[next_alf][0]
    

print(ans)

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

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

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

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>=num:
        ans +=m
    index=num

print(ans+index)

Solution (Python):


from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()


iS = defaultdict(list)
for (idx, ch) in enumerate(S):
    iS[ch].append(idx)


for v in T:
    if v not in iS:
        print(-1)
        exit()


cnt = 0
cur = -1
for v in T:
    i = bisect_right(iS[v], cur)
    if i == len(iS[v]):
        j = iS[v][0]
    else:
        j = iS[v][i]

    if cur >= j:
        cnt += 1
    cur = j

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

Solution (Python):
s=input()
t=input()
ds={}
for i in range(len(s)):
  if s[i] in ds:
    ds[s[i]].append(i+1)
  else:
    ds[s[i]]=[i+1]
n=len(s)
now=0 
ans=0
from bisect import bisect_right
for ti in t:
  if ti not in ds:
    print(-1)
    exit()
  tmp=bisect_right(ds[ti],now)
  if tmp==len(ds[ti]):
    get=n+ds[ti][0]
  else:
    get=ds[ti][tmp]
  ans+=get-now
  
  now=(get)%n
print(ans)

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

s = input()
t = input()

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

cnt = 0
cur = -1
mod = len(s)
flag = False
for v in t:
    if v not in indices:
        flag = True
        break

    i = bisect_right(indices[v], cur)
    if i == len(indices[v]):
        j = indices[v][0]
    else:
        j = indices[v][i]

    if cur >= j:
        cnt += 1
    cur = j

if flag:
    print(-1)
else:
    print(cnt * mod + cur + 1)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





S,T = S(),S()
N = len(S)
dic = DD(list)
for i in range(N):
  dic[S[i]].append(i+1)

now = 0
for t in T:
  if not dic[t]:
    print(-1)
    exit()
  if now%N < dic[t][-1]:
    now += dic[t][bisect.bisect(dic[t],now%N)]-now%N
  else:
    now = -(-now//N)*N + dic[t][0]

print(now)

Solution (Python):
from bisect import bisect_left, bisect_right

s = input()
t = input()

alp = 'abcdefghijklmnopqrstuvwxyz'
alp_pos = {}
for a in alp:
    alp_pos[a] = []

for i,v in enumerate(s):
    alp_pos[v].append(i+1)


loop = 0
curr_pos = 0
for ti in t:
    if not alp_pos[ti]:
        print(-1)
        exit()
    curr_alp_poss = alp_pos[ti]
    ind = bisect_right(curr_alp_poss, curr_pos)
    if ind >= len(curr_alp_poss):
        loop += 1
        curr_pos = curr_alp_poss[0]
    else:
        curr_pos = curr_alp_poss[ind]

print(loop*len(s)+curr_pos)

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

    def check(S, T):
        b = {s for s in S}
        for t in T:
            if t not in b:
                return True  
        return False

    def is_ok(mid, now, ans):
        if ans < now[mid]:
            return True
        else:
            return False

    def binary_search_meguru(now, ans):
        ng = -1
        ok = len(now)-1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid, now, ans):
                ok = mid
            else:
                ng = mid
        return now[ok]

    if check(S, T):
        return print(-1)

    from string import ascii_lowercase

    dic = {a: [] for a in ascii_lowercase}
    for i, s in enumerate(S):
        dic[s].append(i+1)
    ans = 0
    cycle = 0
    for t in T:
        now = dic[t]
        if now[-1] <= ans:
            cycle += 1
            ans = 0
        idx = binary_search_meguru(now, ans)
        ans = idx
    print(ans + N*cycle)


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


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

    D = {chr(i): [] for i in range(ord("a"), ord("z") + 1)}

    for i, s in enumerate(S):
        D[s].append(i)
    
    res = 0
    p = 0
    for t in T:
        if D[t] == []:
            print(-1)
            return
        
        j = bisect.bisect_left(D[t], p)
        if j == len(D[t]):
            p = D[t][0] + 1
            res += 1
        else:
            p = D[t][j] + 1
        
    print(res * len(S) + p)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    S = input()
    N = len(S)
    INF = N + 1
    T = input()
    
    next_loc = [[INF for _ in range(N)] for _ in range(26)]
    for i, s in enumerate(S):
        c = ord(s) - ord('a')
        next_loc[c][i - 1] = 1
    for c in range(26):
        n = INF
        for i in range(N - 1, -(N + 1), -1):
            n = min(next_loc[c][i], n + 1)
            next_loc[c][i] = n
    
    ans = 0
    index = -1
    for t in T:
        c = ord(t) - ord('a')
        i = next_loc[c][index]
        if i == INF:
            print(-1)
            return
        ans += i
        index = (index + i) % N
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()
l_s = len(s)
l_t = len(t)

s2 = s + s
l_s2 = len(s2)

next_idx = [[l_s2] * 26 for i in range(l_s2)]

for i in reversed(range(1, l_s2)):
    for j in range(26):
        next_idx[i-1][j] = next_idx[i][j]
    next_idx[i-1][ord(s2[i]) - ord("a")] = i

cur_idx = 0
for i in range(l_t):
    if i == 0:
        flg = False
        for j in range(l_s):
            if t[i] == s[j]:
                cur_idx += j
                flg = True
                break
        if flg:
            continue
        else:
            print("-1")
            exit()

    else:
        idx = next_idx[cur_idx%l_s][ord(t[i]) - ord("a")]

    if idx == l_s2:
        print("-1")
        exit()

    cur_idx += idx - (cur_idx % l_s)
    
print(cur_idx+1)