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


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush

from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math

import bisect






INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())



def run():
    S, T = input(), input()
    dic = defaultdict(lambda : [])
    for i, s in enumerate(S):
        dic[s].append(i)

    k = -1
    ans = 1
    for t in T:
        if t in dic.keys():
            i = bisect.bisect_right(dic[t], k)
            if i >= len(dic[t]):
                k = dic[t][0]
                ans += 1
            else:
                k = dic[t][i]

        else:
            print(-1)
            return

    print((ans-1) * len(S) + k +1)


if __name__ == "__main__":
    
    run()

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  t=S()
  n2=len(t)

  d={}
  for i,x in enumerate(s):
    if x in d:
      y=d[x]
      y.append(i)
      d[x]=y
    else:
      d[x]=[i]

  
  i=0
  j=0
  ans=1
  while j<n2:
    check=t[j]
    if check not in d:
      return -1
    l=d[check]
    if i<l[0]:
      ans+=l[0]-i+1
      i=l[0]+1
      j+=1
    elif l[-1]<i:
      ans+=n-(i+1)+l[0]+2
      i=l[0]+1
      j+=1
    else:
      if i==l[0]:
        ans+=1
        i+=1
        j+=1
      elif i==l[-1]:
        ans+=1
        i+=1
        j+=1
      else:
        left=0
        right=len(l)
        while right-left>1:
          m=(right+left)//2
          if l[m]>=i:
            right=m
          else:
            left=m
          
        ans+=l[right]-i+1
        i=l[right]+1
        j+=1

    

    i%=n

  return ans-1


print(main())

Solution (Python):
from bisect import bisect_left


S = input()
T = input()
if any(c not in S for c in T):
    print(-1)
    exit()

N = len(S)
pos = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
for i in range(N):
    pos[S[i]].append(i)

loop = 0
cur = 0
for c in T:
    nxt = bisect_left(pos[c], cur)
    if nxt == len(pos[c]):
        loop += 1
        cur = pos[c][0] + 1
    else:
        cur = pos[c][nxt] + 1
print(loop * N + cur)

Solution (Python):
from bisect import bisect_right as br
S=input()
T=input()

def s2n(s):
    return ord(s)-97

ALF=[[] for _ in [0]*26]
for i in range(len(S)):
    ALF[s2n(S[i])].append(i)

ALF_T=[0]*26
seqT=[]
res=0
for t in T:
    i=s2n(t)
    if ALF[i]:
        if seqT:
            a=seqT[-1]
        else:
            a=-1
        j=br(ALF[i],a)
        seqT.append(ALF[i][j%len(ALF[i])])
    else:
        res=-1
if res>=0:
    tmp=[]
    m=-1
    for n in seqT:
        if m<n:
            tmp.append(n)
        else:
            res+=1
            tmp=[n]
        m=n
    res=res*len(S)+tmp[-1]+1
print(res)

Solution (Python):
from bisect import bisect_left

S = list(input())
T = list(input())
dict_s = {}
for i,val in enumerate(S):
    if val in dict_s:
        dict_s[val].append(i)
    else:
        dict_s[val] = [i]

l_cunt = 0
now_point = -1
for i,val in enumerate(T):
    if val in dict_s:
        tmp_point = bisect_left(dict_s[val],now_point)
        if tmp_point == len(dict_s[val]):
            l_cunt += 1
            tmp_point = 0
        now_point = dict_s[val][tmp_point]+1
    else:
        print(-1)
        exit()

print(l_cunt*len(S)+now_point)

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

n = len(s)
m = len(t)
s += s
next = [[-1] * 26 for _ in range(len(s) + 1)]




for i in range(len(s) - 1, -1, -1):
    c = ord(s[i]) - ord('a')
    for j in range(26):
        if j == c:
            next[i][j] = i
        else:
            next[i][j] = next[i + 1][j]
now = 0
ans = 0
for i in range(m):
    c = ord(t[i]) - ord('a')
    if next[now][c] == -1:
        print(-1)
        exit()
    ans += next[now][c] - now + 1
    now = next[now][c] + 1
    if now >= n:
        now -= n
print(ans)

