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:
# -*- coding: utf-8 -*-
import bisect

def search_next_char(idxs, now, iter):
    l = len(idxs)
    next = bisect.bisect(idxs, now)
    if next >= l:
        iter += 1
        next = bisect.bisect(idxs, 0)
    return idxs[next], iter


s = input()
t = input()

set_s = set(s)
set_t = set(t)

if len(set_t - set_s) > 0:
    print(-1)
    exit()


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

now = 0
iter = 0
for c in t:
    now, iter = search_next_char(c_idx[c], now, iter)

print(iter * len(s) + now)

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = input()
t = input()
sc = [ [] for _ in range(26)]

n = len(s)
for i in range(n):
    p = ord(s[i]) - ord('a')
    sc[p].append(i+1)

for c in t:
    p = ord(c) - ord('a')
    if len(sc[p]) == 0:
        print(-1)
        exit()

ans = 0
x = 0
for c in t:
    p = ord(c) - ord('a')
    if len(sc[p]) == 0:
        print(-1)
        exit()
    tmp = bisect_right(sc[p], x)
    if tmp == len(sc[p]):
        px = x
        x = sc[p][0]
        ans += n - px + x
    else:
        px = x
        x = sc[p][tmp]
        ans += x - px
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict

S=input()
T=input()

def solve():
    obj=defaultdict(list)
    for i,s in enumerate(S):
        obj[s].append(i)

    result=1
    mx=-1
    for t in T:
        flag=True

        if not obj[t]:
            return -1

        
        bi_pos=bisect.bisect_right(obj[t],mx)
        if bi_pos==len(obj[t]):
            pos=-1
            mx=obj[t][0]
            result+=1
        else:
            pos=obj[t][bi_pos]
            mx=pos

    if pos==-1:
        pos=obj[t][0]
    return len(S)*(result-1)+pos+1
print(solve())

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
s = input()
t = input()

dict = {}
for i in range(len(s)):
    c = s[i]
    if c not in dict:
        dict[c] = []
    dict[c].append(i)

for k,v in dict.items():
    dict[k] = sorted(v)

#print(dict)

from bisect import bisect_right
def find_min_t(cur, c):
    k = bisect_right(dict[c], cur)
    if k >= len(dict[c]):
        return dict[c][0]
    else:
        return dict[c][k]

cur = -1
ans = 0
succeed = True
for c in t:
    if c not in dict:
        succeed = False
        break
    i = find_min_t(cur, c)
    #print(c, i, cur)
    if i <= cur:
        ans += len(s)
    cur = i

