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:


def submit():
    s = input()
    t = input()
    char_set = set(s)
    next_char = {c: -1 for c in char_set}
    char_list = {(c, len(s)): -1 for c in char_set}

    for i in reversed(range(len(s))):
        for c in char_set:
            if c == s[i]:
                char_list[(c, i)] = i
            else:
                char_list[(c, i)] = char_list[(c, i + 1)]
            
    loop = 0
    curr = 0
    for c in t:
        # 実現不可能
        if c not in char_set:
            print(-1)
            return
        if char_list[(c, curr)] < 0:
            loop += 1
            curr = 0
        curr = char_list[(c, curr)] + 1
    print(loop * len(s) + curr)
        

submit()

Submission status: Accepted

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

NS = len(S)
NT = len(T)
alp = {}
for i in range(26):
    alp[chr(97+i)] = i
D = [[] for i in range(26)]
for i in range(NS):
    D[alp[S[i]]].append(i)
inf = float("inf")
for i in range(26):D[i].append(inf)
k = 0
l = -1
ans = -1
for i in range(NT):
    index = alp[T[i]]
    if D[index] == [inf]:break
    b = bisect(D[index],l)
    if D[index][b]==inf:
        k += 1
        l = D[index][0]
    else:
        l = D[index][b]
    if i==NT-1:ans = k*NS+l+1
print(ans)

Submission status: Accepted

Solution code:
import bisect
w1=input()
w2=input()
d={}
for i in list("qwertyuiopasdfghjklzxcvbnm"):
  d[i]=[]
for i in range(len(w1)):
  d[w1[i]].append(i+1)
num=len(w1)
for i in w2:
  if d[i]==[]:
    print(-1)
    exit()
now=0#w1の何文字目か
count=0#w1を何回繰り返しているか
num2=len(w2)
for i in range(num2):
  d1=d[w2[i]]
  if d1[-1]<now:
    now=d1[0]+1
    count+=1
  else:
    index=bisect.bisect_left(d1,now)
    now=d1[index]+1
