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:
#!/usr/bin/env python3
 
# 以下を記述しないとTLEになる, 何故？
import numpy
import itertools
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
def main():
    s = list(input())
    t = list(input())
    dic_s = defaultdict(list)
    for i in range(len(s)):
        dic_s[s[i]].append(i)
    x,y = 0,-1
    for i in range(len(t)):
        if dic_s[t[i]] == []:
            print(-1)
            return
        next_y = bisect.bisect_left(dic_s[t[i]],y+1)
        if next_y == len(dic_s[t[i]]):
            x += 1
            y = dic_s[t[i]][0]
        else:
            y = dic_s[t[i]][next_y]
    print(x*len(s)+y+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
# 以下を記述しないとTLEになる, 何故？
import math
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
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

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
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()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import bisect

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

x = [[] for j in range(26)]

for i, s in enumerate(S):
    x[ord(s) - ord('a')].append(i)

sett = list(set(T))

for t in sett:
    if len(x[ord(t) - ord('a')]) == 0:
        print(-1)
        exit()

c = 0
z = 0

for t in T:
    y = bisect.bisect_left(x[ord(t) - ord('a')], c)
    if y == len(x[ord(t) - ord('a')]):
        z += 1
        c = x[ord(t) - ord('a')][0] + 1
    else:
        c = x[ord(t) - ord('a')][y] + 1

print(z * len(S) + c)

Submission status: Accepted

Solution code:
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7
alphabet = [chr(i) for i in range(97, 97 + 26)]


def resolve():
    S = input()
    T = input()

    n = len(S)
    m = len(T)

    idx = [[] for _ in range(26)]
    for i in range(n):
        idx[alphabet.index(S[i])].append(i)

    for i in range(n):
        idx[alphabet.index(S[i])].append(i + n)

    res = 0
    pos = 0
    for i in range(m):
        c = alphabet.index(T[i])
        if len(idx[c]) == 0:
            print(-1)
            break
        pos = idx[c][bisect.bisect_left(idx[c], pos)] + 1
        if pos >= n:
            pos -= n
            res += n
    else:
        res += pos
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect
from collections import Counter
from collections import defaultdict
s=input()
t=input()
#s="contest"
#t="antakuso"
sd=Counter(s)
td=Counter(t)
N=len(t)
Ns=len(s)
for ts in td:
    if ts not in sd:
        print(-1)
        exit()
D=defaultdict(list)
for i in range(Ns):
    D[s[i]].append(i)
ans=0
for i in range(N):
    if i==0:
        pre=min(D[t[i]])
    else:
        L=D[t[i]]
        idx=bisect.bisect(L,pre)
        if idx==len(L):
            ans+=Ns
            pre=min(L)
        else:
            pre=L[idx]
    if i==N-1:
        ans+=pre+1
print(ans)

Submission status: Accepted

Solution code:
S = list(input())
T = list(input())

S = [ord(s)-97 for s in S]
T = [ord(t)-97 for t in T]

N = len(S)

dp = [[-1 for j in range(26)] for i in range(N)]

for i,s in enumerate(S):
    if dp[N-1][s] == -1:
        dp[N-1][s] = i

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

M = len(T)
ans = dp[N-1][T[0]] + 1
now = dp[N-1][T[0]]
if now == -1:
    print(-1)
    exit()
for i in range(1,M):
    t = T[i]
    if dp[now][t] == -1:
        print(-1)
        exit()
    if now < dp[now][t]:
        ans += dp[now][t] - now
    else:
        ans += N + dp[now][t] - now
    now = dp[now][t]

print(ans)

Submission status: Accepted

Solution code:
S = list(input())
T = list(input())

S = [ord(s)-97 for s in S]
T = [ord(t)-97 for t in T]

N = len(S)

dp = [[-1 for j in range(26)] for i in range(N)]

for i,s in enumerate(S):
    if dp[N-1][s] == -1:
        dp[N-1][s] = i

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

M = len(T)
ans = dp[N-1][T[0]] + 1
now = dp[N-1][T[0]]
if now == -1:
    print(-1)
    exit()
for i in range(1,M):
    t = T[i]
    if dp[now][t] == -1:
        print(-1)
        exit()
    if now < dp[now][t]:
        ans += dp[now][t] - now
    else:
        ans += N + dp[now][t] - now
    now = dp[now][t]

print(ans)

Submission status: Accepted

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

ans=0
s_inx=0
t_inx=0
s_l=len(s)
t_l=len(t)

c=0
while t_inx<=t_l-1:
  try:
    temp_inx=s[s_inx:].index(t[t_inx])
    s_inx+=temp_inx+1
    t_inx+=1
    c=0
  except:
    c+=1
    s_inx=0
    ans+=s_l

  if c==2:
    print(-1)
    exit()
else:
  ans+=s_inx

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

S = input()
T = input()

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

sToI = {s: [] for s in set(list(S))}
for i, s in enumerate(S):
    sToI[s].append(i)

now = 0
R = 0
for t in T:
    I = sToI[t]
    nx = bisect_left(I, now)

    if nx == len(I):
        nx = 0
        R += 1

    now = I[nx] + 1

print(now + R * len(S))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

s=input()
t=input()
import collections
dic={}
lim={}
mod=len(s)
for ind,i in enumerate(s):
    if i not in dic:
        dic[i] = []
        lim[i] = 0
    dic[i].append(ind)
    lim[i] += 1
now=0
cnt=0
ok = True
#print(dic)
import bisect
for i in t:
    if i not in dic:
        ok=False
        break
    ed = bisect.bisect_left(dic[i],now)
    if ed == lim[i]:
        cnt+=1
        now = dic[i][0]+1
    else:
        now = dic[i][ed]+1
    #print(now)
if ok==True:
    print(mod*cnt+now)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

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

x = -1
cnt = 0

for t in T:
    if len(d[t]) == 0:
        print(-1)
        exit()
    y = bisect.bisect_right(d[t], x)
    if y == len(d[t]):
        cnt += 1
        x = d[t][0]
    else:
        x = d[t][y]

ans = len(S) * cnt + x + 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()
ls = len(s)
sets = set(s)
sett = set(t)
ind = [[] for _ in range(26)]
temp = 0
ans = 0
if sett.issubset(sets) == False:
    print('-1')
else:
    for i in range(ls):
        ind[ord(s[i])-97].append(i+1)
    for x in t:
        if temp >= ind[ord(x)-97][-1]:
            ans += ls - temp + ind[ord(x)-97][0]
            temp = ind[ord(x)-97][0]
        else:
            bs = bisect.bisect_right(ind[ord(x)-97],temp)
            ans += ind[ord(x)-97][bs] - temp
            temp = ind[ord(x)-97][bs]
    print(ans)

Submission status: Accepted

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

ls = len(s)
cnt = 0

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

Submission status: Accepted

Solution code:
from sys import stdin
import bisect
def main():
    #入力
    readline=stdin.readline
    s=readline().strip()
    n=len(s)
    t=readline().strip()

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

print(main()+1)

Submission status: Accepted

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

from collections import defaultdict
from bisect import bisect_left

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

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect
from collections import deque
stdin=sys.stdin

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

s=list(ns())
t=list(ns())
d={'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}

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

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


print(rep*len(s)+now)

Submission status: Accepted

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

d = defaultdict(list)

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

ans = 0
now = -1
for t in T:
    arr = d[t]
    if len(arr) == 0:
        print(-1)
        exit()
    idx = bisect.bisect_right(arr, now) # leftにすると、同じ文字を2連続探索するときにバグる
    if idx == len(arr):
        ans += 1
        now = arr[0]
    else:
        now = arr[idx]
print(ans * len(S) + now + 1)

Submission status: Accepted

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

d = defaultdict(list)

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

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)

from collections import defaultdict
d = defaultdict(list)

from bisect import bisect_right

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

    lee = len(s_li)
    #add_li = [ii+lee for ii in tmp_li]
    #new_li = tmp_li + add_li
    #bi = bisect.bisect_left(new_li, last_index+1)
    bi = bisect.bisect_left(tmp_li, last_index+1)
    #print(bi,len(tmp_li),'bi',tmp_li,last_index,'last_index')
    if bi>= len(tmp_li):
        repeat_count += 1
        min_index = tmp_li[0]
    else:
        min_index = tmp_li[bi]
    #print(new_li,last_index+1,min_index,'min')
    #if min_index>= lee:
    #    repeat_count += 1
    #    min_index -= lee
    last_index = min_index
    #print(repeat_count,'repeat')
    #print(last_index,'last')
print(lee*(repeat_count)+last_index+1)

Submission status: Accepted

Solution code:
import bisect

s=input()
t=input()

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

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

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

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

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

d = dict()

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

ret = 0
cindex = -1

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

print(ret)

Submission status: Accepted

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

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

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

print(res)

Submission status: Accepted

Solution code:
# S.find()の部分を高速化する
from collections import defaultdict
from bisect import bisect_right
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
import sys

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

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

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

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

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

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

    print(ans)


solve()

Submission status: Accepted

Solution code:
import sys

numChar = 26
ordA = ord('a')

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

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

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

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

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

print(i)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

S = input()
T = input()

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

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

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