Solution (Python):
def main():
    from functools import lru_cache
    import bisect
    S = input()
    T = input()
    if set(S) & set(T) != set(T):
        print(-1)
    else:
        lt = len(T)
        ls = len(S)
        st = set(T)
        D = dict()
        for t in st:
            D[t] = list()
            for i, s in enumerate(S):
                if t == s:
                    D[t].append(i)
        pre = -1
        cnt = 0

        @lru_cache(maxsize=None)
        def judge(pre, t):
            X = D[t]
            index = bisect.bisect(X, pre)
            if len(X) == index:
                return (X[0], True)
            else:
                return (X[index], False)

        for t in T:
            J = judge(pre, t)
            pre = J[0]
            if J[1]:
                cnt += 1

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


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_right

s = input()
t = input()

n = len(s)

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

ans = 0
now = -1
for i in range(len(t)):
    a = ord(t[i]) - ord('a')
    nxt = bisect_right(mp[a], now)
    if len(mp[a]) == nxt:
        print(-1)
        exit()

    ans += mp[a][nxt] - now
    now = mp[a][nxt]
    if now >= n:
        now -= n

print(ans)

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

s = input()
t = input()

n = len(s)

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

ans = 0
now = -1
for i in range(len(t)):
    a = ord(t[i]) - ord('a')
    nxt = bisect_right(mp[a], now)
    if len(mp[a]) == nxt:
        print(-1)
        exit()

    now = mp[a][nxt]
    if now >= n:
        ans += n
        now -= 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)

ans = 0
import bisect
cur = -1
for c in t:
    j = ord(c)-ord('a')
    if len(X[j]) == 0:
        print(-1)
        exit()
    k = bisect.bisect_right(X[j], cur)
    if k != len(X[j]):
        cur = X[j][k]
    else:
        cur = X[j][0]
        ans += len(s)
ans += cur+1
print(ans)

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

s,t = input(),input()
before,count = len(s),0
idx = defaultdict(list)

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

for i,l in enumerate(s):
  idx[l] += [i]
  
for c in t:
  N = idx[c]
  index = bisect_left(N, before)
  if index > len(N) - 1:
    before = N[0] + 1
    count += 1
  else:
    before = N[index] + 1
    
print((count - 1) * len(s) + before)

Solution (Python):
from collections import defaultdict
from bisect import bisect_left
s = input()
t = input()
ids = defaultdict(list)
for i, c in enumerate(s):
    ids[c].append(i)
i = 0
ans = 0
for c in t:
    if c not in ids:
        print(-1)
        exit()
    ls = ids[c]
    j = bisect_left(ls, i)
    if j == len(ls):
        ans += len(s)
        i = ls[0]+1
    else:
        i = ls[j]+1
print(ans+i)

Solution (Python):
import sys
import bisect


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


def main():
    S = list(input())
    T =list(input())

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

    orda =ord("a")

    for i in range(len(S)):
        G[ord(S[i])-orda].append(i)

    count =0
    p=-1
    for j in range(len(T)):
        tord = ord(T[j]) -orda
        if G[tord]!=[]:
            if G[tord][-1]<p+1:
                p=-1
                count+=1

            gp =bisect.bisect_left(G[tord],p+1)
            p =G[tord][gp]

        else:
            print(-1)
            exit()


    print(count * len(S)+p+1)





if __name__ == "__main__":
    main()

Solution (Python):
import bisect

s = input()
t = input()
if set(list(s + t)) != set(list(s)):
    print(-1)
    exit()
check = set(list(t))
dic = {}
for Str in check:
    dic[Str] = []
for i in range(len(s)):
    if s[i] in check:
        dic[s[i]] += [i]
times = 0
now = -1
for p in t:
    if now >= dic[p][-1]:
        now = dic[p][0]
        times += 1
    else:
        now = dic[p][bisect.bisect(dic[p], now)]
print(len(s) * times + now + 1)

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

n = len(s)
s = s * 2


r = {}
for i, v in enumerate(s):
    if v in r.keys():
        r[v].append(i+1)
    else:
        r[v] = [i+1]

now = 0

lt = len(t)
for v in t:
    if v in r.keys():
        index = bisect_left(r[v], now % n + 1)
        tmp = r[v][index]
        now += tmp - now % n
    else:
        print(-1)
        exit()

print(now)

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

