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.



Sample input:
contest
son


Sample output:
10

Submission status: Accepted

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

# next[i][c] = k : i文字目以降で最初にcが現れるのはk文字目 である (i < |s|)
N = len(s)
next = [dict() for _ in range(N)]
last = dict()
for i, c in enumerate(s + s):
    last_c = last[c] if last.get(c) is not None else -1
    for j in range(last_c + 1, min(i + 1, N)):
        next[j][c] = i % N
    last[c] = i

i = -1
for c in t:
    cur = i % N
    cur1 = (i + 1) % N
    if next[cur1].get(c) is None:
        print(-1)
        exit(0)
    n = next[cur1][c]
    if cur < n:
        i += n - cur
    elif n < cur:
        i += N - (cur - n)
    else:
        i += N
print(i + 1)

Submission status: Accepted

Solution code:
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    for i in d:
        d[i] = sorted(d[i])
    m = 0
    j = 0
    for i in t:
        ind = bisect.bisect_left(d[i], j)
        m += d[i][ind] - j + 1
        if d[i][ind] >= n:
            j = d[i][ind] - n + 1
        else:
            j = d[i][ind] + 1
    return m
print(main())

Submission status: Accepted

Solution code:
def main():
    S = list(map(lambda x: ord(x) - 97, input()))
    T = list(map(lambda x: ord(x) - 97, input()))
    if not set(T) <= set(S):
        return -1

    tbl = [-1] * 26
    st = [None] * (len(S) + 1)
    for i, s in reversed(list(enumerate(S))):
        st[i + 1] = tuple(tbl)
        tbl[s] = i
    st[0] = tuple(tbl)
    r = 0
    c = 0
    for t in T:
        if st[r][t] == -1:
            c += 1
            r = 0
        r = st[r][t] + 1
    return c * len(S) + r

print(main())

Submission status: Accepted

Solution code:
import bisect
INF = 10 ** 10
s = input()
t = input()
moji = [[] for _ in range(26)]

for i, m in enumerate(s):
    moji[ord(m) - ord("a")].append(i)

for i in range(26):
    moji[i].sort()

moji_o = [0 for _ in range(len(t))]

cnt = 0
ans = 1
# print(moji)
for i, m in enumerate(t):
    if len(moji[ord(m) - ord("a")]) == 0:
        ans = -1
        break
    if i == 0:
        moji_o[i] = moji[ord(m) - ord("a")][0]
    else:
        if moji_o[i - 1] >= moji[ord(m) - ord("a")][-1]:
            moji_o[i] =  moji[ord(m) - ord("a")][0]
        else:
            tmp = bisect.bisect_right(moji[ord(m) - ord("a")], moji_o[i - 1])
            if tmp == 0:
                moji_o[i] = moji[ord(m) - ord("a")][0]
            else:
                moji_o[i] = moji[ord(m) - ord("a")][tmp]
# print(moji_o)
for i in range(1, len(moji_o)):
    if ans == -1:
        break
    if moji_o[i - 1] >= moji_o[i]:
        cnt += 1

if ans == -1:
    print(-1)
else:
    print(cnt * len(s) + moji_o[-1] + 1)

Submission status: Accepted

Solution code:
s = input()
t = input()
d = {i:[] for i in "abcdefghijklmnopqrstuvwxyz"}
for i in range(len(s)):
    d[s[i]].append(i)
for i in t:
    if len(d[i]) == 0:
        print(-1)
        exit()

def binary_search(arr, k):
    l, r = 0, len(arr)-1
    while l <= r:
        m = l+r >> 1
        if arr[m] < k:
            l = m+1
        else:
            r = m-1
    return l

a, b = 0, 0
for i in t:
    j = binary_search(d[i], a)
    if len(d[i]) <= j:
        a = 0
        b += 1
        j = binary_search(d[i], 0)
    a = d[i][j] + 1
print(b * len(s) + a)

Submission status: Accepted

Solution code:
s = input()
t = input()
d = {i:[] for i in "abcdefghijklmnopqrstuvwxyz"}
for i in range(len(s)):
    d[s[i]].append(i)
for i in t:
    if len(d[i]) == 0:
        print(-1)
        exit()

def binary_search(arr, k):
    l, r = 0, len(arr)-1
    while l <= r:
        m = l+r >> 1
        if arr[m] < k:
            l = m+1
        else:
            r = m-1
    return l

