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:
import bisect
import collections
s = input()
t = input()

table = collections.defaultdict(list)
table2 = collections.defaultdict(int)
last = t[-1]
last_id = []
for i, x in enumerate(s):
    table[x].append(i)

for i, x in enumerate(t):
    if x not in table:
        print(-1)
        exit(0)

tmp = 0
id = 0
ans = 0
for x in t:
    l = len(table[x])
    i = bisect.bisect_left(table[x], id)
    if l == i:
        id = 0
        ans += len(s)
        i = bisect.bisect_left(table[x], id)
    id = table[x][i]+1

ans += id


print(ans)

Submission status: Accepted

Solution code:
S = list(map(lambda x : ord(x)-ord('a'), input().strip()))
T = list(map(lambda x : ord(x)-ord('a'), input().strip()))

L = len(S)

occ = [[] for i in range(26)]
for i, c in enumerate(S):
    occ[c].append(i)

for c in T:
    if occ[c] == []:
        print(-1)
        quit()

total = 0
cur = -1

def getLowest(bound, lo, hi, lst):
    # Return lowest element in list greater than bound
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if lst[mid] > bound:
            hi = mid
        else:
            lo = mid + 1
    if lst[lo] > bound:
        return lst[lo]
    return lst[0]
        
    

for i, char in enumerate(T):
    newpos = getLowest(cur, 0, len(occ[char])-1, occ[char])
    if cur == newpos:
        total += L
    elif newpos < cur:
        total += L - cur + newpos
    else:
        total += newpos - cur
    cur = newpos
print(total)

Submission status: Accepted

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

dic = {}
for i in range(len(s)):
    if s[i] in dic:
        dic[s[i]].append(i)
    else:
        dic[s[i]] = [i]
        
def f(L, u, l, x):
    if L[-1] <= x:
        return -1
    if u-l < 2:
        if L[l] > x:
            return l
        else:
            return u
    m = (u+l)//2
    if L[m] > x:
        return f(L, m, l, x)
    else:
        return f(L, u, m, x)
    
ans = 0
c = 0 #１ステップ前に考察した文字がsの前から何番目か
for i in range(len(t)):
    if t[i] not in dic:
        ans = -1
        break
    idx = f(dic[t[i]], len(dic[t[i]])-1, 0, c-1)
#    print("idx =", idx)
    if idx < 0:
        num = dic[t[i]][0]+1
        ans += len(s)-c+num
        c = num
#        print(ans,c)
    else:
        num = dic[t[i]][idx]+1
        ans += num-c
        c = num
#        print(ans,c)
        
print(ans)

Submission status: Accepted

Solution code:
import collections
import bisect

def main():
    s=input()
    t=input()
    s = s*2
    n = len(s)
    cs = collections.Counter(s)
    ct = collections.Counter(t)
    for sct in ct.keys():
        if cs[sct] == 0:
            return -1
    dc = collections.defaultdict(list)
    for i in range(n):
        dc[s[i]].append(i+1)
    res = 0
    ptl = 0
    for i in range(len(t)):
        tl = dc[t[i]][bisect.bisect_left(dc[t[i]],ptl+1)]
        res += tl - ptl
        ptl = tl - n//2 if tl > n//2 else tl
    return res

print(main())

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bi_l
from collections import defaultdict

def main():
    s, t = sys.stdin.read().split()
    if set(t) - set(s):
        print(-1)
        sys.exit()

    n = len(s)
    s *= 2
    c = defaultdict(list)
    for i in range(n * 2):
        c[s[i]].append(i)

    i = 0
    l = 0 # left_most
    for ch in t:
        b = c[ch][bi_l(c[ch], l)]
        if b < n:
            l = b + 1
        else:
            l = b - n + 1
            i += n

    print(i+(l-1)+1) # 最初が0のため

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left


def main():
	s = input()
	n = len(s)
	s = s + s
	t = input()
	if set(t) - set(s):
		print(-1)
		exit()
	d = defaultdict(list)
	for i in range(2 * n):
		d[s[i]] += [i]
	cur = ncnt = 0

	for c in t:
		x = d[c][bisect_left(d[c], cur)]
		if x < n:
			cur = x + 1
		else:
			cur = x - n + 1
			ncnt += 1
	print(ncnt*n + cur)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from bisect import bisect