def main():

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

  dic=dd(list)
  for idx,i in enumerate(s*2):
    dic[i].append(idx)

  ans,p=0,-1
  for i in t:
    if i not in dic.keys():
      print(-1)
      exit()
    p=dic[i][bisect_left(dic[i], p+1)]
    if p>=n:
      p-=n
      ans+=n

  print(ans+p+1)

if __name__=='__main__':
  main()

Solution (Python):
import bisect

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

dic={}
for idx,i in enumerate(s*2):
  if i in dic.keys():
    dic[i].append(idx)
  else:
    dic[i]=[idx]

ans,p=0,-1
for i in t:
  if i not in dic.keys():
    print(-1)
    exit()
  p=dic[i][bisect.bisect_left(dic[i], p+1)]
  if p>=n:
    p-=n
    ans+=n
  
print(ans+p+1)

Solution (Python):
import bisect

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

dic={}
for idx,i in enumerate(s*2):
  if i in dic.keys():
    dic[i].append(idx)
  else:
    dic[i]=[idx]


    
ans=k=0
before='-1'
for i in t:
  if i not in dic.keys():
    print(-1)
    exit()
  t=bisect.bisect_left(dic[i], ans%n)
  if before==i:
    t+=1
  if len(dic[i])==t:
    t=0
    k+=n
  ans=dic[i][t]+k
  before=i
  
print(ans+1)

Solution (Python):
s = input()
t = input()
next_alpha = [[-1] * len(s) for _ in range(30)] 
for i, s_ in enumerate(s):
    j = ord(s_) - 97
    for k in range(i, -1, -1):
        if next_alpha[j][k] != -1:
            break
        next_alpha[j][k] = i

ans = 0
for t_ in t:
    i = ans % len(s)
    tmp = next_alpha[ord(t_) - 97][i]
    if tmp == -1:
        ans += (-1 * ans) % len(s)
        i = ans % len(s)
        tmp = next_alpha[ord(t_) - 97][i]
    if tmp == -1:
        ans = -1
        break
    else:
        ans += tmp - (i - 1)
print(ans)

Solution (Python):
import string
import bisect
s=input()
t=input()
S=[[] for _ in range(26)]
a=string.ascii_lowercase
now=-1
ans=-1
count=0
for i in range(len(s)):
    for j in range(26):
        if s[i]==a[j]:
            S[j].append(i)
            break
for i in range(len(t)):
    for j in range(26):
        if t[i]==a[j]:
            break
    if len(S[j])==0:
        break
    nex=bisect.bisect_right(S[j],now)
    if nex==len(S[j]) or now>=S[j][nex]:
        count+=1
        now=S[j][0]
    else:
        now=S[j][nex]
    if i==len(t)-1:
        ans=count*(len(s))+now+1
print(ans)

Solution (Python):
import bisect

s = input()
t = input()
n = len(s)
s0 = {}
for i in range(n):
    s0.setdefault(s[i], [])
    s0[s[i]].append(i)
num1 = 0
num2 = -1
flag = True
for i in t:
    if i not in s:
        flag = False
        break
    num = bisect.bisect_right(s0[i], num2)
    if num == len(s0[i]):
        num1 += 1
        num2 = s0[i][0]
    else:
        num2 = s0[i][num]
if flag == True:
    print(num1 * n + num2 + 1)
else:
    print(-1)

Solution (Python):
"""
tの先頭から、できるだけ長い文字列を一回のsで消費するゲーム
できるだけ短い時間で、残っているtの先頭からどこまでを一回で消費できるかを判断したい。
部分文字列DPのときにやったみたいに、ns[i][j] => i番目より後ろで、つぎに文字jが出てくるインデックス
という表を作っておけばよい。
"""

S = input()
T = input()
N = len(S)
dp = [[-1]*26 for _ in range(N+1)]
for i in range(N):
    s = S[i]
    dp[i][ord(s)-ord("a")] = i+1

for i in range(N-2,-1,-1):
    for j in range(26):
        if dp[i][j] == -1:
            dp[i][j] = dp[i+1][j]

cycleCnt = 0
sInd = 0
for i in range(len(T)):
    if dp[sInd][ord(T[i])-ord("a")] == -1:
        cycleCnt += 1
        sInd = 0
        if dp[sInd][ord(T[i])-ord("a")] == -1:
            print(-1)
            exit()
    sInd = dp[sInd][ord(T[i])-ord("a")]
