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

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

s_alpha_ind = {x:[] for x in string.ascii_lowercase}

for i in range(len_s):
    s_alpha_ind[s[i]].append(i+1)

ans = 0
now_s_ind = 0
for i in range(len_t):
    now_t = t[i]
    if len(s_alpha_ind[now_t]) == 0:
        ans = -1
        break
    else:
        # print('now s_ind is: '+ str(now_s_ind))
        # print('-'*30)
        # print('now_t is: ' + str(now_t))

        # 二分探索で、now_s_indよりも大きな値を探す
        # なければ最初の値を返す
        Inds = s_alpha_ind[now_t]
        ind = bisect.bisect_right(Inds, now_s_ind)
        # print('Inds is :')
        # print(Inds)
        # print('ind is:' + str(ind))

        if ind == len(Inds):
            ans += (len_s - now_s_ind + Inds[0])
            if i == 0:
                ans -= len_s
            now_s_ind = Inds[0]
        else:
            ans += Inds[ind] - now_s_ind
            now_s_ind = Inds[ind]
        # print('ans is:' +  str(ans))


print(ans)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
n = len(s)
m = len(t)
indices = [[] for _ in range(26)]
for i in range(n):
    indices[ord(s[i]) - ord('a')].append(i)
for i in range(n):
    indices[ord(s[i]) - ord('a')].append(i + n)

ans = 0
p = 0
for i in range(m):
    c = ord(t[i]) - ord('a')
    if len(indices[c]) == 0:
        print(-1)
        exit()
    p = indices[c][bisect.bisect_left(indices[c], p)] + 1
    if p >= n:
        p -= n
        ans += n
ans += p
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
s = [ord(i) - ord("a") for i in input()]
t = [ord(i) - ord("a") for i in input()]
index = [[] for _ in range(26)]

for i, x in enumerate(s):
    index[x].append(i)


l_s = len(s)

for x in index:
    if x:
        x.append(x[0] + l_s)

cnt = -1
for r in t:
    seq = index[r]
    if not seq:
        cnt = -2
        break
    i = cnt % l_s
    j = bisect_right(seq, i)
    cnt += seq[j] - i

print(cnt+1)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s = input()
t = input()

loop = 0
index = -1

# tの要素が全てsに含まれていないと無理
# 部分集合かどうかを判定
if not set(t) <= set(s):
    print(-1)
    exit()

dic = defaultdict(list)
t_set = set(t)

for i, c in enumerate(s):
    dic[c].append(i)

for i in range(len(t)):
    # tを最初から最後まで見る
    # tのi番目の文字がsで，何番目に出てくるかのリストの中で，indexをinsertできる場所をidxとする
    idx = bisect_left(dic[t[i]], index)
    
    if idx < len(dic[t[i]]):
        # 0 start -> 1 start by plus 1
        index = dic[t[i]][idx] + 1
    elif idx >= len(dic[t[i]]):# hitしなくなったら，文字列を足す，loopする
        loop += 1
        index = -1 # 最初から
        idx = bisect_left(dic[t[i]], index)
        index = dic[t[i]][idx] + 1
print(len(s) * loop + index)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from collections import defaultdict

s = input()
t = input()
idx = defaultdict(list)
for i in range(len(s)):
    idx[s[i]].append(i)
num = 0
prev = -1
for c in t:
    l = len(idx[c])
    if l == 0:
        print(-1)
        exit()
    j = bisect_right(idx[c], prev)
    if j == l:
        prev = idx[c][0]
        num += 1
    else:
        prev = idx[c][j]
print(len(s) * num + prev + 1)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_right
    s=input()
    t=input()
    ls=len(s)
    lt=len(t)

    dic={i:[] for i in set(t)}
    for i in range(ls):
        st=s[i]
        if st in dic:
            dic[st].append(i)  

    cnt=0
    idx=-1
    for i in range(lt):
        st=t[i]
        if dic[st]==[]:
            print(-1)
            exit()

        tmp_idx=bisect_right(dic[st],idx)

        if tmp_idx==len(dic[st]):
            cnt+=1
            idx=dic[st][0]
        
        else:
            idx=dic[st][tmp_idx]
    
    print(cnt*ls+idx+1)  
 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