a, b = 0, 0
for i in t:
    j = binary_search(d[i], a)
    if len(d[i]) <= j:
        a = 0
        b += 1
        j = binary_search(d[i], 0)
    a = d[i][j] + 1
print(b * len(s) + a)

Submission status: Accepted

Solution code:
import bisect
a = input()
b = input()
dp = [[] for _ in range(26)]
# print(dp)

for e,i in enumerate(a):
    t=ord(i)-ord('a')
    dp[t].append(e)
# print(dp)
f = 0
ans = 0
c = 0 
for e,i in enumerate(b):
    t = ord(i)-ord('a')
    if not dp[t]:
        print(-1)
        exit()
    i_i = bisect.bisect_left(dp[t],f)
    if len(dp[t])<=i_i:
        F = dp[t][0] 
        ans+=F+1
        c +=1
    else:
        F = dp[t][i_i]
        ans += F-f+1
    f = F+1
    # print(dp[t],f,F,ans)
    if e == len(b)-1: ans = c*len(a)+ F+1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect

def indexes(L, x):
    INDEXES = []
    for i in range(len(L)):
        if L[i] == x:
            INDEXES.append(i)
    return INDEXES


s = input()
t = input()

ss = s * 2
alphabets = "abcdefghijklmnopqrstuvwxyz"
INDEXES = {c:indexes(ss, c) for c in alphabets}

def index(i, c):
    return INDEXES[c][bisect(INDEXES[c], i)]

if not INDEXES[t[0]]:
    print(-1)
    exit()
now = INDEXES[t[0]][0]

answer = now + 1
mod = len(s)
for c in t[1:]:
    if not INDEXES[c]:
        print(-1)
        exit()
    next = index(now, c)
    answer += next - now
    now = next % mod

print(answer)

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()

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

    s_indexes = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, s_c in enumerate(s):
        s_indexes[s_c].append(i)
    s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
    s_length = {c: len(s_indexes[c]) for c in "abcdefghijklmnopqrstuvwxyz"}

    power = 0
    last_index = -1
    for i, t_c in enumerate(t):
        if s_length[t_c] <= s_pointer[t_c]:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1
        elif s_indexes[t_c][s_pointer[t_c]] <= last_index:
            for j in range(s_pointer[t_c], s_length[t_c]):
                if last_index < s_indexes[t_c][j]:
                    s_pointer[t_c] = j
                    break
            else:
                # reset
                s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
                power += 1

        last_index = s_indexes[t_c][s_pointer[t_c]]
        s_pointer[t_c] += 1

    print(len(s) * power + last_index + 1)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s = input()
t = input()
dicta = defaultdict(list)
for a,b in enumerate(s):
    dicta[b] += [a]
snow = -1
count = 0
flag = True
for i in t:
    if not dicta[i]:
        flag = False
        break
    nowt = dicta[i]
    snowind = bisect.bisect_right(nowt,snow)
    if snowind == len(nowt):
        count += 1
        snow = nowt[0]
    else:
        snow = nowt[snowind]