else:
    print(cycleCnt*N+sInd)

Solution (Python):
from bisect import bisect

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

def solve():
    S = input()
    T = input()
    N = len(S)
    idx = [[] for i in range(26)]
    for i in range(2 * N):
        idx[ctoi(S[i % N])].append(i)
    ans = -1
    for c in T:
        if not idx[ctoi(c)]:
            return -1
        ans += idx[ctoi(c)][bisect(idx[ctoi(c)], ans % N)] - ans % N
    return ans + 1
print(solve())

Solution (Python):
from bisect import bisect_left, bisect_right
s = input()
t = input()
n_s = len(s)
n_t = len(t)


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



def a_idx(a):
    idx = ord(a)
    idx -= 97
    return idx


for i in range(n_s):
    idx[a_idx(s[i])].append(i)

t_syutugenkasyo = []
for i in range(n_t):
    t_syutugenkasyo.append(idx[a_idx(t[i])])


now = -1
ans = 0
for i in range(n_t):
    if len(t_syutugenkasyo[i]) == 0:
        print(-1)
        exit()
    ni = bisect_right(t_syutugenkasyo[i], now)
    if ni >= len(t_syutugenkasyo[i]):
        ans += n_s
        now = t_syutugenkasyo[i][0]
    else:
        now = t_syutugenkasyo[i][ni]
ans += now+1
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
s = input()
t = input()
n_s = len(s)
n_t = len(t)


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



def a_idx(a):
    idx = ord(a)
    idx -= 97
    return idx


for i in range(n_s):
    idx[a_idx(s[i])].append(i)

t_syutugenkasyo = []
for i in range(n_t):
    t_syutugenkasyo.append(idx[a_idx(t[i])])


now = -1
ans = 0
for i in range(n_t):
    if len(t_syutugenkasyo[i]) == 0:
        print(-1)
        exit()
    ni = bisect_right(t_syutugenkasyo[i], now)
    if ni >= len(t_syutugenkasyo[i]):
        ans += n_s
        now = -1
        ni = bisect_right(t_syutugenkasyo[i], now)
        now = t_syutugenkasyo[i][ni]
    else:
        now = t_syutugenkasyo[i][ni]
ans += now+1
print(ans)

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

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

len_s=len(s)
len_t=len(t)


for i in range(len_s):
    idx=ord(s[i])-97
    pos[idx].append(i)

ans=[]
tmp=-1
cnt=0
for i in range(len_t):
    idx=ord(t[i])-97
    if len(pos[idx])==0:
        print(-1)
        exit()

    if tmp<pos[idx][-1]:
        l=-1
        r = len(pos[idx]) - 1
        while l + 1 < r:
            mid = (l + r) // 2
            if pos[idx][mid] <= tmp:
                l = mid
            else:
                r=mid
        ans.append(pos[idx][r])
        tmp=pos[idx][r]
    else:
        cnt+=1
        ans.append(pos[idx][0])
        tmp=pos[idx][0]


print(cnt*len_s+ans[-1]+1)

Solution (Python):
def next(str):
    N = len(str)
    nxt = [[N] * 26 for i in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(str[i]) - ord('a')] = i
    return nxt

def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = next(S)
    ans = -1
    for c in T:
        i = ans % N
        pos = ord(c) - ord('a')
        if nxt[i + 1][pos] == M:
            return -1
        ans += nxt[i + 1][pos] - i
    return ans + 1

print(solve())

Solution (Python):
def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = [[M] * 26 for i in range(M + 1)]
    for i in range(M - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(S[i]) - ord('a')] = i
    ans = -1
    for c in T:
        i = ans % N
        pos = ord(c) - ord('a')
        if nxt[i + 1][pos] == M:
            return -1
        ans += nxt[i + 1][pos] - i
    return ans + 1

print(solve())

Solution (Python):
def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = [[M] * 26 for i in range(M + 1)]
    for i in range(M - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(S[i]) - ord('a')] = i
    ans = 0
    i = 0
    for c in T:
        pos = ord(c) - ord('a')
        if nxt[i][pos] == M:
            return -1
        ans += nxt[i][pos] - i + 1
        i = (nxt[i][pos] + 1) % N
    return ans

print(solve())