import bisect

def main():
    s = input()
    t = input()
    
    index = [[] for _ in range(26)]
    for x,st in enumerate(s):
        index[ord(st)-ord("a")].append(x)
    
    roop,now = 0,-1
    for st in t:
        num = ord(st)-ord("a")
        if index[num] == []:
            print(-1)
            exit()
        else:
            pos = bisect.bisect_right(index[num],now)
            if pos == len(index[num]):
                roop += 1
                now = index[num][0]
            else:
                now = index[num][pos]
                
    print(roop*len(s)+now+1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left
import heapq
import numpy as np

def input(): return sys.stdin.readline().strip()
def INt(): return int(input())
def MAP(): return map(int, input().split())
def LISt(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	t = input()
	
	if not set(s) >= set(t):
		print(-1)
		exit()

	dic = defaultdict(list)
	for i, char in enumerate(s):  # 文字列が出現する位置のリスト
		dic[char].append(i)
	
	loop = 0
	index = -1
	for i in range(len(t)):
		idx = bisect_left(dic[t[i]], index)  # リストの何個目とヒットするか
		if idx != len(dic[t[i]]):
			index = dic[t[i]][idx] + 1
		else:  # idx = |dic[t[i]]| -> もうヒットする箇所がないので次のループ
			loop += 1
			index = -1
			idx = bisect_left(dic[t[i]], index)
			index = dic[t[i]][idx] + 1

	print(len(s)*loop+index)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left
import heapq
import numpy as np

def input(): return sys.stdin.readline().strip()
def INt(): return int(input())
def MAP(): return map(int, input().split())
def LISt(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	t = input()
	if len(set(s)&set(t)) != len(set(t)):
		print(-1)
		exit()

	dic = defaultdict(list)
	for i, char in enumerate(s):  # 文字列が出現する位置のリスト
		dic[char].append(i)
	
	loop = 0
	index = -1
	for i in range(len(t)):
		idx = bisect_left(dic[t[i]], index)  # リストの何個目とヒットするか
		if idx != len(dic[t[i]]):
			index = dic[t[i]][idx] + 1
		else:  # idx = |dic[t[i]]| -> もうヒットする箇所がないので次のループ
			loop += 1
			index = -1
			idx = bisect_left(dic[t[i]], index)
			index = dic[t[i]][idx] + 1

	print(len(s)*loop+index)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left
import heapq
import numpy as np

def input(): return sys.stdin.readline().strip()
def INt(): return int(input())
def MAP(): return map(int, input().split())
def LISt(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	t = input()
	if len(set(s)&set(t)) != len(set(t)):
		print(-1)
		exit()

	dic = defaultdict(list)
	for i, char in enumerate(s):  # 文字列が出現する位置のリスト
		dic[char].append(i)
	
	loop = 0
	index = -1
	for i in range(len(t)):
		if len(dic[t[i]]) == 0:
			print(-1)
			exit()
		idx = bisect_left(dic[t[i]], index)  # リストの何個目とヒットするか
		if idx != len(dic[t[i]]):
			index = dic[t[i]][idx] + 1
		else:  # idx = |dic[t[i]]| -> もうヒットする箇所がないので次のループ
			loop += 1
			index = -1
			idx = bisect_left(dic[t[i]], index)
			index = dic[t[i]][idx] + 1

	print(len(s)*loop+index)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

S = input()
T = input()

# 文字列の各文字がどのインデックスにあるか辞書化する
for i in range(len(S)):
    d[S[i]].append(i)


NoFind = False

sequence = 1  # 文字列の連続数
index = -1
for i in range(len(T)):
    if len(d[T[i]]) == 0:
        NoFind = True
        break
    find = bisect_left(d[T[i]], index)
    if find != len(d[T[i]]):
        index = d[T[i]][find] + 1
    else:  # 見つからなかったので文字列を追加
        sequence += 1
        index = -1
        find = bisect_left(d[T[i]], index)
        index = d[T[i]][find] + 1 
            
if NoFind:
    print(-1)
else:
    print(len(S)*(sequence-1) + index)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
data = {}
max_s = len(s) + 1
for i in range(26):
    data[chr(i + ord('a'))] = []
for i in range(len(s)):
    data[s[i]].append(i+1)
for i in range(26):
    data[chr(i + ord('a'))].append(max_s)
pre = 0
ans = 0
for i in range(len(t)):
    char = t[i]
    if len(data[char]) == 1:
        print(-1)
        exit()
    else:
        index = bisect.bisect_left(data[char], pre+1)
        if data[char][index] == max_s:
            ans += len(s) - pre
            pre = data[char][0]
            ans += pre
        else:
            ans += data[char][index] - pre
            pre = data[char][index]
print(ans)

Submission status: Accepted

Solution code:
al = "abcdefghijklmnopqrstuvwxyz"
d = {}
dn = {}
for a in al:
    d[a] = []
    dn[a] = 0
s = input()
for i in range(len(s)):
    d[s[i]].append(i)
    dn[s[i]] += 1

t = input()
import bisect
ans = 0
n = -1
for a in t:
    l = d[a]
    if l:
        res = bisect.bisect(l, n)
        if res == dn[a]:
            ans += 1
            n = l[0]
        else:
            n = l[res]
    else:
        ans = 0
        n = -2
        break
print(ans * len(s) + n + 1)

Submission status: Accepted

Solution code:
INF=float("inf")
def c2i(c): return ord(c)-ord("a")

def main():
    S=list(map(c2i, input()))
    N=len(S)
    T=list(map(c2i, input()))
    S*=2
    Next=[[INF]*26 for _ in range(N*2)]
    for i in range(N*2-2,-1,-1):
        for j in range(26):
            Next[i][j] = 1 if S[i%N]==j else Next[i+1][j]+1
    ans=0
    i=0
    for t in T:
        x=Next[i][t]
        if x==INF:
            print(-1)
            exit()
        i+=x
        i%=N
        ans+=x
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
S=input()
T=input()
Sdata=[[] for i in range(26)]
for i in range(0,len(S)):
    Sdata[alphabetlist.index(S[i])].append(i)
ans=0
for i in range(len(T)):
    if Sdata[alphabetlist.index(T[i])]==[]:
        ans=-1
if ans!=-1:
    sequence=0
    number=-1
    for i in range(0,len(T)):
        x=T[i]
        n=alphabetlist.index(x)
        start=0
        end=len(Sdata[n])-1
        while end-start>1:
            test=(end+start)//2
            if Sdata[n][test]>number:
                end=test
            else:
                start=test
        if Sdata[n][start]>number:
            number=Sdata[n][start]
        elif Sdata[n][end]>number:
            number=Sdata[n][end]
        else:
            sequence+=1
            number=Sdata[n][0]
    ans=sequence*len(S)+number+1
print(ans)

Submission status: Accepted

Solution code:
import bisect
s = input()
l = len(s)
ch = [[] for _ in range(26)]
s *= 2
for i in range(l*2):
  ch[ord(s[i]) - ord("a")].append(i)
  
t = input()
ans = 0
now = -1
for i in t:
  idx = ord(i) - ord("a")
  if not ch[idx]:
    print(-1)
    break
  temp = bisect.bisect_right(ch[idx], now)
  ans += ch[idx][temp] - now
  now = ch[idx][temp]%l
else:
  print(ans)

Submission status: Accepted

Solution code:
from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)
"""
a=len(s)*len(t)
maxcount=len(s)
for i in range(100):
    if maxcount<a:
        maxcount**=10
    else:
        break
"""

for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=0
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]+1
    else:
        prei=dic[t[i]][0]+1
        count+=N
    if i==len(t)-1:
        count+=prei



print(count)

Submission status: Accepted

Solution code:
from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)
"""
a=len(s)*len(t)
maxcount=len(s)
for i in range(100):
    if maxcount<a:
        maxcount**=10
    else:
        break
"""

for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=0
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]+1
    else:
        prei=dic[t[i]][0]+1
        count+=N
    if i==len(t)-1:
        count+=prei