if flag:
    print(len(s)*count+snow +1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s = input()
t = input()
dicta = defaultdict(list)
for a,b in enumerate(s):
    dicta[b] += [a]
snow = -1
count = 0
flag = True
for i in t:
    if i not in s:
        flag = False
        break
    nowt = dicta[i]
    snowind = bisect.bisect_right(nowt,snow)
    if snowind == len(nowt):
        count += 1
        snow = nowt[0]
    else:
        snow = nowt[snowind]
if flag:
    print(len(s)*count+snow +1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s = input()
t = input()
dicta = defaultdict(list)
for i in range(len(s)):
    dicta[s[i]] += [i]
snow = -1
count = 0
flag = True
for i in t:
    if i not in s:
        flag = False
        break
    nowt = dicta[i]
    snowind = bisect.bisect_right(nowt,snow)
    if snowind == len(nowt):
        count += 1
        snow = nowt[0]
    else:
        snow = nowt[snowind]
if flag:
    print(len(s)*count+snow +1)
else:
    print(-1)

Submission status: Accepted

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
if t[0] not in s:
    print(-1)
else:
    snow = s.index(t[0])
    while True:
        tcount += 1
        if tcount == lent:
            break
        if t[tcount] in s[snow+1:]:
            snow = s[snow+1:].index(t[tcount])+snow+1
        elif t[tcount] in s:
            snow = s.index(t[tcount])
            count += 1
        else:
            flag = False
            break
    if flag:
        print(count*len(s) + snow+1)
    else:
        print(-1)

Submission status: Accepted

Solution code:
from bisect import bisect_right
def find_gt(a, x):
  i = bisect_right(a, x)
  if i != len(a):
    return a[i]
  print(-1)
  exit()

S = list(map(lambda x: ord(x) - ord("a"), input())) * 2
T = list(map(lambda x: ord(x) - ord("a"), input()))

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

for i in range(len(S)):
  l[S[i]].append(i)

ans = 0
cur = -1

for i in range(len(T)):
  fge = find_gt(l[T[i]], cur)
  ans += fge - cur
  cur = fge
  if cur >= len(S)//2:
    cur -= len(S)//2

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

S = list(input().strip())
T = list(input().strip())

s = set(S)
t = set(T)
f = True
for v in t:
    if v not in s:
        f = False
        break
if f == False:
    print(-1)
    exit()

m = defaultdict(list)
for i in range(len(S)):
    m[S[i]].append(i)

counter = 0
before = -1
for v in T:
    c = m[v]
    index = bisect.bisect_left(c, before+1)
    if index >= len(c):
        before = -1
        index = bisect.bisect_left(c, before+1)
        before = c[index]
        counter += 1
    else:
        before = c[index]

print(counter * len(S) + before + 1)

Submission status: Accepted

Solution code:
import bisect

REPEAT_NUM = 10 ** 100

S = input()
T = input()
lenS = len(S)
lenT = len(T)

idxes_S = {}
for idx, s in enumerate(S):
    if s not in idxes_S:
        idxes_S[s] = []
    idxes_S[s].append(idx)

idx_s = -1
idx_t = 0
while idx_t < lenT and idx_s < lenS * REPEAT_NUM:
    if T[idx_t] not in idxes_S:
        print(-1)
        exit()
    else:
        tmp_idx = bisect.bisect(idxes_S[T[idx_t]], idx_s % lenS)
        if len(idxes_S[T[idx_t]]) == tmp_idx:
            idx_s += lenS - idx_s % lenS + idxes_S[T[idx_t]][0]
        else:
            idx_s += idxes_S[T[idx_t]][tmp_idx] - idx_s % lenS
        idx_t += 1

if idx_t == lenT:
    print(idx_s + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

S=input()
T=input()
lenS=len(S)

NX=[[-1]*26 for _ in range(len(S))]

for i in range(len(S)*2-1)[::-1]:
    idx = i%lenS
    idx2 = (i+1)%lenS
    for j in range(26):
        if NX[idx2][j] != -1:
            NX[idx][j] = NX[idx2][j] + 1
    NX[idx][ord(S[idx2])%26] = 1

# for lis in NX:
#     print(lis)
# for c in S:
#     print(ord(c)%26, end=" ")
# print("")

res = 0
prev=lenS-1
for c in T:
    v = NX[prev][ord(c)%26]
    if v == -1:
        print(-1)
        exit()
    else:
        res += v
        prev = (prev + v)%lenS

print(res)

Submission status: Accepted

Solution code:
import sys
import bisect
def input():
    return sys.stdin.readline()[:-1]
s=input()
t=input()
ss=s+s
al=[-1]*26
for i in range(len(ss)):
    tmp=ord(ss[i])-ord("a")
    if al[tmp]==-1:
        al[tmp]=[i]
    else:
        al[tmp].append(i)
ans=0
now=0
for i in range(len(t)):
    tmp=ord(t[i])-ord("a")
    if al[tmp]==-1:
        print(-1)
        exit()
    tmp2=bisect.bisect_left(al[tmp],now)
    # print(al[tmp],tmp2)
    ans+=al[tmp][tmp2]-now+1
    now=al[tmp][tmp2]+1
    if now>=len(s):
        now-=len(s)
    # print(ans,now)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = input().strip()
t = input().strip()
D = {}
for i in range(len(s)):
    a = s[i]
    if a not in D:
        D[a] = []
    D[a].append(i+1)
A = sorted(list(set(list(s))))
A.append(chr(123))
B = sorted(list(set(list(t))))
cur = 0
flag = 0
for i in range(len(B)):
    while True:
        if A[cur]<B[i]:
            cur += 1
        elif A[cur]==B[i]:
            break
        else:
            flag = 1
            break
    if flag==1:break
if flag==1:
    print(-1)
else:
    C = []
    cur = -1
    for i in range(len(t)):
        b = t[i]
        ind = bisect_right(D[b],cur)%len(D[b])
        C.append(D[b][ind])
        cur = D[b][ind]
    cnt = 0
    for j in range(1,len(C)):
        if C[j]<=C[j-1]:
            cnt += 1
    print(len(s)*cnt+C[-1])

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())


def n(i):
    return ord(i) - 97


ss = set(s)
ts = set(t)
if not ts.issubset(ss):
    print(-1)
else:
    # mapping
    sp = s + s
    mp = [[-1] * 26 for _ in range(len(sp) + 1)]
    for i in range(len(sp) - 1, -1, -1):
        for j in range(26):
            if mp[i + 1][j] > -1:
                mp[i][j] = mp[i + 1][j] + 1
            mp[i][n(sp[i])] = 0
    i = 0
    im = 0
    for c in t:
        cn = n(c)
        i += mp[im][cn] + 1
        im = i % len(s)
    print(i)

Submission status: Accepted

Solution code:
import collections
import bisect
S = input()
T = input()
N = len(S)
 
d = collections.defaultdict(list)
for i, s in enumerate(S):
  d[s].append(i + 1)

ans = 0
end = 0
isOK = True
i = 0

for t in T:
  if len(d[t])==0: # 存在しない文字ならFalse
    isOK = False
    break
  dic = d[t]
  idx = bisect.bisect_right(dic, i) # i番目以降におけるtの出現位置を取得(O(logN))
  if len(dic) == idx:
    i = dic[0]  # iをtのあるところに動かす
    end += 1    # 端に到達したら，繰り返し数を増やす
  else:
    i = dic[idx]# iをtのあるところに動かす

if isOK:
  ans = N * end + i
else:
  ans = -1
    
print(ans)

Submission status: Accepted

Solution code:
import collections
import bisect
S = input()
T = input()
N = len(S)

d = collections.defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i + 1)

ans = 0
end = 0
isOK = True
i = 0

for t in T:
    if len(d[t]) == 0:
        isOK = False
        break
    dic = d[t]
    idx = bisect.bisect_right(dic, i)
    if len(dic) == idx:
        i = dic[0]
        end += 1
    else:
        i = dic[idx]

if isOK:
    ans = N * end + i
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
sl = list(input())
tl = list(input())

n = len(sl)
from collections import defaultdict
dic = defaultdict(list) 

for idx, s in enumerate(sl):
   dic[s].append(idx)
   dic[s].append(idx+n)

for s in dic:
   dic[s] = sorted(dic[s])

import bisect

ans = 0
now = -1
for t in tl:
   if dic[t] == []:
      print(-1)
      import sys
      sys.exit()
   idx = bisect.bisect_left(dic[t], now+1)
   ans += dic[t][idx] - now
   now = dic[t][idx]
   if now >= n:
      now -= n
print(ans)

Submission status: Accepted

Solution code:
#dictでよかったかも？
import bisect

s=input()
t=input()

#a,b,cの出てきたところを小さい順にメモ
alp=[[] for i in range(26)]

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

#alp[w]の中からnow以降のものを探す．なければ一番手前を．
def bi_search(now,w):
    r=0
    if now>=alp[w][-1]:
        now=-1
        r=1
    ne_i=bisect.bisect_right(alp[w],now)
    ne=alp[w][ne_i]
    return ne,r

    
ans=0
rep=0
now=-1#s上の何文字目か
for i in range(len(t)):
    num=ord(t[i])-ord("a")
    if len(alp[num])==0:
        ans=-1
        break
    now,r=bi_search(now,num)
    rep+=r
if ans==-1:
    print(ans)
else:
    ans=rep*len(s)+now+1
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

d=defaultdict(list)

s=input()
t=input()

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

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

for k,v in d.items():
  d[k].append(ns)
#print(d)

ans=0
cnt=-1

for i in range(nt):
  tt=d[t[i]]
#  print(t[i],tt,ans,cnt)
  if tt==[]:
    print(-1)
    exit(0)
  else:
    a=bisect.bisect_right(tt,cnt)
#    print("ind",a)
    if tt[a]==ns:
      ans+=ns+tt[0]-cnt
      cnt=tt[0]
    else:
      ans+=tt[a]-cnt
      cnt=tt[a]
      
print(ans)

Submission status: Accepted

Solution code:
import bisect

S = input()
T = input()

ls = len(S)
d = {}
for i, s in enumerate(S):
  if s in d:
    d[s].append(i+1)
  else:
    d[s] = [i+1]


now = 0
ans = 0
pre_t = ''
for t in T:
  if not t in d:
    ans = -1
    break
    
  if t == pre_t:
    idx = bisect.bisect_left(d[t], now+1)
  else:
    idx = bisect.bisect_left(d[t], now)

  if idx == len(d[t]):
    idx = 0
  
  if d[t][idx] > now:
    ans += d[t][idx] - now
  else:
    ans += ls + d[t][idx] - now
  
  now = d[t][idx]
  pre_t = t

print(ans)

Submission status: Accepted

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

pos = 0
itr = 0

S = set(s)
T = set(t)

if S>=T:
    for i in t:
        pos = s.find(i,pos) 
        if pos < 0:
            itr += 1
            pos = s.find(i) + 1
        else:
            pos += 1
    print(itr*len(s)+pos)

else:
    print(-1)

Submission status: Accepted

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

if len(set(t)-set(s))>0:
  print(-1)
else:
  s2=s*2
  s2pos={}
  for i in range(len(s2)):
    if s2[i] in s2pos:
      s2pos[s2[i]].append(i)
    else:
      s2pos[s2[i]]=[i]

  cur=-1
  import bisect
  rev=0
  for c in t:
    cur+=1
    pos=s2pos[c]
    p=bisect.bisect_left(pos,cur)
    cur=pos[p]
    if cur>=len(s):
      cur-=len(s)
      rev+=1
  else:
    print(rev*len(s)+cur+1)

Submission status: Accepted

Solution code:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
  exit(0)

ss=s*2
ind=-1
turn=0
for c in t:
  nex=ss[ind+1:].find(c)
  ind=(ind+1)+nex
  if ind>=len(s):
    ind-=len(s)
    turn+=1

print(turn*len(s)+ind+1)

Submission status: Accepted

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

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

times = 0
cs = 0
for c in t:
    if c not in D.keys():
        print(-1)
        exit()
    else:
        i = bisect.bisect_left(D[c], cs+1)
        if i == len(D[c]):
            times += 1
            cs = D[c][0]
        else:
            cs = D[c][i]
print(times*len(s)+cs)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

ss = s+s

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

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

ans = 0
tmp = 0

for i in range(len(t)):
    if not char[ord(t[i])-97]:
        print(-1)
        break
    
    k = bisect.bisect_right(char[ord(t[i])-97],tmp)
    ans += char[ord(t[i])-97][k]-tmp
    tmp = char[ord(t[i])-97][k]
    if tmp-len(s)>0:
        tmp -= len(s)
    
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
from bisect import bisect
def resolve():
    S=input()
    T=input()

    if(len(set(S))!=len(set(S+T))):
        print("-1")
        return

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

    now=-1
    n=len(S)
    for t in T:
        i=bisect(idx[t],now%n)
        now+=idx[t][i]-now%n

    print(now+1)
resolve()

Submission status: Accepted

Solution code:
# Library
import bisect

alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = -1
cir = 0
letter = []
res = 0

for i in range(len(ss)):
    letter.append([ss[i], i])

# Sort出来る.
letter.sort()

for i in range(len(t)):
    search = [t[i], index]
    tmp_ind = bisect.bisect(letter, search)
    # print("now searching " + str(search))
    # print("find: " + str(tmp_ind))
    # print("found: " + str(letter[tmp_ind]))
    if tmp_ind == len(ss):
        res = -1
        break
    if t[i] != letter[tmp_ind][0]:
        # Not exist
        res = -1
        break
    index += (letter[tmp_ind][1] - index)
    if index >= len(s):
        cir += 1
        index -= len(s)
    # print("cir,index : " + str(cir) + " " + str(index))
    res = cir * len(s) + index + 1

print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict


def solve():
    s = input()
    t = input()

    n = len(s)
    index = defaultdict(list)
    for i, char in enumerate(s):
        index[char] += [i]
    
    cur, orbit = -1, 0
    for char in t:
        target = index[char]
        if not target:
            print(-1)
            exit()
        
        i = bisect_left(target, cur + 1)
        if i < len(target):
            cur = target[i]
        else:
            cur = target[0]
            orbit += 1
    print(n*orbit + cur + 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
t = input()

# ord('a') == 97 
abc = [[] for i in range(26)]
for i,j in enumerate(s):
    tmp = ord(j) - 97
    abc[tmp].append(i)
ln = [0] * 26
for i,j in enumerate(abc):
    ln[i] = len(j)
    # print(abc[i],ln[i])
count = 0
p = -1
for i,j in enumerate(t):
    tmp = ord(j) - 97
    if not abc[tmp]:
        print(-1)
        break
    c = bisect.bisect_left(abc[tmp],p+1)
    # print(c)
    if c == ln[tmp]:
        count += 1
        p = abc[tmp][0]
    else:
        p = abc[tmp][c]
else:
    print(count * len(s) + p + 1)

Submission status: Accepted

Solution code:
s=input()
t=input()
a=-1
c=0
if not set(t)<=set(s):print(-1);exit()
for i in t:
  a=s.find(i,a+1)
  if a==-1:
    c+=1
    a=s.find(i)
print(c*len(s)+a+1)

Submission status: Accepted

Solution code:
import sys
import bisect
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    s = str(readline().rstrip().decode('utf-8'))
    d = collections.defaultdict(list)
    for i in range(len(s)):
        d[s[i]] += [i]
    loop = 0
    pos = 0
    t = str(readline().rstrip().decode('utf-8'))
    for i in range(len(t)):
        if t[i] in d:
            pos = bisect.bisect_left(d[t[i]], pos)
            if pos == len(d[t[i]]):
                loop += 1
                pos = 0
                pos = bisect.bisect_left(d[t[i]], pos)
            pos = d[t[i]][pos] + 1
        else:
            print(-1)
            exit()
    print(loop * len(s) + pos)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
from bisect import bisect_left
def resolve():
    S,T=input(),input()
    if(not (set(S)>=set(T))):
        print(-1)
        return

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

    n=len(S)
    now=0
    ans=0
    for t in T:
        i=bisect_left(D[t],now)
        ans+=D[t][i]-now+1
        now=(D[t][i]+1)%n
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
from bisect import bisect_left


s = input().rstrip("\n")
len_s = len(s)
t = input().rstrip("\n")
len_t = len(t)

alpha = defaultdict(list)
for i in range(len_s):
    alpha[s[i]].append(i)

if not alpha[t[0]]:
    print(-1)
    exit()
else:
    now_index = alpha[t[0]][0]
    answer = now_index + 1

# O(|t|)
for i in range(1,len_t):
    index = alpha[t[i]]
    if not index:
        print(-1)
        exit()
    # O(log(index))
    next_index = bisect_left(index, now_index+1)
    # s[now_index+1:]にt[i]がある場合
    if next_index < len(index):
        answer += index[next_index] - now_index
        now_index = index[next_index]
    else:
        answer += (len_s -1) - now_index + (index[0] + 1)
        now_index = index[0]

print(answer)

Submission status: Accepted

Solution code:
def main():
  import bisect
  s = input()
  t = input()
  al = [[] for _ in range(26)]
  for i in range(len(s)):
    al[ord(s[i])-97].append(i)
  #print(al)
  ans = 0
  std = -1
  for i in range(len(t)):
    x = al[ord(t[i])-97]
    if not x:
      print(-1)
      exit()
    y = bisect.bisect_left(x,std+1)
    if y == len(x):
      ans += len(s) - std + x[0]
      std = x[0]
    else:
      ans += al[ord(t[i])-97][y] - std 
      std = al[ord(t[i])-97][y]
  print(ans)
main()

Submission status: Accepted

Solution code:
import bisect
S = input()
T = input()
OUT = 10**5

N = len(S)
M = len(T)
indice = [0]*M
# 素直にやるとO(NM)かかるので工夫が必要
A = [[] for _ in range(26)]
for i in range(N):
    A[ord(S[i]) - ord('a')].append(i + 1)

res = 0
b = 0
for j in range(M):
    tj = ord(T[j]) - ord('a')
    if len(A[tj]) == 0:
        print(-1)
        exit()
    r = bisect.bisect_right(A[tj], b)
    if len(A[tj]) > r:
        res += A[tj][r] - b
        b = A[tj][r]
    else:
        res += N - b + A[tj][0]
        b = A[tj][0]

print(res)

Submission status: Accepted

Solution code:
import bisect
s=input()
L=len(s)
s*=2
t=input()
pl={chr(i+97):[] for i in range(26)}
for i in range(len(s)):
  pl[s[i]]+=[i]
cnt=0
rem=0
for i in t:
  if pl[i]==[]:print(-1);exit()
  cnt+=pl[i][bisect.bisect_right(pl[i],rem-1)]-(rem-1)
  rem=cnt%L
print(cnt)

Submission status: Accepted

Solution code:
import bisect
S = list(input())
T = list(input())
s_dict = {}
# 二週分の文字とインデックス番号の組み合わせを保持
for s in S:
    s_dict[s] = []
for i, s in enumerate(S+S):
    bisect.insort_right(s_dict[s], i)

N = len(S)
try:
    ret = 0
    cnt = 0
    pre_t_idx = -1
    for t in T:
        t_idx = s_dict[t][bisect.bisect_right(s_dict[t], pre_t_idx)]
        if t_idx > N-1:
            cnt += 1
            t_idx -= N
        ret = t_idx+1
        pre_t_idx = t_idx

    print(cnt*N+ret)
except Exception as e:
    print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

S = input()
T = input()
lenS = len(S)
if set(S) >= set(T):
    SS = S + S
    pos = defaultdict(list)
    for i, s in enumerate(SS): pos[s].append(i)
    ans = -1
    for t in T:
        lb = (ans + 1) % lenS
        nxt = bisect_left(pos[t], lb)
        ans += pos[t][nxt] - lb + 1
    ans += 1
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

S = input()
T = input()

SS = S + S
lens = len(S)

index = defaultdict(list) # alphabet to indices

for i, ss in enumerate(SS):
    index[ss].append(i)

x = -1 
for t in T:
    arr = index[t]
    if len(arr) == 0:
        x = -2
        break
    y = (x + 1) % lens
    i = bisect_left(arr, y)
#    print(arr, i, y)
    x = (x + 1) + arr[i] - y
    
answer = x + 1
print(answer)

Submission status: Accepted

Solution code:
#%%

#%%
import bisect
s = list(input())
t = list(input())
alpha2num = lambda c: ord(c) - ord('a')
count = [0] * 26
count_t = [0] * 26
ind = [[] for _ in range(26)]
for i in range(len(s)):
    count[alpha2num(s[i])] += 1
    ind[alpha2num(s[i])].append(i)
for i in range(len(t)):
    count_t[alpha2num(t[i])] += 1

flag = True
for i in range(26):
    if count_t[i] >= 1 and count[i] == 0:
        flag = False

if flag:
    ans = 0
    tmp = -1
    i = 0
    while True:
        a = bisect.bisect_right(ind[alpha2num(t[i])], tmp)
        #print(i, tmp, a)
        if 0 <= a < count[alpha2num(t[i])]:
            tmp = ind[alpha2num(t[i])][a]
            i += 1
        else:
            tmp = -1
            ans += 1
        if i >= len(t):
            break
    ans = ans * len(s) + tmp + 1
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
#from string import ascii_lowercase
from bisect import bisect_right
s = input()
t = input()
p = {c: [] for c in s}
for x, c in enumerate(s):
    p[c].append(x)
z = 0
l = -1
for c in t:
    if c not in p:
        print(-1)
        exit()
    x = bisect_right(p[c], l)
    if x == len(p[c]):
        x = 0
        z += 1
    l = p[c][x]

print(z * len(s) + l + 1)

Submission status: Accepted

Solution code:
#from string import ascii_lowercase
from bisect import bisect_right
s = input()
t = input()
p = {c: [] for c in s}
for x, c in enumerate(s):
    p[c].append(x)
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)

Submission status: Accepted

Solution code:
from string import ascii_lowercase
from bisect import bisect_right
s = input()
t = input()
p = {c: [] for c in s}
for x, c in enumerate(s):
    p[c].append(x)
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)