Solution (Python):
def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = [[M] * 26 for i in range(M + 1)]
    for i in range(M - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(S[i]) - ord('a')] = i
    ans = 0
    i = 0
    for c in T:
        pos = ord(c) - ord('a')
        if nxt[i][pos] == M:
            return -1
        ans += nxt[i][pos] - i + 1
        i = (nxt[i][pos] + 1) % N
    return ans

print(solve())

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

def main():
    S = input()
    T = input()
    Ls = len(S)
    Lt = len(T)
    d = defaultdict(list)
    for i in range(Ls):
        d[S[i]].append(i+1)

    now = 0
    ans = 0
    for i in range(Lt):
        if not d[T[i]]:
            print(-1)
            exit()
        ni = bisect_right(d[T[i]], now)
        if ni >= len(d[T[i]]):
            now = 0
            ans += Ls
            ni = bisect_right(d[T[i]], now)
            now = d[T[i]][ni]
        else:
            now = d[T[i]][ni]

    ans += now
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



s = input()
t = input()

l = [chr(v) for v in range(ord("a"), ord("z")+1)]
d = {c:i for i,c in enumerate(l)}

def snx(s, target=None, reverse=False, loop=False):
    """文字列sの各要素について、cがiより→で最初に現れる位置n[i][c]
    loop=Trueのとき周回した先のインデックスまで求める
    """
    if target is None:
        target = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:None for c in target}
    nx = [[None]*len(target) for _ in range(len(s))]
    if not reverse:
        i = len(s)-1
        for c in reversed(s):
            d[c] = i
            for j,t in enumerate(target):
                nx[i][j] = d[t]
            i -= 1
        if loop:
            for i in range(len(s)):
                for j in range(len(target)):
                    if nx[i][j] is None:
                        nx[i][j] = nx[0][j]
    else:
        i = 0
        for c in s:
            d[c] = i
            for j,t in enumerate(target):
                nx[i][j] = d[t]
            i += 1
        if loop:
            for i in range(len(s)):
                for j in range(len(target)):
                    if nx[i][j] is None:
                        nx[i][j] = nx[-1][j]
    return nx
nx = snx(s, loop=True)
c = -1
ans = 0
for i in range(len(t)):
    nc = nx[(c+1)%len(nx)][d[t[i]]]
    if nc is None:
        ans = -1
        break
    elif nc>c:
        ans += nc-c
    else:
        ans += nc+len(s)-c
    c = nc
print(ans)

Solution (Python):
from collections import Counter, deque
from bisect import *
alphabets = list("abcdefghijklmnopqrstuvwxyz")
s = input()
t = input()
cs = Counter(list(s))
ct = Counter(list(t))
for char in alphabets:
    if ct[char] > 0 and cs[char]==0:
        print(-1)
        exit()

l_s = len(s)
l_t = len(t)
ss = list(s+s)
c2loc = {char: [] for char in alphabets}
for i in range(l_s*2):
    c2loc[ss[i]].append(i)

ans = 0
now = -1
for i in range(l_t):
    target = t[i]
    target_idxes = c2loc[target]
    idx = bisect_right(target_idxes, now)
    ans += target_idxes[idx] - now
    now = target_idxes[idx]%l_s
print(ans)

Solution (Python):
s=input()
t=input()
ls=len(s)
alpha="abcdefghijklmnopqrstuvwxyz"
c={}
l={}
for i in alpha:
  c[i]=[]
  l[i]=0
  
for i in range(ls):
  c[s[i]].append(i)
  l[s[i]]+=1

f=True
x,y=0,-1
for i in t:
  if l[i]==0:
    f=False
    break
  left,right=-1,l[i]
  while right-left!=1:
    a=(left+right)//2
    if c[i][a]>y:
      right=a
    else:
      left=a
  if right==l[i]:
    x+=1
    y=c[i][0]
  else:
    y=c[i][right]
if f:
  print(x*ls+y+1)
else:
  print(-1)

Solution (Python):

import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)




def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


s = S()
t = S()
set_s = set(s)
set_t = set(t)
if (set_t <= set_s) is False:
    print(-1)
    exit()
alphabet2index = defaultdict(list)
for i, alphabet in enumerate(s):
    alphabet2index[alphabet].append(i+1)