if count<=len(s)*(10**100):
    print(count)
else:
    print(-1)

Submission status: Accepted

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

s, t = sys.stdin.read().split()
l = len(s)
s *= 2

def main():
    for c in t:
        try:
            s.index(c)
        except:
            return -1
    
    d = defaultdict(list)
    for i in range(l*2):
        d[s[i]].append(i)
    
    for c in d:
        d[c].sort()
    
    j = 0
    cnt = 0
    for c in t:
        k = bi_l(d[c], j)
        j = d[c][k]
        if j >= l:
            j -= l
            cnt += 1
        j += 1
    ans = l * cnt + j

    return ans
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
N, M = len(s), len(t)

schr, indchr = dict(), dict()
for i in range(N):
    if s[i] in schr:
        schr[s[i]].append(i+1) 
    else:
        schr[s[i]] = [i+1]
        indchr[s[i]] = 0

schrset = set(schr)
ans, pos, pre, back = 0, 0, set(), True
for i in range(M):
    if t[i] in schrset:
        c = schr[t[i]]
        if c[-1] <= pos:
            ans += N - pos + c[0]
            pos = c[0]
            if not back:
                for x in indchr.keys():
                    indchr[x] = 0
                back, pre = True, set()
        else:
            j = indchr[t[i]]
            while c[j] <= pos:
                j += 1
            if j > 0:
                pre.add(t[i])
            ans += c[j] - pos
            pos, back, indchr[t[i]] = c[j], False, j
    else:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        next_index = bisect_right(obj[char], temp_num)
        if next_index == len(obj[char]):
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = obj[char][next_index]

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Feb 17 09:13:00 2020