print(count*num+now-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
t = input()
counter = 0
idx = -1
if set(t) <= set(s):
  for i in range(len(t)):
    idx = s.find(t[i],idx+1)
    if idx == -1:
      counter += 1
      idx = s.find(t[i],idx+1)
  print(counter * len(s) +idx +1)
else:
  print(-1)

Submission status: Accepted

Solution code:
s = input()
t = input()
len_s = len(s)
a = ord('a')
dictionary = {chr(a + i): [[], 0] for i in range(26)}
for i in range(len_s):
  dictionary[s[i]][0].append(i)
  dictionary[s[i]][1] += 1
repeat = 0
cur_index = -1
for c in t:
  indices, len_indices = dictionary[c]
  if len_indices == 0:
    repeat = 0
    cur_index = -2
    break
  inf = -1
  sup = len_indices
  while sup - inf > 1:
    x = (inf + sup) // 2
    if indices[x] > cur_index:
      sup = x
    else:
      inf = x
  if sup == len_indices:
    repeat += 1
    cur_index = indices[0]
  else:
    cur_index = indices[sup]
print(len_s * repeat + cur_index + 1)

Submission status: Accepted

Solution code:
from bisect import *
s = input()
t = input()
pos = {}
for j,i in enumerate(s):
  if i in pos.keys():
  	pos[i].append(j+1)
  else:
    pos[i] = [j+1]
n = len(s)
for i in pos.keys():
  pos[i].append(pos[i][0] + n)
ans = 0
last = 0
for i in t:
  if not i in s:
    print(-1)
    exit()
  last = pos[i][bisect(pos[i],last)]
  if last > n:
    last -= n
    ans += n
print(ans + last)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    s = input()
    s = [ord(i) - ord("a") for i in s]
    N = len(s)
    t = input()
    t = [ord(i) - ord("a") for i in t]

    posit = {}
    for i in range(0, ord("z")-ord("a")+1):
        posit[i] = []

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

    ans = 0
    cur = -1
    for src_target in t:
        if not posit[src_target]:
            return -1
        if posit[src_target][-1] <= cur: # 使い捨て処理
            ans += (N-cur-1)
            cur = -1
            #print("a", ans)

        idx = bisect_left(posit[src_target], cur+1) # 次のがあるindexを探す
        next = posit[src_target][idx]
        ans += next - cur
        cur = next
        #print(ans, src_target)

    return ans



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans1=0
ans2=0

ss=s*2

for i in range(len(t)):
    a=ss.find(t[i],ans2)
    if a==-1:
        ans=-1
        break
    if a>=len(s):
        ans1+=1
    ans2=a%(len(s))+1
    ans=ans1*len(s)+ans2
print(ans)

Submission status: Accepted

Solution code:
import bisect
s = list(input())
t = list(input())
ls = len(s)
check = [[] for i in range(26)]
for i in range(len(s)):
    o = ord(s[i])-ord("a")

    check[o].append(i+1)
ans = 0
c1 = 0

for i in t:
    o =ord(i)-ord("a")
    if check[o]:
        x = bisect.bisect_right(check[o],ans) 
        if x == len(check[o]):
            c1 += 1
            ans = check[o][0]
        else:
            ans = check[o][x]
            

    else:
        print(-1)
        exit()
 
print(ans+c1*ls)

Submission status: Accepted

Solution code:
sl = list(input())
tl = list(input())
n = len(sl)
from collections import defaultdict
dic = defaultdict(list)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
l = len(s)
sl = [[] for _ in range(26)]
for i in range(l):
	j = ord(s[i])-97
	sl[j].append(i)
sord = [[-1 for _ in range(l)] for _ in range(26)]
checksord = [0 for _ in range(26)]
for i in range(26):
	for j in range(len(sl[i])):
		cnt = sl[i][j]
		for q in range(checksord[i], cnt):
			sord[i][q] = cnt
		checksord[i] = cnt

for i in range(26):
	for j in range(l):
		if (sl[i] != []) & (sord[i][j] == -1):
			sord[i][j] = sl[i][0] + l

#print(sord)

j = ord(t[0])-97
if sl[j] == []:
	ans = -1
else: 
	ans = sl[j][0]

if ans != -1:
	for i in range(1, len(t)):
		j = ord(t[i])-97
		if sl[j] == []:
			ans = -1
			break
		else:
			w = ans % l
			ans = ans - w + sord[j][w]
			#print(ans)

if ans == -1:
	print(ans)
else:
	print(ans+1)

Submission status: Accepted

Solution code:
import sys
s=input()
ss=s+s
t=input()
l=len(s)
d={}
for i in range(26):
    d[chr(ord("a")+i)]=i
ref=[[] for _ in range(26)]
for i in range(2*l):
    ref[d[ss[i]]].append(i)

for i in range(26):
    if ref[i]==[]: ref[i].append(-1)

tmp=[0 for i in range(26)]
next=[[-1]*26 for i in range(l)]
for i in range(l):
    tmp[d[s[i]]]+=1
    for j in range(26):
        next[i][j]=ref[j][tmp[j]]

p=s.find(t[0])
if p==-1: print(-1);sys.exit()
ans=p

for i in range(1,len(t)):
    x=d[t[i]]
    q=next[p][x]
    if q==-1: print(-1);sys.exit()
    ans+=-p+q
    p=q%l
print(ans+1)

Submission status: Accepted

Solution code:
import sys
s=input()
t=input()
l=len(s)
d={}
for i in range(26):
    d[chr(ord("a")+i)]=i
ref=[[] for _ in range(26)]
for i in range(l):
    ref[d[s[i]]].append(i)

for i in range(26):
    if ref[i]==[]: ref[i].append(-1)

tmp=[0 for i in range(26)]
next=[[-1]*26 for i in range(l)]
for i in range(l):
    x=d[s[i]]
    tmp[x]=(tmp[x]+1)%len(ref[x])
    for j in range(26):
        next[i][j]=ref[j][tmp[j]]

p=s.find(t[0])
ans=p

if p==-1: print(-1);sys.exit()
for i in range(1,len(t)):
    x=d[t[i]]
    q=next[p][x]
    if q==-1: print(-1);sys.exit()
    ans+=-p+q
    if p>=q: ans+=l
    p=q
print(ans+1)

Submission status: Accepted

Solution code:
S = input()
T = input()
dic = {}
for i,s in enumerate(S):
  if s not in dic:
    dic[s] = [i]
  else:
    dic[s].append(i)
#print(dic)
ind = -1
loop = 0
import bisect
for t in T:
  if t not in dic:
    ans = -1
    break
  if dic[t][-1]<=ind:
    loop += 1
    ind = dic[t][0]
  else:
    i = bisect.bisect_right(dic[t],ind)
    ind = dic[t][i]
  #print(ind)
#print(loop,ind)
else:
  ans = len(S)*loop+ind+1
          
print(ans)   

#print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
# https://img.atcoder.jp/abc138/editorial.pdf
# https://www.youtube.com/watch?v=lWETOlGiuaI
# このコードは公式解説動画をまんまpythonにしたものです。

# 解説動画
# s = abacaababc (10文字)の場合は
# a: [0, 2, 4, 5, 7, 10, 12, 14, 15, 17]
# b: [1, 6, 8, 11, 16, 18]
# c: [3, 9, 13, 19]
# という二重配列をまず作る。

# 例えばt = 'bbcca'だと
# 現在位置0、bを探す→1
# 現在位置1、bを探す→6
# 現在位置6、cを探す→9
# 現在位置9、cを探す→13(3に戻す)
# 現在位置3、aを探す→4
# で答えは14。


# 解説pdf曰く：
# next(ch, i):=「s'のi文字目以降で文字種chが最初に現れる位置」を
# をO(文字種数×|S|)かけて事前に全て求める

# 文字の先頭に戻る可能性があるので、2回連結しておくと処理が楽になる

from bisect import bisect_left

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

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

for i in range(n):
    index_list[ord(s[i]) - ord('a')].append(i)
for i in range(n):
    index_list[ord(s[i]) - ord('a')].append(i+n)

p = 0  # p以降
ans = 0
for j in range(m):
    ch = ord(t[j]) - ord('a')
    if len(index_list[ch]) == 0:
        # t内に出現する文字が、sに全く登場しないので、不可
        print(-1)
        exit()
    next_pos = bisect_left(index_list[ch], p)
    p = index_list[ch][next_pos] + 1
    if p >= n:
        p -= n
        ans += n
    # print(p)

ans += p
print(ans)

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

LS = len(S)
LT = len(T)

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

for i in range(LS):
    n = ord(S[i]) - 97
    POS[n].append(i)


cnt = 0
prev = -1
for i in range(LT):
    n = ord(T[i]) - 97

    if not POS[n]:
        print(-1)
        exit()

    ps = POS[n]
    p = bisect.bisect_right(ps, prev)

    if p == len(ps):
        cnt += 1
        p = bisect.bisect_right(ps, -1)

    prev = ps[p]


ans = cnt * LS + prev + 1
print(ans)

Submission status: Accepted

Solution code:
import sys

import bisect

from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math


# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    sd = defaultdict(list)

    sl = len(s)

    for i in range(sl):
        c = s[i]
        sd[c].append(i+1)

    tl = len(t)
    prev = 0

    ans = 0

    for i in range(tl):
        c2 = t[i]
        appear = sd[c2]
        if len(appear) == 0:
            print(-1)
            sys.exit()

        appear_max = appear[-1]
        if appear_max <= prev:
            nxt = appear[0]
        else:
            nxt = appear[bisect.bisect_right(appear, prev)]
        forward = nxt - prev
        if forward <= 0:
            forward += sl
        ans += forward
        prev = nxt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
n = len(s)
l = [[]for i in range(26)]

for i, c in enumerate(s * 2):
    l[ord(c) - ord('a')].append(i)


from bisect import *

shukai = 0
now = 0

t = input()
for c in t:
    x = ord(c) - ord('a')
    if len(l[x]) == 0:
        print(-1)
        exit()
    i = bisect_left(l[x], now)
    now = l[x][i] + 1

    if now >= n:
        now -= n
        shukai += 1


print(shukai * n + now)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
d = {}
if set(t) <= set(s):
    for c in set(s):
        d[c] = []
    for i,c in enumerate(s):
        d[c].append(i)
    ret = 0
    for i,c in enumerate(t):
        if i==0:
            loc = d[t[0]][0]
        else:
            nx_idx = bisect.bisect_right(d[c], loc)
            if nx_idx == len(d[c]):
                ret += 1
                nx_idx = 0
            nx_loc = d[c][nx_idx]
            loc = nx_loc
    print(ret*len(s) + loc + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import bisect
s = list(input())
t = list(input())
dic = {}
for i, j in enumerate(s):
    if j in dic:
        dic[j].append(i)
    else:
        dic[j] = [i]
loop = 0
if set(t) <= set(s):
    for i in range(len(t)):
        if i==0:
            idx = dic[t[0]][0]
        else:
            lis = dic[t[i]]
            idx2 = bisect.bisect_right(lis, idx)
            if idx2 == len(lis):
                loop += 1
                idx = lis[0]
            else:
                idx = lis[idx2]
    print(loop*len(s) + idx + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import bisect

s = list(input())
t = list(input())

dic = {}
for i, j in enumerate(s):
    if j in dic:
        dic[j].append(i)

    else:
        dic[j] = [i]

loop = 0
try:
    for i in range(len(t)):
        if i == 0:
            idx = dic[t[0]][0]

        else:
            lis = dic[t[i]]
            idx2 = bisect.bisect_right(lis, idx)
            if idx2 == len(lis):
                loop += 1
                idx = lis[0]

            else:
                idx = lis[idx2]
    # print(idx)

    print(len(s) * loop + idx + 1)
except:
    print(-1)

Submission status: Accepted

Solution code:
from bisect import bisect_left
s = input()
t = input()
dic = {}
for ind, c in enumerate(s):
    if c in dic:
        dic[c].append(ind)
    else:
        dic[c] = [ind]
loop = 0
ind = 0
try:
    for c in t:
        if ind > dic[c][-1]:
            ind = dic[c][0] + 1
            loop += 1
            continue
        tmp = bisect_left(dic[c], ind)
        ind = dic[c][tmp] + 1
    print(len(s)*loop+ind)
except:
    print(-1)

Submission status: Accepted

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

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

S = sr()
T = sr()
S_set = set(S)
T_set = set(T)
if len(T_set - S_set) > 0:
    print(-1); exit()

#これ以降は必ず部分列が出来る
dict_S = defaultdict(list)
for i, s in enumerate(S):
    dict_S[s].append(i)

cur = -1
lenS = len(S)
answer = 0
for t in T:
    cur += 1
    answer += 1
    L = dict_S[t]
    i = bisect_left(L, cur)
    if i == len(L):
        answer += lenS - cur + L[0]
        cur = L[0]
    else:
        answer += L[i] - cur
        cur = L[i]

print(answer)
# 07

Submission status: Accepted

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

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

ans = 0
spos = -1
for c in t:
    if c not in sdict:
        print(-1)
        exit()
    tt = bisect_right(sdict[c], spos)
    if tt == len(sdict[c]):
        # print('-',tt)
        tt = bisect_right(sdict[c], -1)
        ans += len(s)
    # print(c, spos, sdict[c], tt)
    spos = sdict[c][tt]

print(ans + spos + 1)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict

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

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

d=defaultdict(list)
for i,s in enumerate(S):
  d[s].append(i)
start=-1
ans=0
for i in T:
  p=bisect.bisect_right(d[i],start)
  le=len(d[i])
  if p==le:
    ans+=(L-start-1)+(d[i][0]+1)
    start=d[i][0]    
  else:
    ans+=d[i][p]-start
    start=d[i][p]
print(ans)

Submission status: Accepted

Solution code:
#138_E
from bisect import bisect_left, bisect_right
#leftはある数未満,rightはある数以下を返す
s = input()
t = input()
if set(s) >= set(t):
    al_idx = [[] for _ in range(26)]
    ss = s * 2
    alp = 'abcdefghijklmnopqrstuvwxyz'
    for i in range(len(ss)):
        al_idx[alp.index(ss[i])].append(i)
    
    tmp = -1
    ans = 0
    for j in range(len(t)):
        idx = alp.index(t[j])
        cur = bisect_right(al_idx[idx], tmp)
        ans += al_idx[idx][cur] - tmp
        tmp = al_idx[idx][cur] % len(s)
        
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: UTF-8 -*-
import math
import bisect
# f=open("test.txt")
# line=f.readline()
# lists=[]
# while line:
#     lists.append("".join(list(line)[:-1]))
#     line=f.readline()
# 
# f.close()
# 
# s=lists[0]
# t=lists[1]

s=input()
t=input()

alpha=list("abcdefghijklmnopqrstuvwxyz")

dic_s={alpha[i]:0 for i in range(26)}
dic_t={alpha[i]:0 for i in range(26)}

a={alpha[i]:[] for i in range(26)}
b={alpha[i]:[] for i in range(26)}


for i in range(len(s)):
  
    if dic_s[s[i]]==0:
        dic_s[s[i]]=+1
    a[s[i]].append(i+1)


for j in range(len(t)):
    
    if dic_t[t[j]]==0:
        dic_t[t[j]]=+1
    b[t[j]].append(j+1)
for i in range(26):
	a[alpha[i]].append(10**9)
flag=True

for i in range(26):
    if dic_t[alpha[i]]>0 and dic_s[alpha[i]]==0:
        flag=False

place=[0,0]

if flag:
    #文字を構成できる場合
    for i in range(len(t)):
        string=t[i]
        num=bisect.bisect_right(a[string],place[0])  
        if a[string][num]==10**9:
            place[1]+=1
            place[0]=a[string][0]
        else:
            place[0]=a[string][num]
  

    print(place[0]+place[1]*len(s))

else:
    #構成できない場合
    print(-1)

Submission status: Accepted

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

s = input().rstrip()
t = input().rstrip()
n = len(s)
m = len(t)

from collections import deque

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = deque([])


for i in range(n):
    dic[s[i]].append(i + 1)

cnt = 0
res = 0
from bisect import bisect

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = bisect(dic[i], cnt)
    if idx >= len(dic[i]):
        res += 1
        cnt = dic[i][0]
    else:
        cnt = dic[i][idx]

print(n * res + cnt)

Submission status: Accepted

Solution code:
# -*- coding: UTF-8 -*-
import math
import bisect
# f=open("test.txt")
# line=f.readline()
# lists=[]
# while line:
#     lists.append("".join(list(line)[:-1]))
#     line=f.readline()
# 
# f.close()
# 
# s=lists[0]
# t=lists[1]

s=input()
t=input()

alpha=list("abcdefghijklmnopqrstuvwxyz")

dic_s={alpha[i]:0 for i in range(26)}
dic_t={alpha[i]:0 for i in range(26)}

a={alpha[i]:[] for i in range(26)}
b={alpha[i]:[] for i in range(26)}


for i in range(len(s)):
  
    if dic_s[s[i]]==0:
        dic_s[s[i]]=+1
    a[s[i]].append(i+1)


for j in range(len(t)):
    
    if dic_t[t[j]]==0:
        dic_t[t[j]]=+1
    b[t[j]].append(j+1)
for i in range(26):
	a[alpha[i]].append(10**9)
flag=True

for i in range(26):
    if dic_t[alpha[i]]>0 and dic_s[alpha[i]]==0:
        flag=False

place=[0,0]

if flag:
    #文字を構成できる場合
    for i in range(len(t)):
        string=t[i]
        num=bisect.bisect_right(a[string],place[0])  
        if a[string][num]==10**9:
            place[1]+=1
            place[0]=a[string][0]
        else:
            place[0]=a[string][num]
  

    print(place[0]+place[1]*len(s))

else:
    #構成できない場合
    print(-1)

Submission status: Accepted

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

alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {char: i for i, char in enumerate(alph)}

set_ = set(list(s))
for char in t:
    if char not in set_:
        print(-1)
        exit()

next_ = [[0] * 26 for i in range(n + 1)]
for i in range(n)[::-1]:
    for j, char in enumerate(alph):
        if s[i] == char:
            next_[i][j] = i + 1
        else:
            next_[i][j] = next_[i + 1][j]

ans = 0
pos = 0
for char in t:
    if next_[pos][to_int[char]] == 0:
        ans += len(s)
        pos = next_[0][to_int[char]]
    else:
        pos = next_[pos][to_int[char]]
print(ans + pos)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
sub = s+s
dp = []
for i in range(len(s)):
    d = [10**15]*26
    dp.append(d)
index = [[] for i in range(26)]
for i in range(len(sub)):
    index[ord(sub[i])-97].append(i)
for i in range(len(s)):
    cur = s[i]
    for j in range(26):
        if len(index[j]) != 0:
            k = bisect.bisect_right(index[j], i)
            dp[i][j] = index[j][k]-i
if s[0] == t[0]:
    ans = 1
else:
    ans = dp[0][ord(t[0])-97]+1
if dp[0][ord(t[0])-97] != 10**15 and dp[0][ord(t[0])-97] >= len(s):
    next = dp[0][ord(t[0])-97]-len(s)
else:
    next = dp[0][ord(t[0])-97]
if next == 10**15:
    print(-1)
    exit()
else:
    flag = True
for i in range(1,len(t)):
    cur = next
    if dp[cur][ord(t[i])-97] == 10**15:
        flag = False
        break
    else:
        ans += dp[cur][ord(t[i])-97]
        if cur + dp[cur][ord(t[i])-97] >= len(s):
            next = cur + dp[cur][ord(t[i])-97] - len(s)
        else:
            next = cur + dp[cur][ord(t[i])-97]
if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

import bisect
from collections import defaultdict
d = defaultdict(list)
for i in range(len(s)):
    d[s[i]].append(i)

#print(d)
now=-1
cnt=0
for i in range(len(t)):
    if len(d[t[i]])==0:
        print(-1)
        exit()

    ind = bisect.bisect_right(d[t[i]],now)
#    print(now,ind)
    if ind==len(d[t[i]]):
        ind = bisect.bisect_right(d[t],0)
        cnt+=1
#    print(t[i],cnt)
    now=d[t[i]][ind]

print(cnt*len(s) +now +1)

#print(cnt,len(s), d[t[-1]])

Submission status: Accepted

Solution code:
from bisect import bisect_right
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  for i in range(n):
    if len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
  cnt=0
  inde=-1
  for i in range(n):
    l=len(lindex[ord(t[i])-97])
    idx=bisect_right(lindex[ord(t[i])-97],inde)
    if l==idx:
      cnt+=1
      inde=lindex[ord(t[i])-97][0]
    else:
      inde=lindex[ord(t[i])-97][idx]
  return print(m*cnt+inde+1)
if __name__=='__main__':
  main()

Submission status: Accepted

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

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

from collections import defaultdict
import bisect

def main():
	s=input().rstrip().decode('utf-8')
	t=input().rstrip().decode('utf-8')

	D=defaultdict(list)

	for i in range(len(s)):
		D[s[i]].append(i+1)

	now=0
	cnt=0

	for i in t:
		if D[i]==[]:
			print(-1)
			exit(0)
		else:
			idx=bisect.bisect_right(D[i],now)
			try:
				now=D[i][idx]
			except:
				now=D[i][0]
				cnt+=1
	print(cnt*len(s)+now)
















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import bisect
def main():
    input = sys.stdin.readline
    s = input().rstrip()
    t = input().rstrip()

    letters = set(t)
    indices = dict()
    for l in letters:
        lst = []
        left = 0
        while left < len(s):
            i = s.find(l, left)
            if i < 0: break
            lst.append(i)
            left = i+1
        if not lst:
            print(-1)
            exit()
        indices[l] = lst
    
    offset = 0
    cycle = 0
    for l in t:
        ind = indices[l]
        i = bisect.bisect_left(ind, offset)
        if i < len(ind):
            offset = ind[i] + 1
        else:
            offset = ind[0] + 1
            cycle += 1
        if offset >= len(s):
            offset %= len(s)
            cycle += 1

    print(len(s)*cycle + offset)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

S = input()
T = input()

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

ans = 0
i = 0

for t in T:
    if not d[t]:
        print(-1)
        exit()

    if i >= d[t][-1]:
        ans += len(S)
        i = d[t][0]
        continue

    pos = bisect.bisect_right(d[t], i)
    i = d[t][pos]

ans += i
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

s = input()
t = input()
idx = [[] for _ in range(26)]
for i in range(len(s)):
    c = ord(s[i]) - ord('a')
    idx[c].append(i)
count = 0
index = -1
for i in range(len(t)):
    c = ord(t[i]) - ord('a')
    if len(idx[c]) == 0:
        print(-1)
        exit()
    j = bisect_left(idx[c], index+1)
    if j == len(idx[c]):
        count += 1
        index = idx[c][0]
    else:
        index = idx[c][j]
print(count*len(s) + index + 1)

Submission status: Accepted

Solution code:
s=input()
t=input()
ls,lt=len(s),len(t)
if not set(t)<=set(s):print(-1);exit()
co=0
ind=-1
for i in range(lt):
  ind=s.find(t[i],ind+1)
  if ind==-1:
    ind=s.find(t[i])
    co+=1
print(co*ls+ind+1)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict


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

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

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

idx = -1
ans = 0
for t in T:
    pos = bisect.bisect_right(d[t], idx)
    if pos == len(d[t]):
        ans += L - idx - 1 + d[t][0] + 1
        idx = d[t][0]
    else:
        ans += d[t][pos] - idx
        idx = d[t][pos]

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

s = input()
t = input()

l = len(s)

ss = s * 2
let = [[] for _ in range(26)]
for i, e in enumerate(ss, 1):
    idx = ord(e) - ord("a")
    let[idx].append(i)

for e in t:
    idx = ord(e) - ord("a")
    if not let[idx]:
        print(-1)
        exit()

i = 1
times = 0
for e in t:
    j = ord(e) - ord("a")
    choose = bisect_left(let[j], i)
    q, r = divmod(let[j][choose], l)
    times += q
    i = r + 1

ans = times * l + i - 1
print(ans)

Submission status: Accepted

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i + 1)

out = 0
cnt = -1
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        """
        for l in dic[t]:
            if cnt < l:
                V[i] = l
                cnt = l
                break
        else:
            cnt = dic[t][0]
        """

        idx = bisect.bisect(dic[t], cnt)
        if idx == len(dic[t]):
            V[i] = dic[t][0]
            cnt = dic[t][0]
        else:
            V[i] = dic[t][idx]
            cnt = dic[t][idx]

    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] <= V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * (cnt + 1))
    else:
        print(len(S) * cnt + V[-1])
a = 0