ans = 0
pos = 0
prev_pos = 0
base = 0
n = -1
c = 0
for _t in t:
    n = s.find(_t, n+1)
    if (n == -1):
        c += 1
        n = s.find(_t)
ans = n + c*len(s) + 1
"""

    ng_flg = True
    while ng_flg:
        pos_lis = alphabet2index[_t]
        i = 0
        while len(pos_lis) > i:
            if (pos_lis[i] >= pos):
                pos = pos_lis[i]
                ans += (pos_lis[i]-prev_pos)
                
                prev_pos = pos
                ng_flg = False
                break
            i += 1
        else:
            prev_pos = pos - len(s)
            
            
            pos = 0
    """
print(ans)

Solution (Python):
from math import *
from bisect import *
s=input()
t=input()
n=len(s)
nn=len(t)
ss=[[]for i in range(26)]
tt=[[] for i in range(26)]
ans=0
k=0
for i in range(n):
    ss[ord(s[i])-97].append(i+1)
for i in t:
    j=ss[ord(i)-97]
    if len(j)==0:
        print(-1)
        exit()
    else:
        if j[-1]<=ans:
            ans=j[0]
            k+=1
        else:
            ans=j[bisect(j,ans)]
print(k*n+ans)

Solution (Python):
def Binary_Search_Big_Count(A,x,equal=False,sort=False):
    """2分探索によって,xを超える要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    """

    if sort:
        A.sort()

    if A[-1]<x or ((not equal) and A[-1]==x):
        return 0

    L,R=-1,len(A)-1
    while R-L>1:
        C=L+(R-L)//2
        if A[C]>x or (equal and A[C]==x):
            R=C
        else:
            L=C
    return len(A)-R

def Binary_Search_High_Value(A,x,equal=False,sort=False):
    """Aのxを超える要素の中で最小のものを出力する.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    ※全ての要素がx以上(超える)場合はNoneが返される.
    """

    if sort:
        A.sort()

    K=Binary_Search_Big_Count(A,x,equal=equal,sort=False)
    if K:
        return A[-K]
    else:
        return None

S=input()
T=input()

N=len(S)

if not(set(S)>=set(T)):
    print(-1)
    exit()

D={x:[] for x in set(S)}

for i in range(N):
    D[S[i]].append(i)


X=0
A=-1
for t in T:
    P=Binary_Search_High_Value(D[t],A)

    if P==None:
        X+=1
        A=D[t][0]
    else:
        A=P

print(N*X+A+1)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect
    
    mod=10**9+7
    s=input()
    t=input()
    
    L=[[]for _ in range(26)]
    
    N=len(s)
    for i in range(N):
        c=ord(s[i])-97
        L[c].append(i)
        
    cur=-1
    rep=0
    
    M=len(t)
    for i in range(M):
        c=ord(t[i])-97
        if len(L[c])==0:
            print(-1)
            exit()
            
        num=bisect.bisect_right(L[c],cur)
        if num>=len(L[c]):
            rep+=1
            num=0
        cur=L[c][num]
        
    ans=N*rep + cur + 1
    print(ans)
        
        
        

main()

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

Solution (Python):
def abc138_e():
    s = str(input())
    t = str(input())
    sd = dict()
    for i, c in enumerate(s):
        if sd.get(c) == None: sd[c] = []
        sd[c].append(i)
    from bisect import bisect_left
    k = 0
    p = 0
    for c in t:
        if sd.get(c) == None: return print(-1)
        idx = bisect_left(sd[c], p)
        if idx == len(sd[c]):
            k += 1
            p = 0
            idx = bisect_left(sd[c], p)
        p = sd[c][idx] + 1
    ans = k * len(s) + p
    return print(ans)

if __name__ == '__main__':
    abc138_e()

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


def solve(s, t):
    dd = defaultdict(list)
    for i, c in enumerate(s):
        dd[c].append(i)
    inv = 0
    index = 0
    for c in t:
        x = bisect_left(dd[c], index)
        if x == len(dd[c]):
            inv += 1
            if not dd[c]:
                return -1
            index = dd[c][0] + 1
        else:
            index = dd[c][x] + 1
    return len(s) * inv + index


def main():
    s = input()
    t = input()
    print(solve(s, t))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import bisect

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

dict = defaultdict(list)
for i, c in enumerate(S):
    dict[c].append(i + 1)



div_cnt = 0

now = 0