@author: msaleh1
"""

def upper_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = int(l + (r - l) / 2)
        if nums[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return l


mx = pow(10,100)
#pypy3
s = input()
t = input()

    
cnt_s = dict()
cnt_t = dict()

for c in t:
    if c in cnt_t:
        cnt_t[c]+=1
    else:
        cnt_t[c] = 1


for idx in range(len(s)):
    if s[idx] in cnt_s:
        cnt_s[s[idx]].append(idx)  
    else:
       cnt_s[s[idx]] = [idx]

#cannot
for x in cnt_t:
    if x not in cnt_s:
        print(-1)
        exit(0)
    else:
        if(cnt_t[x] > mx*len(cnt_s[x])):
            print(-1)
            exit(0)
            
cur_indx =-1
skp =0
ans = 0

for x in t:
    temp_idx = upper_bound(cnt_s[x],cur_indx)
    if(temp_idx == len(cnt_s[x])):
        skp+=1
        cur_indx = cnt_s[x][0]
    else:
        cur_indx = cnt_s[x][temp_idx];
if(skp >= mx):
    print(-1)
else:
    print(skp*len(s)+cur_indx+1)

Submission status: Accepted

Solution code:

from bisect import bisect_right
from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]
# 即時終了
if set(t) - set(s):
    print(-1)
    exit()

# 前処理
# 0文字目から見たときにその文字が何文字目にあるかを記録しておく
mojiidx = defaultdict(lambda: [])
for i, ss in enumerate(s + s):
    mojiidx[ss].append(i)

# 本処理
# 最初にうまく飛べる点を探索
for i, ss in enumerate(s):
    if ss == t[0]:
        now = i
        break

for tt in t[1:]:
    idx = now % len(s)
    # 前処理の列から文字ttが何文字あとに出現するかを探索する
    ls = mojiidx[tt]
    tmp = ls[bisect_right(ls, idx)] - idx
    now += tmp
print(now + 1)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]
# 即時終了
if set(t) - set(s):
    print(-1)
    exit()

# 前処理
# 0based indexにおいてi文字目以降に文字cが出てくるidxを取得する

# 前処理の前処理、0文字目から見たときにその文字が何文字目にあるかを記録しておく
mojiidx = defaultdict(lambda: [])
for i, ss in enumerate(s + s):
    mojiidx[ss].append(i)

# i文字目において、次に文字cが出てくるのは何文字あと？
skiptable = []
for i in range(0, len(s)):
    tmp = {}
    for c, ls in mojiidx.items():
        tmp[c] = ls[bisect_right(ls, i)] - i
    skiptable.append(tmp)

# print(skiptable)

# 本処理
# 最初にうまく飛べる点を探索
for i, ss in enumerate(s):
    if ss == t[0]:
        now = i
        break

for tt in t[1:]:
    idx = now % len(s)
    now += skiptable[idx][tt]
print(now + 1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_e

# s'は無限回繰り返されているとみなす
# sの中に含まれていない文字でtが構成されていたら速攻で-1

'''
1234567    ...                      33
contest contest contest contest contest contest
     s      e     nte     n     c   e

だけどcontestを無限に生成して、マッチングさせていくのでは最悪10**10になってTLEになってしまう。
貪欲を高速にやる必要あり。
つまりs`を回すんじゃなくて、tを回してできる方法を考える
t=sentenceなら 1文字目から次にsがでてくるのは5文字後、
6文字目から次にeが出てくるのは6文字後、
12文字目から...みたいに計算できる。 (12文字目は 12%7文字目に対応 (=0のときだけ7文字目に対応))

この操作に必要なのはsのi文字目(1-based-idx)において次に文字cが出てくるのは何文字後か、である。
'''

from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]
if set(t) - set(s):
    print(-1)
    exit()

# 前処理パート
S = s + s
# 逆向きから走査することでi文字目に置いて次にiが出てくるのはどこか見つける
tmp = {}  # いま文字keyが最後に出たのはいくつあとか
skiptable = [None] * (len(s) + 1)

# 前処理の前処理、
for i in range(len(S) - 1, -1, -1):
    moji = S[i]
    for key in tmp.keys():
        tmp[key] += 1  # すべて一文字あとになる
    if i < len(s):
        skiptable[i + 1] = tmp.copy()  # ミュータブルかつアドレス参照に注意
    tmp[moji] = 0  # その文字は0文字あとに修正


# 本処理
# 最初にうまく飛べる点を探索
for i, ss in enumerate(s):
    if ss == t[0]:
        now = i + 1
        break

for tt in t[1:]:
    idx = now % len(s)
    idx = idx if idx else len(s)
    now += skiptable[idx][tt]
print(now)

Submission status: Accepted

Solution code:
import bisect


def bisect_search(f, val=0, l=0, r=10**6):

    #is_increase=(f(r)-f(l))>=0

    eps = 10**(-5)
    while True:

        c = (l+r)//2
        print(l, c, r)
        input()
        if f(c) == val and f(c-1) != val:
            return c
        #if f(c)-val < eps:
        #    return c

        if f(c) > val:
            r = c

        else:
            l = c

        if l == r:
            return False



def next(ch,k):
    global N,dcs
    k_=k%N
    #print(ch,ch_,k)
    #print(dcs[ch][ch_]+1)
    #print(dcs[ch])
    #print(dcs[ch][ch_]+1)
    #print(N)
    val = dcs[ch][k_-1]+1
    if k_==0:
        val=1

    A=bisect.bisect_left(dcs[ch],val,k_,min(k_+N,2*N-1))
    B = N*((k//N))
    #print(A,B,k//N,k,N)

    return A+B#+A//N


import numpy as np

s=input()
t=input()

td=list(set(t))

N=len(s)
d={}

import sys

R = set(list(s))
L = set(list(t))

if not(L <= R):
    print(-1)
    sys.exit()

for std in td:
    d[std] =[0]*(2*N)



for i in range(len(s)*2):
    #nd[s[i]]

    for std in td:            
        if s[i%N]==std:
            d[std][i]=1



dcs={}
for std in td:
    dcs[std]=np.cumsum(d[std])


last=-1
for ts in t:
    #print(last)
    last=next(ts,last+1)


print(last+1)


#print(dcs)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
T = sr()
len_S = len(S)
indexes_S = defaultdict(list)
for i, s in enumerate(S):
    indexes_S[s].append(i)

x = -1 # 今いるところ、次はx+1から探索
for t in T:
    if len(indexes_S[t]) == 0:
        print(-1); exit()
    arr = indexes_S[t]
    y = (x+1) % len_S
    next_i = bisect.bisect_left(arr, y) # tの同じ文字がある次のindex
    if next_i < len(arr):
        x = (x+1) + arr[next_i] - y
    else:
        x = (x+1) + arr[0] + len_S - y # 1周して次のarr

print(x+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left
S = input()
sl = len(S)
T = input()
t = set(T)
dic = defaultdict(list)
for c in t:
  for i, m in enumerate(S):
    if m==c:
      dic[c] += [i]
  if dic[c]==[]:
    print(-1)
    import sys
    sys.exit()
p = -1
ans = 0
pc = ''
for c in T:
  if pc==c:
    p += 1
    ans += 1
  if p>dic[c][-1]:
    ans += sl-1-p
    p = -1
  ind = bisect_left(dic[c],p)
  ans += dic[c][ind]-p
  p = dic[c][ind]
  pc = c
print(ans)

Submission status: Accepted

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

# 構成不可
if set(list(T)) - set(list(S)):
    print(-1)
    exit()


# 各文字の出現場所を記録
D = defaultdict(list)
for i, s in enumerate(S):
    D[s].append(i)


ans = 0
marker = -1
for t in T:
    target_char_appeared_indexes = D[t]
    bi = bisect_right(target_char_appeared_indexes, marker)
    # もう一周してこないと見つけられない
    if bi == len(target_char_appeared_indexes):
        ans += NS
        marker = target_char_appeared_indexes[0]
    else:
        marker = target_char_appeared_indexes[bi]


# 0-indexedのため+1
print(ans + marker + 1)

Submission status: Accepted

Solution code:
#14:20-


import bisect

s = input()
t = input()

s_dict = {c:[] for c in s}
for i, c in enumerate(s):
  s_dict[c].append(i)

len_s = len(s)

ans = 0
prev_i = -1
for c in t:
  if c not in s_dict:
    ans = -1
    prev_i = -1
    break;
  else:
    if s_dict[c][-1] <= prev_i:
      ans += len_s 
      prev_i = s_dict[c][0]
    else:
      prev_i = s_dict[c][bisect.bisect_right(s_dict[c], prev_i, lo=0, hi=len(s_dict[c]))]


print(ans + prev_i + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()

if set(s) >= set(t):
    d = defaultdict(list)
    for i, x in enumerate(s * 2):
        d[x].append(i)
    
    ans = 0
    cur = 0
    N = len(s)
    for x in t:
        cur_new = d[x][bisect_left(d[x], cur)]
        ans += cur_new - cur + 1
        cur = (cur_new + 1) % N

    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
S = input()
T = input()
n = len(S)
m = len(T)
set_S = set(list(S))
for i in range(m):
    if T[i] not in set_S:
        print(-1)
        exit()

# 必ず再現できることが確定
res = [[n]*26 for _ in range(n+1)]
for i in reversed(range(n)):
    for j in range(26):
        res[i][j] = res[i+1][j]
    res[i][ord(S[i])-ord("a")] = i

# print(*res, sep="\n")
cnt = 0
tmp = 0
for i in range(m):
    # tmpがnに到達する or このループでは次の文字がもう現れないなら次のループに進む
    if tmp == n or res[tmp][ord(T[i])-ord("a")] == n:
        cnt += n
        tmp = 0
    tmp = res[tmp][ord(T[i])-ord("a")]  # T[i]が現れる場所がわかる
    tmp += 1  # 次の文字へ
cnt += tmp  # ループを抜ける直前でtmp+=1しているので0-indexとも辻褄が合う
print(cnt)

Submission status: Accepted

Solution code:
S = input()
T = input()
n = len(S)

# Sのi文字目以降で最初に文字Cが登場するindex
res = [[n]*26 for _ in range(n+1)]
for i in reversed(range(n)):
    for j in range(26):
        res[i][j] = res[i+1][j]  # 一旦そのままの値を引き継いだ後に、今みているS[i]については若い番号で更新する
    res[i][ord(S[i])-ord("a")] = i  # 今後ろから見ていて、同じアルファベットが前の方で見つかったらより若い番号で更新されていく

# 与えられているのはindex
# nにはアクセスできないから、今後現れない文字はnで与えられている
# str_list = [chr(i + ord('a')) for i in range(26)]
# str_list = ' '.join(str_list)
# print(str_list)
# for r in res:
#     print(r)
# nに辿り着いたら26で割った余りを足す
set_S = set(list(S))
for i in range(len(T)):
    if T[i] not in set_S:
        print(-1)
        exit()
cnt = 0
tmp = 0
for i in range(len(T)):
    # T[i]を探しにいく
    if tmp == n:
        cnt += n
        tmp = 0
    elif res[tmp % n][ord(T[i])-ord("a")] == n:  # もうそのループでは見つからないなら
        if tmp == 0:
            print(-1)
            exit()
        cnt += n
        tmp = 0
    tmp = res[tmp % n][ord(T[i])-ord("a")]  # 0が手に入る
    tmp += 1
cnt += tmp
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

def main():
    S = input()
    T = input()
    d = defaultdict(list)
    for i, s in enumerate(S):
        d[s].append(i+1)
    pre = 0
    cnt = 0
    loop = 0
    len_S = len(S)
    for t in T:
        if not d[t]:
            print(-1)
            exit()
        index = bisect_right(d[t],pre)
        if index > len(d[t])-1:
            pre = 0
            loop += 1
            index = bisect_right(d[t],pre)
        pre = d[t][index]
        
    ans = loop * len_S + pre
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()
d = defaultdict(list)
e = defaultdict(int)

a, b = set(s), set(t)
if a&b!=b:
    print(-1)
else:
    for i,j in enumerate(s):
        d[j].append(i)
        e[j]+=1
    
    p = -1
    orig_size = len(s)
    ans = 0

    for i in t:
        a = bisect_left(d[i], p)
        if 0<= a < e[i]:
            p = d[i][a] + 1
        else:
            p = d[i][0] + 1
            ans += orig_size
    
    print(ans+p)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict

S = input()
T = input()
a = 97

grid = defaultdict(list)
for idx, s in enumerate(S + S):
    grid[s].append(idx)

ans = 0
cur = 0
lenS = len(S)
for t in T:
    if t in grid:
        tList = grid[t]
        ncur = tList[bisect_left(tList, cur)]
        ans += ncur - cur + 1
        cur = (ncur + 1) % lenS
    else:
        ans = -1
        break

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

S = input()
T = input()
a = 97

grid = [[] for _ in range(26)]
for idx, s in enumerate(S):
    s = ord(s) - a
    grid[s].append(idx)

glen = [0] * 26
for idx, g in enumerate(grid):
    glen[idx] = len(g)

cnt = 0
cur = 0
for t in T:
    t = ord(t) - a
    if glen[t]:
        idx = bisect_left(grid[t], cur)
        if idx == glen[t]:
            cnt += 1
            ncur = grid[t][0] + 1
        else:
            ncur = grid[t][idx] + 1
            cnt = cnt + (ncur <= idx)
        cur = ncur
    else:
        cnt = 0
        cur = -1
        break

print(cur + len(S) * cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import bisect

s=list(map(lambda x : ord(x)-97,list(input())))
t=list(map(lambda x : ord(x)-97,list(input())))
#print(s)

alpha=[[] for i in range(26)]
#print(alpha)

for index,item in enumerate(s):
    alpha[item].append(index)
    #print(alpha)

loc=-1
count=0

for index,item in enumerate(t):
    temp=bisect.bisect(alpha[item],loc)
    if len(alpha[item])==0:
        print(-1)
        exit()
    if temp==len(alpha[item]):
        count+=1
        loc=alpha[item][0]
    else:
        loc=alpha[item][temp]
    #print(loc,count)
print(loc+1+count*len(s))

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s = input()
t = input()
ns = len(s)
nt = len(t)
word = defaultdict(int)
wordnum = defaultdict(int)
for i in range(ns):
  if word[s[i]] != 0:
    word[s[i]].append(i+1)
  else:
    word[s[i]] = [i+1]
  wordnum[s[i]] += 1
cnt = 0
pnt = 0
for i in range(nt):
  x = t[i]
  if word[x] != 0:
    pos = bisect.bisect_right(word[x],pnt)
    if pos == wordnum[x] or pnt>word[x][pos]:
      cnt += 1
    if pos == wordnum[x]:
      pnt = word[x][0]
    else:
      pnt = word[x][pos]
  else:
    print(-1)
    exit()
print(cnt*ns+pnt)