if succeed:
    print(ans + cur + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from bisect import *

S = input()
T = input()

ds = {}
for i,s in enumerate(S) :
    if s not in ds :
        ds[s] = [i]
    else :
        ds[s].append(i)
L = []
ind = -1
flg = 0
cnt = 0
for t in T :
    if t not in ds :
        ans = -1
        flg = 1
        break
if flg == 0 :
    for t in T :
        if ind >= ds[t][-1] :
            ind = ds[t][0]
            L.append(ind)
            cnt += 1
        else :
            ind = ds[t][bisect_right(ds[t], ind)]
            L.append(ind)
    ans = cnt * len(S) + L[-1] + 1
"""
    cnt = 0
    val = L[0]
    for i in range(1,len(L)) :
        if val >= L[i] :
            val = L[i]
            cnt += 1
"""
    
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意


ss = input()
t = input()

s = ss+ss


l = len(s)
d = [[-1]*26 for _ in range(l)]
#now = [-1]*27
prev = [-1]*27

ans = -1
for i,c in enumerate(s):
#        if now[j] == -1: continue
#        if d[now[j]][ord(c)-97] == -1:
#            d[now[j]][ord(c)-97] = i
    for k in range(max(0,prev[ord(c)-97]),i):
        d[k][ord(c)-97] = i
#    now[ord(c)-97] = i
    prev[ord(c)-97] = i

#print(now)
#print(d)

ans = ss.find(t[0])
if ans == -1:
    print(-1)
    exit()

ls = len(ss)
#print(ans)
lt = len(t)-1

res = ans
for i in range(lt):
#    print(res, d[res])
    if d[res][ord(t[i+1])-97] == -1:
        print(-1)
        exit()
    diff = d[res][ord(t[i+1])-97] - res 
    ans += diff
    res = (res+diff)%ls


print(ans+1)

Submission status: Accepted

Solution code:

import sys
#input = sys.stdin.readline

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

alpha2num = lambda c: ord(c) - ord('a') 

alpha = [[] for _ in range(26)]
for i,s in enumerate(S):
    alpha[alpha2num(s)].append(i)

import bisect
tmp = -1
N = len(S)
base = 0
for t in T:
    a = alpha2num(t)
    if len(alpha[a]) == 0:
        print(-1)
        sys.exit()
    else:
        L = len(alpha[a])        
        num = bisect.bisect_right(alpha[a],tmp)
        
        if num == L:
            base += 1
            tmp = alpha[a][0]
        else:
            tmp = alpha[a][num]
ans = N * base + tmp + 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

sset = set(s)
tset = set(t)

if not all(i in sset for i in tset):
    print(-1)
    exit()

d = {}

for x in tset:
    d[x] = sorted([j for j,y in enumerate(s) if x == y])

rep = 0
tmp = d[t[0]][0]

n = len(t)

for i in range(1,n):
    k = d[t[i]]
    x = bisect.bisect_right(k,tmp)
    if x == len(k):
        rep += 1
        tmp = k[0]
    else:
        tmp = k[x]

print(rep*len(s) + tmp +1)

Submission status: Accepted

Solution code:
from bisect import bisect_right

S = input()
T = input()

s_len = len(S)

indexs_by_char = dict([s, []] for s in (S))
for i, s in enumerate(S):
    indexs_by_char[s].append(i)
# print(indexs_by_char)
indexs_len = dict([[k, len(v)] for k, v in indexs_by_char.items()])
# print(indexs_len)

s_count = 0
current_i = -1
for t in T:
    if t not in indexs_by_char:
        print(-1)
        exit()
    j = None
    while True:
        j = bisect_right(indexs_by_char[t], current_i)
        if j < indexs_len[t]:
            break
        s_count += 1
        current_i = -1
    current_i = indexs_by_char[t][j]

print(s_len*s_count + current_i+1)

Submission status: Accepted

Solution code:
s=input()
t=input()
i=0
index=-1
ans=0
while i<len(t):
  if t[i] not in s:
    break
  elif t[i] not in s[index+1:]:
    ans+=len(s)-index+s.index(t[i])
    index=s.index(t[i])
    i+=1
  else:
    ans+=s[index+1:].index(t[i])+1
    index+=s[index+1:].index(t[i])+1
    i+=1
print(ans if i==len(t) else -1)

Submission status: Accepted

Solution code:
s = input()
t = input()
n = 0
c = 0
for e in t:
    try:
        i = s[c:].index(e)
        n += i + 1
        c = (c + i + 1) % len(s)
    except ValueError:
        try:
            i = s.index(e)
            n += len(s) - c + i + 1
            c = i + 1
        except ValueError:
            n = -1
            break
print(n)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()

len_s = len(s)
indices = defaultdict(list)
for i in range(len_s):
    indices[s[i]].append(i + 1)

letters_s = set(indices.keys())
letters_t = set(t)
if letters_t <= letters_s:
    cycles = 0
    cur = 0
    for ti in t:
        index = bisect_left(indices[ti], cur + 1)
        if index == len(indices[ti]):
            cycles += 1
            cur = indices[ti][0]
        else:
            cur = indices[ti][index]
    ans = len_s * cycles + cur
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:

from bisect import bisect_left
s= input()
t = input()

d = {}
n = len(s)
ans = 0
for i in range(len(s)):
    if s[i] not in d:
        d[s[i]] = [i+1]
    else:
        d[s[i]].append(i+1)

flag = True
bef = 0
befchar = ""
for c in t:
    if c not in d:
        flag = False
        break
    else:
        if c == befchar:
            temp = bisect_left(d[c],bef)
            # print(temp)
            if temp == len(d[c]):
                temp = d[c][0]
                ans += temp + (n-bef)
                bef = temp
            else:
                if temp +1 < len(d[c]):
                    temp = d[c][temp+1]
                    ans += temp-bef
                    bef = temp
                else:
                    temp = d[c][0]
                    ans += temp + (n - bef)
                    bef = temp
        else:
            temp = bisect_left(d[c],bef)
            if temp == len(d[c]):
                temp = d[c][0]
                ans += temp + (n-bef)
                bef = temp
            else:
                temp = d[c][temp]
                ans += temp-bef
                bef = temp
    # print(temp)
    befchar=c
    # print(ans)
# print(d)
if flag:
    print(ans)
else:
    print(-1)




# arr = [0,2,4]
# print(bisect_left(arr,2))
# print(bisect_left(arr,4))
# print(bisect_left(arr,5))

Submission status: Accepted

Solution code:
import collections
import bisect
s = input()
t = input()
if not set(t).issubset(set(s)): print(-1)
else:
    d = collections.defaultdict(list)
    for i, letter in enumerate(s):
        d[letter].append(i+1)
    prev = 0
    cnt = 0
    for target in t:
        li = d[target]
        idx = bisect.bisect_left(li, prev+1)
        if idx == len(li):
            cnt += 1
            prev = li[0]
        else:
            prev = li[idx]
    print(cnt * len(s) + prev)

Submission status: Accepted

Solution code:
# kartikay26

from math import *
from collections import *
from itertools import *
from functools import *
from random import *
def getl(t=int): return [t(x) for x in input().split()]
def get(t=int): return t(input())
alphabet = [chr(x) for x in range(ord('a'), ord('z')+1)]
alnum = lambda x: ord(x) - ord('a')

def main():
	a = input()
	b = input()
	n = len(a)
	next_ = [next_arr(alphabet[i], a) for i in range(26)]
	ptr = -1
	ans = 0
	for ch in b:
		old_ptr = ptr
		ptr = next_[alnum(ch)][ptr]
		if ptr == -1:
			print(-1)
			exit()
		if ptr <= old_ptr:
			ans += n
	print(ans+ptr+1)

def next_arr(ch, a):
	n = len(a)
	i = a.find(ch)
	if i == -1:
		return [-1] * n
	ret = [-1] * n
	while ret[prev(i,n)] == -1:
		if a[i] == ch:
			ret[prev(i,n)] = i
		else:
			ret[prev(i,n)] = ret[i]
		i = prev(i,n)
	return ret


def next(i, n):
	return (i+1) % n
def prev(i, n):
	return (i-1+n) % n

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import bisect


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


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

    dic = {"q": [], "w": [], "e": [], "r": [], "t": [], "y": [], "u": [], "i": [], "o": [], "p": [], "l": [], "k": [], "j": [
    ], "h": [], "g": [], "f": [], "d": [], "s": [], "a": [], "z": [], "x": [], "c": [], "v": [], "b": [], "n": [], "m": []}
    now = 0
    ans = 0
    # for a in t:
    #     if not a in s:
    #         print(-1)
    #         sys.exit()
    for i in range(len(s)):
        dic[s[i]].append(i+1)
    for t1 in t:
        if len(dic[t1]) < 1:
            print(-1)
            sys.exit()

        old = now
        now = dic[t1][bisect.bisect_right(dic[t1], now) % len(dic[t1])]
        if old >= now:
            ans += 1
        # print(old, now, ans)

    ans = ans*len(s)+now

    # print(dic)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ABC138E - Strings of Impurity
import sys
input = sys.stdin.readline

def main():
    S = input().rstrip()
    T = input().rstrip()
    if set(T) <= set(S):
        lim_s, lim_t = len(S) - 1, len(T)
        ans, cur, idx = 1, 0, -1
        while cur < lim_t:
            x = S[idx + 1 :].find(T[cur])
            if x == -1:
                ans += 1
                idx = -1
            else:
                idx += x + 1
                cur += 1
        ans = (ans - 1) * (lim_s + 1) + idx + 1
        print(ans)
    else:  # corner case
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

s = input().strip()
t = input().strip()
n = len(s)
m = len(t)
p = 0
q = 0
fold = 0
l = [[] for _ in range(26)]
lim = [0 for _ in range(26)] 
for i, x in enumerate(s):
	l[ord(x) - 97].append(i)
	lim[ord(x) - 97] += 1
r = [0 for _ in range(26)]
cur = -1
while (q < m):
	x = t[q]
	ind = ord(x) - 97
	#print(x, cur)
	if l[ind] == []:
		print(-1)
		exit(0)
	else:
		#print("HERE", r[ind], lim[ind])
		if r[ind] >= lim[ind]:
			fold += 1
			r = [0 for _ in range(26)]
			cur = -1
		else:
			c = l[ind][r[ind]]
			flag = True
			while (c <= cur):
				r[ind] += 1
				if r[ind] >= lim[ind]:
					flag = False
					break
				c = l[ind][r[ind]]
			if flag == False:
				fold += 1
				r = [0 for _ in range(26)]
				cur = -1
			elif c > cur:
				cur = c
				q += 1
				r[ind] += 1
			else:
				fold += 1
				r = [0 for _ in range(26)]
				cur = -1
#print(fold, n, cur)
print(fold * n + cur + 1)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

#len_s = len(s)

#alpha2num = lambda c: ord(c) - ord('a')

results = {}
for i in range(len(s)):
    results.setdefault(s[i], []).append(i+1)

#print(results)

ans = 0
cnt = 0
num = 1

for i in range(len(t)):
    #キーがない場合は-1を出力
    if not t[i] in results.keys():
        print(-1)
        exit()
    else:
        idx = bisect.bisect_right(results[t[i]],cnt)
        #print(ans, len(results[t[i]]) , idx)
        if len(results[t[i]]) <= idx:
            cnt = results[t[i]][0]
            ans = len(s)*num + cnt
            num += 1
        else:
            #print(results[t[i]][idx],results[t[i]])
            ans += results[t[i]][idx] - cnt
            cnt = results[t[i]][idx]
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left, bisect, insort_left, insort
def solve():
    S = input()
    T = input()
    if not set(T) <= set(S):
        return -1
    len_s = len(S)
    m = defaultdict(list)
    for i, s in enumerate(S):
        m[s].append(i)
    for k, v in m.items():
        m[k].append(m[k][0] + len_s)
    last = S.index(T[0])
    ans = last + 1
    for t in T[1:]:
        num = bisect(m[t], last)
        ans += m[t][num] - last
        last = m[t][num] % len_s
    return ans
print(solve())

Submission status: Accepted

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

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

n = [[] for i in range(28)]

def get_ord(c):
    return ord(c)-97

for i in range(s_len):
    ord_c = get_ord(s[i])
    n[ord_c].append(i)

#print(n)

#print("s_len",s_len)
#print("t_len",t_len)

def get_ans():
    res = 0
    for i in range(t_len):
        
        rr = res % s_len
        t_ord = get_ord(t[i])
        words = n[t_ord]
        
        if(len(words)==0):
            return -1
        if(i==0 and words[0] == 0):
            res = 0
            continue
    
        if(words[len(words)-1]<=rr):
            res += s_len - rr 
            #print("add",s_len-rr)
            rr = -1
        
        bis = bisect.bisect_right(words,rr)
        #print(bis,len(words),rr,words)
        w = words[bis]


        if(rr!=-1):
            res += w - rr
        else:
            res += w
        #print(t[i],words,rr,res)
    
    return res+1

print(get_ans())

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 昇順にソート済みのarrから、n以上の最小の要素を探索して返します。
# 存在しない場合は、Noneを返します。
def bin_gte(arr, n):
    l = 0
    r = len(arr) - 1
    c = (l+r)//2
    while l < r:
        c = (l+r)//2
        if arr[c] >= n:
            r = c
        else :
            l = c+1
    c = max(0, (l+r)//2)
    if arr[c] >= n:
        return (c, arr[c])
    else:
        return None


s = input()
t = input()
n = len(s)
m = len(t)
appears = [ [] for _ in range(26)]
for i,app in enumerate(appears):
    char = chr(ord('a') + i)
    base = 0
    while True:
        f = s.find(char, base)
        if f == -1:
            break
        app.append(f)
        base = f+1

cur = 0
loop = 0
for char in t:
    appear = appears[ord(char) - ord('a')]
    if len(appear) == 0:
        print('-1')
        exit()

    nex = bin_gte(appear, cur)

    if nex == None:
        loop += 1
        cur = appear[0]+1
    else:
        cur = nex[1]+1

print(loop * n + cur)

# print(appears)
# print(appears[ord('t') - ord('a')])

Submission status: Accepted

Solution code:
def listan(a,x):
    naga=len(a)
    if(x>=a[naga-1]):
        return -1
    if(x<a[0]):
        return a[0]
    left=0
    right=naga-1
    while(left<=right):
        center=(left+right)//2
        if(a[center]<=x and x<a[center+1]):
            return a[center+1]
        if(a[center+1]<=x):
            left=center+1
        if(a[center]>x):
            right=center-1


list=[0,1,4,5,7,9,11]
b=[1,5,10,13]
#print(listan(b,0))
s=input()
t=input()

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

taiou=[]
jisho=[]


kanou=True
for i in range(tl):
    temp=[]
    if(t[i] in jisho):
        num=jisho.index(t[i])
        taiou.append(jisho[num+1])
    else:
        for j in range(sl):
            
            if(t[i]==s[j]):
                temp.append(j)
        if(temp==[]):
            kanou=False
        jisho.append(t[i])
        jisho.append(temp)
        taiou.append(temp)
        
#print(jisho)
#print(taiou)
if(not kanou):
    print(-1)

if(kanou):
    gyou=0
    retu=-1
    for i in range(tl):
        ban=listan(taiou[i],retu)
        if(ban==-1):
            gyou+=1
            retu=taiou[i][0]
        else:
            retu=ban

    print(gyou*sl+retu+1)

Submission status: Accepted

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

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

str_repeat_num = 0
now_idx = 0
for t in T:
    if t in S[now_idx:]:
        now_idx += S[now_idx:].index(t) + 1
    else:
        str_repeat_num += 1
        now_idx = now_idx = S[:now_idx].index(t) + 1
print(len(S) * str_repeat_num + now_idx)

Submission status: Accepted

Solution code:
# ABC138E - Strings of Impurity
def main():
    S = input()
    T = input()
    if set(T) <= set(S):
        lim_s, lim_t = len(S) - 1, len(T)
        ans, cur, idx = 1, 0, -1
        while cur < lim_t:
            x = S[idx + 1 :].find(T[cur])
            if x == -1:
                ans += 1
                idx = -1
            else:
                idx += x + 1
                cur += 1
        ans = (ans - 1) * (lim_s + 1) + idx + 1
        print(ans)
    else:  # corner case
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import bisect
s = input()
t = input()
N = len(s)
dict = {}
for i in range(N):
  if s[i] in dict.keys():
    dict[s[i]].append(i)
  else:
    dict[s[i]] = [i]
cur = -1
count = 1
for i in range(len(t)):
  if t[i] not in dict.keys():
    print(-1)
    exit()
  if cur <= dict[t[i]][-1]:
    tmp = bisect.bisect_left(dict[t[i]],cur)
    cur = dict[t[i]][tmp] + 1
  else:
    count += 1
    cur = dict[t[i]][0] + 1
#  print("t[i] {} count {}, cur {}".format(t[i],count,cur))
ans = (count-1)*N + cur
print(ans if count <= 10**100 else -1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

s = input()
t = input()
s_set = set(list(s))
t_set = set(list(t))

# print(s_set)
# print(t_set)

if t_set <= s_set:
    str_dict = defaultdict(list)
    for i, cha in enumerate(s):
        str_dict[cha].append(i)
    # print(str_dict)

    times = 0
    now = 0

    for i, c in enumerate(t):
        target_char = str_dict[c]
        if target_char[-1] < now:  # 次の週の最初の文字を使用
            times += 1
            now = target_char[0]+1
        else:
            now = target_char[bisect.bisect_left(target_char, now)]+1
        # print((times, now))
    print(len(s) * times + now)

else:
    print(-1)

Submission status: Accepted

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

table = {}
for ti in t:
    table[ti] = []
    
for i, si in enumerate(s):
    # print("##", si)
    if table.get(si) != None:
        table[si].append(i)

# print("#", table)

import bisect

if [] in table.values():
    print(-1)
else:
    ans = 0
    pos = min(table[t[0]])
    for i in range(len(t) - 1):
        src = t[i]
        dst = t[i + 1]
        idx_tmp = bisect.bisect_right(table[dst], pos)
        if idx_tmp == len(table[dst]):
            ans += len(s)
            pos = table[dst][0]
        else:
            pos = table[dst][idx_tmp]
        # print("##", (src, dst), idx_tmp, pos, ans + pos + 1)
    #    
    print(ans + pos + 1)

Submission status: Accepted

Solution code:

from bisect import bisect_right as br

def main():
    S = [s for s in input()]
    T = [t for t in input()]
    slen = len(S)
    tlen = len(T)

    dic = {}
    for i in range(slen):
        if S[i] in dic:
            dic[S[i]].append(i)
        else:
            dic[S[i]] = [i]

    ans = 0
    pre = 0
    if T[0] in dic:
        if T[0] != S[0]:
            ans = dic[T[0]][0]
            pre = dic[T[0]][0]
    else:
        print(-1)
        return 

    for j in range(1,tlen):
        t = T[j]
        if t in dic:
            point = br(dic[t],pre)
            if point == len(dic[t]):
                ans += slen - pre + dic[t][0]
                pre = dic[t][0]
            else:
                if pre == dic[t] == point:
                    ans += slen
                else:
                    ans += dic[t][point] - pre
                    pre = dic[t][point]
        else:
            print(-1)
            return
    print(ans + 1)
    return 
main()

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
S = input()
T = input()
len_S = len(S)
s2i = defaultdict(list)
for i, si in enumerate(S):
    s2i[si].append(i)
ans = 1
pi = -1
for ti in T:
    si = s2i.get(ti)
    if not si:
        ans = -1
        break
    il = bisect.bisect_right(si,pi)
    if len(si) <= il:
        ans += len_S
        pi = si[0]
    else:
        pi = si[il]

if ans != -1:
    ans += pi

print(ans)

Submission status: Accepted

Solution code:
import bisect
s = list(input())
t = input()
size = len(s)


dic = {}
for c in t:
	if c in dic:
		continue
	dic[c] = [i for i,val in enumerate(s) if val==c]
	if len(dic[c]) == 0:
		print(-1)
		exit()

pos =-1 
loop = 0
for c in t:
	l = dic[c]
	#print(c,l)
	if pos < l[-1]:
		index = bisect.bisect_right(l,pos)
		pos = l[index]
	else:
		pos = l[0]
		loop += 1
	#print("pos",pos,loop)

print(loop*size + pos+1)

Submission status: Accepted

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

S = list(s)

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

idx = 0
ans = 0
l = len(s)
for i in range(len(t)):
    now = ord(t[i])-97
    if C[now] == []:
        ans = -1
        break
    up = bisect.bisect_right(C[now], idx)
    if up >= len(C[now]):
        up = bisect.bisect_right(C[now], 0)
        ans += C[now][up] + l-idx
        idx = C[now][up]
    else:
        ans += C[now][up] - idx
        idx = C[now][up]

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
s_set = set(list(s))
t_set = set(list(t))
if not t_set.issubset(s_set):
    print(-1)
else:
    ans = 0
    pre_idx = -1
    cnt = 0
    for i in range(len(t)):
        if t[i] not in s[pre_idx+1:]:
            ans += len(s)
            pre_idx = -1
            cnt = 0
        if pre_idx == -1:
            idx = s[pre_idx+1:].find(t[i])
        else:
            idx = s[pre_idx+1:].find(t[i]) + pre_idx + 1
        cnt = idx+1
        pre_idx = idx
    print(ans+cnt)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

s = ns()
t = ns()
n = len(s)
g = {}

for i in range(n):
    if s[i] not in g:
        g[s[i]] = [i]
    else:
        g[s[i]].append(i)

import bisect

a = 0
b = -1
for i in t:
    if i not in g or a >= n*(10**100):
        print(-1)
        exit()
    k = bisect.bisect_left(g[i],b)
    if k == len(g[i]):
        b = g[i][0]+1
        a += 1
    else:
        b = g[i][k]+1

print(n*a+b)

Submission status: Accepted

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

import sys
from collections import defaultdict
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()
T = input()
N = len(S)

d = defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i)
for k, v in d.items():
    d[k].append(INF)

cur = -1
ans = 0
for i, t in enumerate(T):
    if t not in d:
        print(-1)
        exit()
    idx = bisect_right(d[t], cur)
    if d[t][idx] == INF:
        ans += N
        cur = d[t][0]
    else:
        cur = d[t][idx]
ans += cur+1
print(ans)

Submission status: Accepted

Solution code:
import copy
s = input()
t = input()
if(set(t) - set(s)):
  print(-1)
  exit()

t_index = 0
s_index = 0
count = 0
copy_s = copy.deepcopy(s)
while len(t) > t_index:
  index = copy_s.find(t[t_index])
  if index >= 0:
    t_index+=1
    copy_s = copy_s[index+1:]
  else:
    copy_s = copy.deepcopy(s)    
    count += 1
print(count*len(s)+len(s)-len(copy_s))

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

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

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

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

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()

Submission status: Accepted

Solution code:
import bisect

def main():
    S = input()
    dS = {c : [] for c in 'abcdefghijklmnopqrstuvwxyz'}

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

    #

    T = input()
    ans = 0

    p = 0

    for t in T:
        if not dS[t]:
            print(-1)
            return
        if dS[t][-1] < p:
            p = 0
            ans += len(S)
        idx = bisect.bisect_left(dS[t], p)
        p = dS[t][idx] + 1
    
    print(ans + p)

main()

Submission status: Accepted

Solution code:
import bisect
s=input()
t=input()
s_set=set([i for i in s])
t_set=set([i for i in t])
if t_set-s_set&t_set:
  print(-1)
  exit()
a={}
for i in t_set:
  a[i]=[]
  for k,j in enumerate(s):
    if j==i:
      a[i].append(k)
  a[i].sort()
ans=0
j=0
for i in t:
  if a[i][-1]<j:
    ans+=len(s)
    j=0
  k=bisect.bisect_left(a[i],j)
  j=a[i][k]+1
print(ans+j)

Submission status: Accepted

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

sc = [0] * 26
tc = [0] * 26

for i in range(len(s)):
    sc[ord(s[i]) - ord("a")] += 1
for i in range(len(t)):
    tc[ord(t[i]) - ord("a")] += 1

# 不可能な場合
for i in range(26):
    if tc[i] > 0 and sc[i] == 0:
        print(-1)
        exit()


alph = [[] for _ in range(26)]
for i in range(len(s)):
    alph[ord(s[i]) - ord("a")].append(i)

ans = [0] * len(t)
pre_num = -1
for i in range(len(t)):
    num = ord(t[i]) - ord("a")
    if i > 0:
        idx = bisect.bisect_right(alph[num], pre_num)
        if idx >= len(alph[num]):
            num_idx = alph[num][0]
        else:
            num_idx = alph[num][idx]
    else:
        num_idx = alph[num][0]
    ans[i] = num_idx
    pre_num = num_idx

count = 0
pre = -1
for v in ans:
    if pre >= v:
        count += 1
    pre = v

print(count * len(s) + ans[-1] + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from bisect import bisect_left


def solve(s, t):
    a = ord('a')
    pos_list = [[] for _ in range(26)]
    for i, ch in enumerate(s):
        pos_list[ord(ch)-a].append(i)
    for ch in t:
        if not pos_list[ord(ch)-a]:
            return -1
    cc = 0
    s_len = len(s)
    for ch in t:
        pl = pos_list[ord(ch)-a]
        cc_mod = cc % s_len
        cc_ofs = (cc // s_len) * s_len
        i = bisect_left(pl, cc_mod)
        if i < len(pl):
            cc = cc_ofs + pl[i] + 1
        else:
            cc = cc_ofs + s_len + pl[0] + 1

    return cc


if __name__ == '__main__':
    s = input().strip()
    t = input().strip()

    ans = solve(s, t)

    print(ans)

Submission status: Accepted

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

s_dict = {}
from bisect import insort_right, bisect_right
for i, c in enumerate(s):
    if c in s_dict:
        insort_right(s_dict[c], i)
    else:
        s_dict[c] = [i]
#print(s_dict)

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

idx = -1
cnt = 1
bad = False
for c in t:
    if not c in s_dict:
        bad = True
        break
    try:
        idx = find_gt(s_dict[c], idx)
    except:
        idx = -1
        idx = find_gt(s_dict[c], idx)
        cnt += 1

#print(idx)
#print(cnt)
if bad:
    print(-1)
else:
    ans = len(s) * (cnt-1) + (idx+1)
    print(ans)