for i, c in enumerate(T):

    
    if dict[c] == []:
        print(-1)
        exit()

    next = bisect.bisect_right(dict[c], now)
    

    
    
    if next == len(dict[c]):
        div_cnt += 1
        now = dict[c][0]
    
    else:
        now = dict[c][next]

ans = div_cnt * len(S) + now
print(ans)

Solution (Python):
import bisect

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 + 1)




div_cnt = 0

now = 0

for c in T:
    
    j = ord(c) - ord('a')

    
    if len(X[j]) == 0:
        print(-1)
        exit()

    next = bisect.bisect_right(X[j], now)
    

    if next == len(X[j]):
        div_cnt += 1
        now = X[j][0]
    else:
        now = X[j][next]

ans = div_cnt * len(S) + now
print(ans)

Solution (Python):
import bisect

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 + 1)

q = 0
r = 0

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 * len(S) + r
print(ans)

Solution (Python):
from collections import defaultdict
import copy
import sys
s = input()
n_s = len(s)
t = input()
n_t = len(t)

chr_firstind = defaultdict(lambda:-1)
chr_nextind = defaultdict(lambda:-1)
i_to_chr_nextind = [0] * n_s
for i in range(n_s-1,-1,-1):
    chr_firstind[s[i]] = i
    i_to_chr_nextind[i] = copy.copy(chr_nextind)
    chr_nextind[s[i]] = i 

first_target = t[0]
previous_ind = chr_firstind[first_target]
if previous_ind == -1:
    print(-1)
    sys.exit()
if n_t == 1:
    print(previous_ind+1)
    sys.exit()
s_used = 0
for i in range(1,n_t):
    
    d = i_to_chr_nextind[previous_ind]
    next_ind = d[t[i]]
    if next_ind == -1:
        s_used += 1
        next_ind = chr_firstind[t[i]]
        if next_ind == -1:
            print(-1)
            sys.exit()
    previous_ind = next_ind
print(n_s*s_used+previous_ind+1)

Solution (Python):
import bisect


d = {}
key = list("abcdefghijklmnopqrstuvwxyz")
for i in range(26):
    d[key[i]] = []


S = list(input())
N = len(S)

T = list(input())
M = len(T)

for i in range(N):
    d[S[i]].append(i + 1)



S_set = set(S)

ans = 0
now = 0

for i in range(M):
    if T[i] in S_set:
        next = bisect.bisect_right(d[T[i]], now)
        
        
        if next < len(d[T[i]]):
            now = d[T[i]][next]
        
        else:
            now = d[T[i]][0]
            ans += N
    else:
        print(-1)
        exit()

ans += now
print(ans)

Solution (Python):
from bisect import*
s=input()
t=input()
n=len(s)
d=dict(zip([chr(i+97) for i in range(26)],[[] for _ in range(26)]))
for i,j in enumerate(s,1):
  d[j]+=[i]
ans=0
cnt=0
for i in t:
  if d[i]:
    j=bisect(d[i],ans)
    if j==len(d[i]):
      cnt+=1
      ans=d[i][0]
    else:ans=d[i][j]
  else:
    cnt,ans=0,-1
    break
print(cnt*n+ans)

Solution (Python):

import collections,math
s = input()
t = input()




ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0
for t_key,t_val in lt.items():
    if t_key not in ls:
        print(-1)
        exit()


cnt = 0
tt = list(t[::-1])
idx=0
ss = s
while tt!=[]:
    next_t = tt.pop()
    idx=ss.find(next_t)
    if idx == -1:
        cnt += len(ss)
        idx = s.find(next_t)
        ss = s[idx+1:]
        cnt += idx+1 
    else:
        cnt += idx+1 
        ss = ss[idx+1:]
print(cnt)

Solution (Python):
import collections,math
s = input()
t = input()




ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0
for t_key,t_val in lt.items():
    if t_key not in ls:
        print(-1)
        exit()


cnt = 0
tt = list(t[::-1])
idx=0
ss = s
while tt!=[]:
    next_t = tt.pop()
    idx=ss.find(next_t)
    if idx == -1:
        cnt += len(ss)
        idx = s.find(next_t)
        ss = s[idx+1:]
        cnt += idx+1
    else:
        cnt += idx+1
        ss = ss[idx+1:]
print(cnt)