s=input()
t=input()
n,m=len(s),len(t)
alf=list("abcdefghijklmnopqrstuvwxyz")
data=[[] for i in range(26)]
for i in range(26):
    for j in range(n):
        if alf[i]==s[j]:
            data[i].append(j)
l=[0]*26
for i in range(26):
    l[i]=len(data[i])
ind=-1
count=0
for i in range(m):
    k=alf.index(t[i])
    if data[k]:
        p=bisect(data[k],ind)
        if p==l[k]:
            count+=1
            ind=data[k][0]
        else:
            ind=data[k][p]
    else:
        print(-1)
        break
else:
    print(n*count+ind+1)

Submission status: Accepted

Solution code:
# 2019-11-17 10:52:21(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    s, t = [s.rstrip() for s in sys.stdin.read().split()]
   
    if set(t) - set(s):
        print(-1)
        sys.exit()

    count = 0
    l = 0
    i = 0
    current = t[i]
    all_found = False
    while not all_found:
        j = s.find(current, l, len(s))
        if j == -1:
            count += len(s)
            l = 0
        else:
            if i == len(t) - 1:
                count += j + 1
                all_found = True
            else:
                if j == len(s) - 1:
                    count += len(s)
                    l = 0
                else:
                    l = j + 1
                i += 1
                current = t[i]
    print(count)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2019-11-17 10:52:21(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    s, t = [s.rstrip() for s in sys.stdin.read().split()]
   
    for l in set(t):
        if not l in s:
            print(-1)
            sys.exit()

    count = 0
    l = 0
    i = 0
    current = t[i]
    all_found = False
    while not all_found:
        j = s.find(current, l, len(s))
        if j == -1:
            count += len(s)
            l = 0
        else:
            if i == len(t) - 1:
                count += j + 1
                all_found = True
            else:
                if j == len(s) - 1:
                    count += len(s)
                    l = 0
                else:
                    l = j + 1
                i += 1
                current = t[i]
    print(count)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
s, t = [ord(c)-ord('a') for c in input()], [ord(c)-ord('a') for c in input()]
cnt = [[] for i in range(26)]
for i in range(len(s)):
    cnt[s[i]].append(i)
    cnt[s[i]].append(i+len(s))
for i in range(26):
    cnt[i] = sorted(cnt[i])
ans = 0
p = 0
for i in range(len(t)):
    c = t[i]
    if (len(cnt[c]) == 0):
        print('-1')
        exit()
    next = bisect_left(cnt[c], p)
    p = cnt[c][next] + 1
    if (p >= len(s)):
        p -= len(s)
        ans += len(s)
ans += p
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

S = input()
T = input()

d = defaultdict(list)

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

ans = 0
cnt = 0

for t in T:
    c = d[t]
    if len(c)==0:
        print(-1)
        quit()
    if c[-1] <= ans:
        ans = c[0]
        cnt += 1
    else:
        ans = c[bisect.bisect_right(c, ans)]
        
print(len(S)*cnt + ans)

Submission status: Accepted

Solution code:
s=input()
t=input()
cnt=0
k=0
for i in t:
  f=s.find(i,k)
  if f<0:
    cnt+=1
    f=s.find(i)
    if f==-1:
      print(-1)
      exit()
    else:
      k=f+1
  else:
    k=f+1
print(cnt*len(s)+k)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

def main():
    s = input()
    t = input()
    
    table = {a : [] for a in 'abcdefghijklmnopqrstuvwxyz'}
    N = len(s)
    
    for idx, a in enumerate(s): table[a].append(idx+1)
    
    length = {a : len(table[a]) for a in 'abcdefghijklmnopqrstuvwxyz'}
    
    loop, idx = 0, 0
    for a in t:
        if not table[a]: 
            print(-1)
            sys.exit()
        
        i = bisect_right(table[a], idx)
        
        if i != length[a]:
            idx = table[a][i]
            if idx == N:
                loop += 1
                idx = 0
        else:
            loop += 1
            idx = table[a][0]
            
    print(loop * len(s) + idx)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
S=list(input())
T=list(input())
sT=set(T)
N=len(S)
TI={}
for i in range(N):
  s=S[i]
  if s in sT:
    if s in TI:
      TI[s].append(i)
    else:
      TI[s]=[i]

i=-1
for t in T:
  if t not in TI:
    print(-1)
    exit()
  else:
    ni=TI[t][(bisect.bisect_right(TI[t],i%N))%len(TI[t])]
    if ni>i%N:
      i+=ni-i%N
    else:
      i+=N-i%N+ni
print(i+1)

Submission status: Accepted

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

check = [False]*30
for c in s:
    i = ord(c) - ord("a")
    check[i] = True

for c in t:
    i = ord(c) - ord("a")
    if not check[i]:
        print(-1)
        sys.exit()

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

s = s + s

#
def ser(string :str,target :str,s :int):
    for i in range(s,len(string)):
        if string[i] == target:
            return i % (len(string)//2),i-1

# 指定した範囲に数字を埋める
def dig(ls,c,v,s,t):
    for i in range(s,t+1):
        ls[i][c] = v

for c in range(len(dp[0])):
    if not check[c]:continue
    i = 0
    while i < len(dp):
        start = i
        v,i = ser(s,chr(c+ord("a")),i+1)
        dig(dp,c,v,start,min(i,len(dp)-1))
        i += 1

# 最初にうまいことやるために
import copy
ls = [0 if s[0] == chr(i + ord("a")) else dp[0][i] for i in range(len(dp[0]))]
dp.append(ls)

ans = 0
i = -1
for char in t:
    ikari = dp[i][ord(char) - ord("a")]
    if i >= ikari:
        ans += 1
    i = ikari
print(ans * (len(dp)-1) + 1 + i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import bisect

def solve(s: str, t: str):
    LENS = len(s)
    dict_s = {} ##{'c': [0], 'o': [1], 'n': [2], 't': [3, 6], 'e': [4], 's': [5]}
    index = [] ##[[5], [4], [2], [3, 6], [4], [2], [0], [4]]

    ## create dict
    for i in range(LENS):
        if dict_s.get(s[i]) != None:
            dict_s[s[i]].append(i)
        else:
            dict_s[s[i]]= [i]
    
    ## そもそもtが作れるかの判定
    for tt in t:
        if dict_s.get(tt) == None:
            print(-1)
            return
        else:
            index.append(dict_s[tt])
    
    answer = 0
    for i in range(len(index)):
        cur = index[i]

        if i == 0:
            answer += cur[0]
            index[i]=[cur[0]]
            continue

        prev = index[i-1]

        if len(cur)==1:
            if cur[0]>prev[0]:
                answer += cur[0]-prev[0]
            else:
                answer += cur[0]+LENS-prev[0] ##一周追加
        else: ##複数
            next_index = bisect.bisect_left(cur,prev[0])

            if next_index<len(cur)-1: ## prevより大きいindexがある時
                next_index += 1 if cur[next_index] == prev[0] else 0
                
                answer += cur[next_index]-prev[0]
                index[i]= [cur[next_index]]
            elif next_index==len(cur)-1:
                if prev[0]<cur[next_index]:
                    answer += cur[next_index]-prev[0]
                    index[i] =[cur[next_index]]
                elif prev[0]==cur[next_index]:
                    answer += cur[0]+LENS-prev[0]
                    index[i] =[cur[0]]
            else: ##next_index==len(cur):
                answer += cur[0]+LENS-prev[0]
                index[i] = [cur[0]]
       

    print(answer+1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: [])
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].append(i)
    min_D[s] = min(i, min_D[s])

for s in D.keys():
    D[s] = sorted(D[s])

cur_pos = 0
repeat = 0
for t in T:
    #print("cur->", cur_pos)
    ind = bisect.bisect_left(D[t], cur_pos)
    if ind >= len(D[t]):
        repeat += 1
        cur_pos = min_D[t]+1
    else:
        cur_pos = D[t][ind]+1

print(len(S)*repeat+cur_pos)

Submission status: Accepted

Solution code:
#$from collections 
import bisect,sys

s_ = input()
t = input()

char_s = set(s_)
char_t = set(t)


if not char_s >= char_t:
    print(-1)
    sys.exit()

s = s_+s_

chr_s = {}

l = len(s_)

for i in range(2*l):
    if s[i] in chr_s:
        chr_s[s[i]].append(i)
    else:
        chr_s[s[i]] = [i]
#print(chr_s)
loops = 0
tmp = -1##?

for i in range(len(t)):
    j = bisect.bisect_right(chr_s[t[i]],tmp)###leftと違うの？
    tmp = chr_s[t[i]][j]
    #print(tmp)
    if tmp>=l:
        loops+=l
        tmp-=l
#print(chr_s)
print(loops+tmp+1)#0-indexで+1

Submission status: Accepted

Solution code:
import bisect

s=input()
t=input()

sl=len(s)
tl=len(t)

r="abcdefghijklmnopqrstuvwxyz"
p=[[] for i in range(26)]

for i in range(sl):
  p[r.find(s[i])].append(i)

for i in range(26):
  if len(p[i])>0:
    p[i].append(p[i][0]+sl)

s=set()
for i in range(tl):
  s.add(t[i])
for c in s:
  if len(p[r.find(c)]) == 0:
     print(-1)
     exit()

ti, si = 0, -1
while ti < tl:
  si +=  p[r.find(t[ti])][bisect.bisect_right(p[r.find(t[ti])], si%sl)] - si%sl
  ti += 1

print(si+1)

Submission status: Accepted

Solution code:
from bisect import*
s=input()
t=input()
if set(t)<=set(s):
    d={}
    for k,j in enumerate(s*2):
        if j in d:
            d[j].append(k)
        else:
            d[j]=[k]
    now=-1
    ans=0
    for i in t:
        nex=d[i][bisect_right(d[i],now)]
        ans+=nex-now
        if nex>=len(s):
            now=nex-len(s)
        else:
            now=nex
    print(ans)

else:
    print(-1)

Submission status: Accepted

Solution code:
from bisect import*
s=input()
t=input()
if set(t)<=set(s):
    d={}
    for k,j in enumerate(s*2):
        if j in d:
            d[j].append(k)
        else:
            d[j]=[k]
    #print(d)
    now=-1
    ans=0
    for _,i in enumerate(t):
        nex=d[i][bisect_right(d[i],now)]
        ans+=nex-now

        #print(i,_,now,nex,ans)
        
        if nex>=len(s):
            now=nex-len(s)
        else:
            now=nex
    print(ans)

else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left


def main():
	s = input()
	n = len(s)
	s = s + s
	t = input()
	if set(t) - set(s):
		print(-1)
		exit()
	d = defaultdict(list)
	for i in range(2 * n):
		d[s[i]] += [i]
	cur = ncnt = 0

	for c in t:
		x = d[c][bisect_left(d[c], cur)]
		if x < n:
			cur = x + 1
		else:
			cur = x - n + 1
			ncnt += 1
	print(ncnt*n + cur)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
n = len(s)
s = s + s
t = input()
if set(t) - set(s):
	print(-1)
	exit()
d = defaultdict(list)
for i in range(2 * n):
	d[s[i]] += [i]
cur = tot = 0
for c in t:
	x = d[c][bisect_left(d[c], cur)]
	if x < n:
		cur = x + 1
	else:
		cur = x - n + 1
		tot += n
tot += cur
print(tot)

Submission status: Accepted

Solution code:
import bisect
s=list(input())
t=list(input())
s=s+s
u=[[] for i in range(26)]
x=0
count=0

for i in range(ord('a'),ord('z')+1):
    for j in range(len(s)):
        if i==ord(s[j]):
            u[i-97].append(j+1)

for i in range(len(t)):
    if len(u[ord(t[i])-97])==0:
        print(-1)
        exit()
    b=bisect.bisect_left(u[ord(t[i])-97],x+1)
    
    if u[ord(t[i])-97][b]>len(s)//2:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]-len(s)//2
        
    else:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]
        
        
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left

s = input().strip()  # e.g., "contest"
t = input().strip()  # e.g., "son"
# s = "contest"
# t = "son"
# t = "programming"
# t = "sentence"

# 文字と出現位置のマップ
charmap = [[] for _ in range(26)]
for i, ch in enumerate((s + s)):
    charmap[ord(ch) - ord('a')].append(i)

# t を舐めながら答えを探す
ans = p = 0
for ch in t:
    pos_list = charmap[ord(ch) - ord('a')]
    if len(pos_list) == 0:
        print('-1')
        exit(0)

    p = pos_list[bisect_left(pos_list, p)] + 1
    if len(s) <= p:
        ans += len(s)
        p -= len(s)

ans += p
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left

s = input().strip()  # e.g., "contest"
t = input().strip()  # e.g., "son"
# s = "contest"
# t = "son"
# t = "programming"
# t = "sentence"

# 文字列 s 二周分の文字の出現位置マップを作る
s_map = [[] for _ in range(26)]
for i, ch in enumerate((s + s)):
    s_map[ord(ch) - ord('a')].append(i)

# t を舐めながら回答を作る
p = ans = 0
for ch in t:
    ch_position_list = s_map[ord(ch) - ord('a')]
    if len(ch_position_list) == 0:
        print('-1')
        sys.exit()

    p = ch_position_list[bisect_left(ch_position_list, p)] + 1
    if len(s) <= p:
        ans += len(s)
        p -= len(s)

ans += p
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()
idxs = defaultdict(list)

for i, c in enumerate(s):
    idxs[c].append(i)
for i, c in enumerate(s):
    idxs[c].append(len(s) + i)

ans, cur_i = -1, -1
for c in t:
    if c not in idxs: print(-1); break
    a = idxs[c]
    nxt = a[bisect_right(a, cur_i)]
    ans += nxt - cur_i
    cur_i = nxt % len(s)
else: print(ans+1)

Submission status: Accepted

Solution code:
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
T = str(input())
N = len(S)
cou = int(0)
cur = int(0)
move = int(0)
S_map = [[]for _ in range(26)]

for i in range(N):
    S_map[ord(S[i])-97].append(i+1)
for i in range(N):
    S_map[ord(S[i])-97].append(N+i+1)

for c in T:
#    print(cur)
    if S_map[ord(c)-97]==[]:
        ans = -1
        break
    move = bisect.bisect_left(S_map[ord(c)-97],cur+1)
    cur = S_map[ord(c)-97][move]
    if cur>=N:
        cou += 1
        cur -= N

if ans==0:
    ans = cou*N + cur

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
s_map = [[] for _ in range(26)]
import bisect
for i in range(len(s)):
    s_map[ord(s[i])-97].append(i)
for i in range(len(s)):
    s_map[ord(s[i])-97].append(len(s)+i)
cur = 0
count = 0
f = True
for c in t:
    if s_map[ord(c)-97] == []:
        f = False
        break
    np = bisect.bisect_left(s_map[ord(c)-97],cur)
    cur = s_map[ord(c)-97][np]+1
    
    if cur >= len(s):
        count += 1
        cur -= len(s)
print(count * len(s) + cur if f else -1)

Submission status: Accepted

Solution code:
import sys


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

    appear_pos = {}  # 文字が出てくる場所
    for idx, T in enumerate(t):
        if T not in appear_pos:
            appear_pos[T] = [idx]
        else:
            appear_pos[T].append(idx)

    search_idx = {}
    for key in appear_pos.keys():
        search_idx[key] = -1

    loop_count = 0
    find_idx = -1
    for S in s:
        if S not in appear_pos:
            print(-1)
            sys.exit()

        while True:
            search_idx[S] += 1
            if len(appear_pos[S]) == search_idx[S]:
                # 次のループに移動する
                loop_count += 1
                for key in appear_pos.keys():
                    search_idx[key] = -1
                find_idx = appear_pos[S][0]
                break

            idx_new = appear_pos[S][search_idx[S]]
            if idx_new > find_idx:
                find_idx = idx_new
                break

    print(find_idx+loop_count*len(t)+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

for i in range(2*n):
    ls[ord(s[i])-97].append(i)

res = 0
flg = True
ind = -1
for i in range(m):
    if ls[ord(t[i])-97] == []:
        flg = False
        break
    nind = ls[ord(t[i])-97][bisect_left(ls[ord(t[i])-97],ind+1)]
    res += nind - ind 
    if nind >= n:
        nind -= n
    ind = nind
if flg:print(res)
else:print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from bisect import bisect_left

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    # See:
    # https://www.youtube.com/watch?v=lWETOlGiuaI
    # KeyInsight
    # 部分列判定：場所i以降で文字Cが最初に現れる位置を高速に求める
    # アルファベットの出現位置をリストで記録

    # sで各文字が出現する位置を2周分記録
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 0
    p = 0  # after p

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        # 二分探索でWAを量産
        # See:
        # https://atcoder.jp/contests/abc138/submissions/6999265
        # p以上の最小の値
        p = alpha[c][bisect_left(alpha[c], p)] + 1

        # インデックスが，sの長さ以上のとき
        if p >= n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from bisect import bisect_left

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    # See:
    # https://www.youtube.com/watch?v=lWETOlGiuaI
    # KeyInsight
    # 部分列判定：場所i以降で文字Cが最初に現れる位置を高速に求める
    # アルファベットの出現位置をリストで記録

    # sで各文字が出現する位置を2周分記録
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 0
    p = 0

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        # 二分探索でWAを量産
        # See:
        # https://atcoder.jp/contests/abc138/submissions/6999265
        p = alpha[c][bisect_left(alpha[c], p)] + 1

        if p >= n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from bisect import bisect_left

    s = input()
    t = input()
    n = len(s)
    m = len(t)
    alpha = [[] for _ in range(26)]

    # KeyInsight
    # 部分列判定：場所i以降で文字Cが最初に現れる位置を高速に求める
    # アルファベットの出現位置をリストで記録

    # sで各文字が出現する位置を2周分記録
    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index)

    for index, si in enumerate(s):
        alpha[(ord(si) - ord('a'))].append(index + n)

    ans = 0
    p = 0

    for ti in t:
        c = ord(ti) - ord('a')

        if len(alpha[c]) == 0:
            print('-1')
            exit()

        pi = bisect_left(alpha[c], p)
        p = alpha[c][pi]
        p += 1

        if p >= n:
            p -= n
            ans += n

    ans += p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
S = input()
E = {S[i]:[] for i in range(len(S)-1)}
for i in range(len(S)-1):
  E[S[i]].append(i)
T = input()
a = len(S)-1
ans=0
now = -1
for i in range(len(T)-1):
  if not T[i] in E.keys():
    print(-1)
    exit()
  s=E[T[i]]
  b= bisect.bisect_right(s,now)
  #print(s,b,now)
  if b==len(s):
    ans+=s[0]+1+a-1-now
    now=s[0]
  else:
    ans+=s[b]-now
    now=s[b]
print(ans)

Submission status: Accepted

Solution code:
def upperbound(ar, value):
    low = 0
    high = len(ar)
    while low < high:
        mid = (low + high) >> 1
        if value > ar[mid]:
            low = mid + 1
        else:
            high = mid
    return low


s = input()
t = input()
data = {}
for index, val in enumerate(s):
    if val not in data:
        data[val] = [index]
    else:
        data[val].append(index)
ok = True
index = 0
mod = len(s)
pos = [0] * (len(t))
for i, c in enumerate(t):
    if c not in data:
        ok = False
        break
    else:
        curr_index = upperbound(data[c], index)
        if curr_index >= len(data[c]):
            pos[i] = data[c][0]
        else:
            pos[i] = data[c][curr_index]
        index = (pos[i] + 1) % mod
if ok:
    result = pos[0] + 1
    for i in range(1, len(t)):
        if pos[i] > pos[i - 1]:
            result = result + (pos[i] - pos[i - 1])
        else:
            result = result - (pos[i - 1] + 1) + mod + pos[i] + 1
    print(result)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue


# sys.stdin = open('input')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    s = raw_input().strip()
    t = raw_input().strip()
    d = defaultdict(list)
    for idx, c in enumerate(s):
        d[c].append(idx)
    i, offset = 1, -1
    for c in t:
        idx = bisect.bisect_right(d[c], offset)
        if not d[c]:
            print -1
            return
        if idx == len(d[c]):
            i+=1
            offset = d[c][0]
        else:
            offset = d[c][idx]
    print (i-1)*len(s)+offset+1






main()

Submission status: Accepted

Solution code:
import bisect

# Receive input
s = input()
t = input()

# preparations
s_len = len(s)
t_len = len(t)

index_in_s = {}
for ch in "abcdefghijklmnopqrstuvwxyz":
    index_in_s[ch] = [] # store positions of each character in s

for j in range(0, s_len):
    index_in_s[s[j]].append(j)


subtract = 0
current = s_len # so that the first iteration falls into the last "else" block
is_subsequence = True
for ch in t:
    # t is not a subsequence of s
    if len(index_in_s[ch]) == 0:
        is_subsequence = False
        break
    else:
        pos = bisect.bisect_right(index_in_s[ch], current)
        if pos < len(index_in_s[ch]): # index_in_s[ch] has a value larger than current
            subtract += 1
            current = index_in_s[ch][pos]
        else: # index_in_s[ch] doesn't have a value larger than current
            # Look for ch in "the next" s
            current = index_in_s[ch][0]


if is_subsequence:
    i = (t_len - 1 - subtract) * s_len + current + 1
else:
    i = -1

print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect


S = input()
T = input()

if set(T) - set(S):
    print(-1)
    exit()

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

now = -1
count = 0
for t in T:
    if dic[t][-1] < now+1:
        now = -1
        count += 1
    idx = bisect.bisect_left(dic[t], now+1)
    now = dic[t][idx]

ans = count*len(S) + now + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect


S = input()
T = input()

if set(T) - set(S):
    print(-1)
    exit()

dic = defaultdict(list)
leng_dic = defaultdict(int)

for pos, s in enumerate(S):
    dic[s].append(pos)
    leng_dic[s] += 1

length = len(S)
now = -1
count = 0
for t in T:
    if dic[t][-1] < now+1:
        now = -1
        count += 1
    idx = bisect.bisect_left(dic[t], now+1)
    now = dic[t][idx]

ans = count*length + now + 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

s,t=input(),input()
ls=len(s)
lt=len(t)
A=[[] for i in range(26+1)]
L=[0 for i in range(26+1)]

for i in range(ls):
  A[ord(s[i])-96].append(i+1)
  L[ord(s[i])-96]+=1
#print(A)

tmp=0
ans=0
for i in range(lt):
  ii=ord(t[i])-96

  if L[ii]==0:
    print(-1)
    exit()
  else:
    iii=bisect.bisect(A[ii],tmp)
    #print(t[i],A[ii],tmp,iii,ans)
    if iii==L[ii]:
      ans+=ls-tmp+A[ii][0]
      tmp=A[ii][0]
    else:
      ans+=A[ii][iii]-tmp
      tmp=A[ii][iii]
print(ans)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    import bisect
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    t = str(input().rstrip('\n'))
    d = collections.defaultdict(list)
    for i in range(len(s)):
        d[s[i]] += [i]

    loop = 0
    pos = 0
    for i in range(len(t)):
        if t[i] not in d:
            print(-1)
            exit()
        else:
            pos = bisect.bisect_left(d[t[i]], pos)
            if len(d[t[i]]) == pos:
                loop += 1
                pos = 0
            pos = d[t[i]][pos] + 1
    print(loop * len(s) + pos)


if __name__ == '__main__':
    slove()