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 copy


def main():
    s = input()
    ss = s + s
    t = input()
    if not set(sorted(t)) <= set(sorted(s)):
        print(-1)
        return
    cnt_s = {}
    cnt_t = {}
    pos = {}  # [({}) for x in range(len(s))]
    for i in range(len(ss)):
        c = ss[i]
        if c not in cnt_s:
            cnt_s[c] = 0
            pos[c] = []
        cnt_s[c] += 1
        pos[c].append(i)
    # for k in pos.keys():
    #     pos[k].reverse()
    # org_pos = copy.deepcopy(pos)
    ret = 0
    tmp = -1
    for i in range(len(t)):
        c = t[i]
        if pos[c][0] > tmp:
            tmp = pos[c][0]
            continue
        l = 1
        r = len(pos[c]) - 1
        while not l == r:
            p = (l + r) // 2
            if pos[c][p] > tmp:
                r = p
            if pos[c][p] <= tmp:
                l = p + 1
        tmp = pos[c][l]
        if tmp >= len(s):
            ret += len(s)
            tmp -= len(s)
    ret += tmp + 1
    print(ret)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(S, T):
    from bisect import bisect_right, bisect_left
    N = len(S)
    a = ord('a')
    S_ = S
    S = [ord(c)-a for c in S]
    T_ = T
    T = [ord(c)-a for c in T]
    index = [[] for i in range((ord('z')-ord('a')+1))]
    for i, c in enumerate(S):
        index[c].append(i)

    for t in T:
        if len(index[t]) == 0:
            return -1

    prev = T[0]
    prevIndex = index[prev][0]
    find = bisect_left
    offset = 0
    for i in range(1, len(T)):
        t = T[i]
        indexT = index[t]
        found = find(indexT, prevIndex+1)
        #print(offset, "%d:'%c'"%(i,T_[i]), "prevIndex=%d:'%c'"%(prevIndex, S_[prevIndex]), "found=%d/%d"%(found,len(indexT)), indexT)
        if found== len(indexT):
            prevIndex = indexT[0]
            offset += 1
        else:
            prevIndex = indexT[found]
        #print("%d:%c"%(i, T_[i]), offset, prevIndex)

    #print(offset, prevIndex, N, offset*N+prevIndex+1)
    return offset*N+prevIndex+1

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

print(solve(S, T))

Submission status: Accepted

Solution code:
import sys

def solve():
    s = input()
    t = input()
    alphabet = ["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"]
    convert = dict()
    for i in range(26):
        convert[alphabet[i]] = i

    behind = [{i:-1 for i in range(26)} for _ in range(len(s) + 1)]
    canuse = set()
    for i in reversed(range(len(s))):
        for j in range(26): behind[i][j] = behind[i+1][j]
        behind[i][convert[s[i]]] = i
        canuse |= {s[i]}
    
    k = 0
    counter = 0
    for i in range(len(t)):
        if t[i] not in canuse:
            print(-1)
            break
        else:
            if behind[counter][convert[t[i]]] > -1:
                counter = behind[counter][convert[t[i]]] + 1
            else:
                k += 1
                counter = behind[0][convert[t[i]]] + 1
    else: print(k * len(s) + counter)
    #print(behind)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def counter(list_1,list_2,length):
    count = 0
    m = 0
    for n in list_1:
        if m == length:
            count += 1
            m = 0
        m = list_2[n][m]
        if m == -1 :
            count += 1
            m = list_2[n][0]
    return count * length + m
s = input()
le_s = len(s)
t = input()
l_t = [ord(x)-97 for x in t]
s_t = set(l_t)
l_s = [[-1 for p in range(le_s)] for _ in range(26)]
s_s =set()
i = 1
l_c = [0 for _ in range(26)]
for y in s:
    z = ord(y)-97
    if z in s_t:
        l_s[z][l_c[z]:i] = [i for a in range(i - l_c[z])]
        l_c[z] = i
        s_s.add(z)
    i += 1
if s_t != s_s:
    print(-1)
    exit()
print(counter(l_t,l_s,le_s))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def bs(arr, val):
	l, h = 0, len(arr)-1
	ans = -1
	while l <= h:
		m = l + h >> 1
		if arr[m] > val:
			ans = m
			h = m - 1
		else:
			l = m + 1
	return ans

s = sys.stdin.readline().strip()
n = len(s)

t = sys.stdin.readline().strip()

occurence = defaultdict(list)
for i in range(n):
	occurence[s[i]].append(i+1)

def solve():
	folds = 0
	cur_ptr = 0

	for ele in t:
		indexes = occurence[ele]
		if not indexes: return -1

		idx = bs(indexes, cur_ptr)
		if idx != -1: 
			cur_ptr = indexes[idx]
		else:
			folds += 1
			cur_ptr = indexes[0]
		# print(ele, cur_ptr, folds)
	ans = folds*(n) + cur_ptr
	return ans

print(solve())

Submission status: Accepted

Solution code:
import bisect

def ctoi(char):
  return ord(char) - 97


#素材
ingredients = input()
ingredients_len = len(ingredients)
#つくりたいもの
recipe = input()
recipe_len = len(recipe)

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

# 素材のアルファベット分布リストをつくる
for i in range(ingredients_len):
  alpha_idx = ctoi(ingredients[i])
  alphabets[alpha_idx].append(i)

ingredients_counter = [0] * 26
for i in range(26):
  ingredients_counter[i] = len(alphabets[i])
  
ingredients_idx_list = []
flag = True
ingredients_pointer = -1

for i in range(recipe_len):
  alpha_idx = ctoi(recipe[i])
  if ingredients_counter[alpha_idx] == 0:
    flag = False
    break
  #今のingredients_pointerより右側に使える素材があるか探す
  pointer_candidate_idx = bisect.bisect_right(alphabets[alpha_idx], ingredients_pointer)
  #右側に無かった。ループして先頭のを使ってどうぞ
  if pointer_candidate_idx == ingredients_counter[alpha_idx]:
    ingredients_pointer = alphabets[alpha_idx][0]
  else:
    ingredients_pointer = alphabets[alpha_idx][pointer_candidate_idx]
  ingredients_idx_list.append(ingredients_pointer)

if flag == False:
  print(-1)
else: 
  loop = 0
  idx = ingredients_idx_list[0]
  #idxのリセット分ループを数える。左より右が小さかったらループ
  for i in range(1, recipe_len):
    if ingredients_idx_list[i] <= idx:
      loop += 1
    idx = ingredients_idx_list[i]
  # ループx素材の長さ + つくりたいものの最後の文字のインデックス(に、+１)
  print(loop * len(ingredients) + ingredients_idx_list[-1] + 1)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

s = input()
t = input()
n = len(s)
s*=2

i = ans = 0
for c in t:
    d = s[i:].find(c)
    if d == -1:
        print(-1)
        exit()
    ans += d+1
    i += d+1
    if i >= n: i -= n
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

s = input()
n = len(s)
t = input()
s*=2

ans = 0
for c in t:
    d = s[ans%n:].find(c)
    if d == -1:
        print(-1)
        exit()
    ans += d+1
print(ans)

Submission status: Accepted

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

s = input().rstrip()
t = input().rstrip()
d = defaultdict(list)

for i,c in enumerate(s):
    d[c].append(i)
ans = 0
ind = -1
for c in t:
    #print("c=",c,"d[c]=",d[c])
    if not d[c]:
        ans = -1
        break
    ins = bisect.bisect_left(d[c],ind+1)
    if ins < len(d[c]):
        ind =d[c][ins]
     #   print("ins=",ins,end = "")
    else:
      #  print("追加",end = "")
        ans += len(s)
        ind = d[c][0]
    #print("ind=", ind)
    #print()
else:
    ans += ind+1

print(ans)

Submission status: Accepted

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

count = 0
ind = -1
if set(t) <= set(s):
    for i in range(len(t)):
        ind = s.find(t[i], ind+1)
        if ind == -1:
            count += 1
            ind = s.find(t[i], ind+1)
    print(count*len(s) + ind+1)

else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import bisect

ss = input()
t = input()
n = len(ss)
cnt = {}
s = ss*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

idx = 0
ten = 0
#print(cnt)
for z in t:
    if z not in ss:
        print(-1)
        sys.exit()

    idx = cnt[z][bisect.bisect_left(cnt[z], idx)] + 1

    if idx>=n:
        idx -= n
        ten += 1

    #print(idx, z, ten)

suffix = idx + ten * n

print(suffix)

Submission status: Accepted

Solution code:
import bisect

ss = input()
tt = input()

def main(ss, t):
	d = {}
	s_uq = set(ss)
	for t in set(tt):
		if t not in s_uq:
			print(-1)
			return
		d[t] = []

	
	for i, s in enumerate(ss):
		if s in d.keys():
			d[s].append(i)

	max_d = {key:max(val) for (key, val) in d.items()}
	
	loop_cnt = 0
	idx = -1
	for t in tt:
		if idx >= max_d[t]:
			loop_cnt += 1
			idx = -1
		idx = d[t][bisect.bisect_right(d[t], idx)]

	print(loop_cnt * len(ss) + idx + 1)
		
main(ss, tt)

Submission status: Accepted

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

temp = s[:]
count = 0
ans = 0

for i in range(len(t)):
    a = s.find(t[i])
    if a == -1:
        print(-1)
        exit()

while count < t_length:
    value = temp.find(t[count])
    if value == -1:
        ans += len(temp)
        temp = s[:]
    
    else:
        ans += value + 1
        count += 1
        temp = temp[value + 1:]

print(ans)

Submission status: Accepted

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

x = len(s)
y = len(t)

a = 0
b = x
c = 0
a0 = 0


for i in range(0,y):
  while True:
    #先頭からの位置
    a=s.find(t[i:i+1],a0)+1
    if a <= 0:
      a=s.find(t[i:i+1])+1
    if a <= 0:
      print("-1")
      exit()
    
    if a<=a0:
      c=c+a+b
    else:
      c=c+a-a0
    b=x-a
    a0=a
    break
    
print(c)

Submission status: Accepted

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

alphabet = set(s)
if any(c not in alphabet for c in t):
    print(-1)
    exit()

N = len(s)

# leftmost[c] = the position of the leftmost c
leftmost = {}
for i, c in enumerate(s):
    if c not in leftmost:
        leftmost[c] = i


# next[i][c] = the position of the next appearance of c
next = [None for i in range(N)]
next[N - 1] = {c: N + leftmost[c] for c in alphabet}
for i in range(N - 2, -1, -1):
    next[i] = {c: i + 1 if s[i + 1] == c else next[i + 1][c]
                  for c in alphabet}

pos = leftmost[t[0]]
for c in t[1:]:
    pos = pos - (pos % N) + next[pos % N][c]

print(pos + 1)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
before = -1
len_s = len(s)
ans = 0
cnt = 0
moji = [[] for _ in range(26)]
for i,S in enumerate(s):
        moji[ord(S) - 97].append(i)

for T in t:
        if not moji[ord(T) - 97]:
                print(-1)
                exit()
        if moji[ord(T) - 97][-1] <= before:
                cnt += 1
                before = moji[ord(T) - 97][0]
                continue
        before = moji[ord(T) - 97][bisect.bisect_right(moji[ord(T) - 97],before)]
        # for num in moji[ord(T) - 97]:
        #         if num > before:
        #                 before = num
        #                 break
ans = cnt * len_s + before + 1
print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
if not set(t) <= set(s):
  print(-1)
else:
  a = 0
  seq = s
  for k in t: 
    p = seq.find(k) + 1
    if p == 0:
      p = s.find(k) + 1
      a += len(seq)
      seq = s
    a += p
    seq = seq[p:]
  print(a)

Submission status: Accepted

Solution code:
# E - Strings of Impurity  maspyさん
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from bisect import bisect_left

S = input().rstrip()
T = input().rstrip()

LS = len(S)

index = defaultdict(list)

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

x = -1 #今みたところ　次はx+1から
for t in T:
    arr = index[t]
    if len(arr) == 0:
        print(-1)
        exit()
    y = (x+1)%LS
    i = bisect_left(arr,y)
    if i < len(arr):
        next_x = (x+1) + arr[i] - y
    else:
        next_x = (x+1) + arr[0] + LS - y
    x = next_x

ans = x + 1
print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
moji = list(set(s))
if all([k in moji for k in set(t)]) is not True:
  print(-1)
else:
  a = 0
  l = len(s)
  seq = s
  for k in t: 
    p = seq.find(k) + 1
    if p == 0:
      p = s.find(k) + 1
      a += p + len(seq)
      seq = s
    else:
      a += p
    seq = seq[p:]
  print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_right

s = input()
t = input()

char_list = [[] for i in range(26)]

for i in range(2*len(s)):
        if i<len(s):
                char_list[ord(s[i])-97].append(i)
        else:
                char_list[ord(s[i-len(s)])-97].append(i)

INF = 10**27

for i in range(26):
        char_list[i].append(INF)

next_list = [[char_list[j][bisect_right(char_list[j],i)] for j in range(26)] for i in range(len(s))]

flag = False
for i in range(len(s)):
        if t[0]==s[i]:
                flag=True
                x = i
                y = i
                break
if flag:
        flag2 = True
        for i in range(1,len(t)):
                n = next_list[x][ord(t[i])-97]
                y += n - x
                x = n%(len(s))
                if y >= INF:
                        flag2=False
                        break
        if flag2:
                print(y+1)
        else:
                print(-1)
else:
        print(-1)

Submission status: Accepted

Solution code:
import sys
import bisect

# 10倍速いらしい
input = sys.stdin.readline

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

S = input().rstrip()
T = input().rstrip()

sn = len(S)
d = dict()
for i, s in enumerate(S):
    d[s] = d.get(s, [])
    d[s].append(i)

nowidx = -1
loop = 0
for t in T:
    l = d.get(t, [])
    if len(l) == 0:
        print(-1)
        sys.exit()
    j = bisect.bisect_right(l, nowidx)
    if len(l) <= j:
        nowidx = l[0]
        loop += 1
    else:
        nowidx = l[j]

# print(loop, nowidx)
print(loop * sn + nowidx + 1)

Submission status: Accepted

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

def main():

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

    dS = {c:[] for c in string.ascii_lowercase}
    for i, s in enumerate(S):
        dS[s].append(i)
    
    ans = 0
    pos = 0
    ls = len(S)
    for c in T:
        if not dS[c]:
            print(-1)
            return
        if dS[c][-1] < pos:
            pos = 0
            ans += ls
        bi = bisect.bisect_left(dS[c], pos)
        pos = dS[c][bi] + 1

    print(ans + pos)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp = [0] * (LT+1)
dp[0] = -1
valid = True

for i in range(1,LT+1):
    t = T[i-1]
    p = dp[i-1] % LS if i > 1 else -1
    if len(H[t]) == 0:
        valid = False
        break
    q = bisect(H[t], p)
    if q == len(H[t]):
        dp[i] = dp[i-1] + LS - p + H[t][0]
    else:
        dp[i] = dp[i-1] + H[t][q] - p

print(dp[-1] + 1 if valid else -1)

Submission status: Accepted

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

def main():

    S = input().strip()
    T = input().strip()
    if any(S.find(c) < 0 for c in T):
        print(-1)
        return

    dS = {c:[] for c in string.ascii_lowercase}
    for i, s in enumerate(S):
        dS[s].append(i)
    
    ans = 0
    pos = 0
    ls = len(S)
    for c in T:
        if dS[c][-1] < pos:
            pos = 0
            ans += ls
        bi = bisect.bisect_left(dS[c], pos)
        pos = dS[c][bi] + 1

    print(ans + pos)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def lower_bound(a, x, index=False):
    from bisect import bisect_left
    i = bisect_left(a, x)
    if (i != len(a)):
        if (index):
            return i
        else:
            return a[i]
    raise ValueError

import sys
import string
s = input()
t = input()
s2 = s*2
lc = string.ascii_lowercase
cd = {}
for c in lc:
    cd[c] = []
for i in range(len(s2)):
    cd[s2[i]].append(i)
p = 0
ans = 0
for c in t:
    if (len(cd[c]) == 0):
        print('-1')
        sys.exit()
    p = lower_bound(cd[c],p)+1
    if (p >= len(s)):
        p -= len(s)
        ans += len(s)
ans += p
print(ans)

Submission status: Accepted

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

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

    if not all(s.find(c) >= 0 for c in t):
        print(-1)
        exit()
    
    sa = [[] for _ in string.ascii_lowercase]
    ai = ord('a')
    for i,c in enumerate(s):
        sa[ord(c)-ai].append(i+1)
#    print(sa)

    ls = len(s)
    ans = 1 # 条件を満たす整数
    i = 1 # s の何番目の文字から探し始めるか
    for c in t:
        a = sa[ord(c)-ai]
        if len(a) == 0 or i > a[-1]:
            ans += ls-i+1
            i = 1
        bi = bisect.bisect_left(a,i)
        if bi < len(a):
            ans += a[bi]-i+1
            i = a[bi]+1
#        print("c,a,ans,i=", c, a, ans, i)
    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from bisect import bisect_right

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

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = [0 for _ in range(26)]
        loop += 1

    ind = bisect_right(letter, ind_prev)
    ind_prev = letter[ind]

if flag:
    print(loop * len(s) + ind_prev + 1)

Submission status: Accepted

Solution code:
import collections
import bisect

d = collections.defaultdict(list)
s = input()
t = input()
for i,S in enumerate(s,1):
    d[S].append(i)
k=0
ans=0
for ch in t:
    l = d[ch]
    if len(l)==0:
        print(-1)
        exit(0)
    if l[-1]<=ans:
        ans=l[0]
        k+=1
    else:
        ans=l[bisect.bisect_right(l,ans)]

print(len(s)*k+ans)

Submission status: Accepted

Solution code:
import bisect
s = input()*2
lens = len(s)//2
t = input()
appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
cnt = -1
bis = bisect.bisect_right
ans = 0

for i, ch in enumerate(s):
  appear[ch].append(i)
  
for j in t:
  if appear[j]:
    idx = bis(appear[j],cnt)
    ans += appear[j][idx] - cnt
    cnt = appear[j][idx]%lens
  else:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
import sys

#+++++

def sss(cc, l):
	#print(cc,l)
	if len(l)==0:
		return (-1,'no_chr')
	elif cc > l[-1]:
		return (-1,'over')
	
	#にぶたんを書く
	if cc <= l[0]:
		return (l[0],'')
	
	ue=len(l) - 1 #以下
	sita=0#より大きい
	while abs(ue - sita) > 1:
		mid = (ue + sita)//2
		if l[mid] >= cc:
			ue = mid
		else:
			sita = mid
	return (l[ue],'')

def main():
	s = input()
	t = input()
	i = 0
	bbb=[[] for i in range(26)]
	ctoi=lambda c : ord(c)-97
	
	for i, c in enumerate(s):
		bbb[ctoi(c)].append(i+1)
	
	for i, b in enumerate(bbb):
		pass
		#print(chr(i+ord('a')) + ':' + str(b))
	
	cc = 0
	kkk=0
	ret = 0
	for c in t:
		address=ord(c) - ord('a')
		l=bbb[address]
		#print(cc,l,'a')
		#cc以上の値をみつける。
		nc, st = sss(cc, l)
		cc = nc + 1
		#print(cc)
		if st =='no_chr':
			print(-1)
			return 
			
		if st == 'over':
			kkk += 1
			cc = l[0] + 1
			
	#print(len(s), kkk, cc)
	ret = len(s) * kkk + cc - 1
	print(ret)
			
		

	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from bisect import bisect

s = input()
t = input()

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

d = dict()

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

ans = 0
res = d[t[0]][0]

for i in range(1, len(t)):
    index = bisect(d[t[i]], res)
    if index == len(d[t[i]]):
        ans += len(s)
        res = d[t[i]][0]
    else:
        res = d[t[i]][index]

ans += res + 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect

s = input()
t = input()

d = dict()

for i in range(26):
    d[chr(i+97)] = []

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

ans = 0
res = -1

for i in range(len(t)):
    if d[t[i]] == []:
        print(-1)
        exit()
    index = bisect(d[t[i]], res)
    if index == len(d[t[i]]):
        ans += len(s) - res + d[t[i]][0]
        res = d[t[i]][0]
    else:
        ans += d[t[i]][index] - res
        res = d[t[i]][index]

print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

S = input()
T = input()

if any(i not in sorted(list(set(S))) for i in sorted(list(set(T)))):
    print(-1)
    exit()

d = {}
for sidx, s in enumerate(S):
    if s not in d.keys():
        d[s] = []
    d[s].append(sidx+1)

if 'LOCAL' in os.environ:
    print('d', d)
current_idx = -1
round_count = 0
for tidx, t in enumerate(T):
    #  pdb.set_trace()
    if 'LOCAL' in os.environ:
        print('t:  ', t, tidx)

    char_position_idx = bisect.bisect_right(d[t], current_idx)
    if char_position_idx >= len(d[t]):
        # 同じ文字だがこえているので次の順目に
        round_count += 1
        current_idx = d[t][0]
        continue

    #  print('char posi idx', char_position_idx)
    #  print('d[t][char posi idx]', d[t][char_position_idx], current_idx)
    if d[t][char_position_idx] < current_idx:
        # この順目にない場合
        current_idx = d[t][0]
        round_count += 1
    else:
        # この順目にある場合
        current_idx = d[t][char_position_idx]
print(len(S)*round_count + current_idx)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

s = input()
t = input()
#%%
ls = len(s)-1
cnt = 0
num = -1
di = defaultdict(list)
for ind,i in enumerate(s):
    di[i].append(ind)

for i in t:
    if(i not in di):
        print(-1)
        break
    if(di[i][-1]<=num):
        cnt += ls-num+di[i][0]+1
    else:
        x = bisect.bisect_left(di[i],num+1)
        if(num==-1):
            cnt += di[i][x]
        else:
            cnt += di[i][x]-num
    num = cnt%(ls+1)
    #print(i,cnt)

else:
    print(cnt+1)

Submission status: Accepted

Solution code:
import bisect

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

# 辞書を作る
dictionary = {}

tt = t[:]
ss = dict(zip(list(range(len(s * 2))), s * 2))

for i in range(len(ss)):
    c = ss[i]
    if c not in dictionary:
        dictionary[c] = []
    dictionary[c].append(i)

result = 0
current_idx = 0
sLen = len(s)

for c in t:
    if c not in dictionary:
        print(-1)
        exit(0)
    indexes = dictionary[c]
    next = dictionary[c][bisect.bisect_left(indexes, current_idx)] + 1
    result += next - current_idx
    current_idx = next
    if next >= sLen:
        current_idx -= sLen

print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left
 
s = input()
t = input()
s_len = len(s)
t_len = len(t)
if not set(t) <= set(s):
  print(-1)
else: 
  idx = defaultdict(list)
  for i in range(s_len):
    idx[s[i]].append(i)
  
  loop_num = 0
  current_position = -1
  for i in range(t_len):
    char = t[i]
    tmp_idx = idx[char]
    n = bisect_left(tmp_idx, current_position+1)
    if n < len(tmp_idx):
      current_position = tmp_idx[n]
    else:
      current_position = tmp_idx[0]
      loop_num += 1
  print(s_len * loop_num + current_position + 1)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()
T = set(t)
s_num = len(s)
t_num = len(T)

# make a dictonary whose keys are the alphabets in t
dict = {}
appearing_times = {}

# when each alphabet in t appears in s
for w in T:
    dict[w] = []
    appearing_times[w] = 0
    index = -1
    while True:
        index = s.find(w, index + 1)
        if index == -1 and appearing_times[w] == 0:
            print(-1)
            exit()
        elif index == -1:
            break
        else:
            dict[w].append(index)
            appearing_times[w] += 1

# how many times s is repeated
count = 0
# 0 <= length <= s_num - 1
s_index = 0
w_pre = 'none'

for w in t:
    idx = bisect.bisect_left(dict[w], s_index)
    if w == w_pre:
        idx += 1
        if idx == appearing_times[w]:
            count += 1
            idx = 0

    if idx < appearing_times[w]:
        s_index = dict[w][idx]
    else:
        count += 1
        s_index = dict[w][0]
    w_pre = w

print(count * s_num + s_index + 1)

Submission status: Accepted

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right
input = lambda: sys.stdin.readline()[:-1]
from collections import defaultdict
s =input()
lenth=len(s)
ss=s*2
t =input()
place=defaultdict(list)

for k,l in enumerate(s):
	place[l].append(k+1)
	place[l].append(k+1+lenth)
for i in place.values():
	i.sort()
now=0
ans=0

for i in t:
	if not place[i]:
		print(-1)
		exit()
	mt=place[i][bisect_right(place[i],now)]
	if mt>lenth:
		mt-=lenth
		ans+=lenth
	now=mt
print(ans+now)

Submission status: Accepted

Solution code:
s = input()
t = input()
s_ = s[:]
cnt = 0
tlen = len(t)
ans = 0
flag = True

while cnt < tlen:
    
    num = s_.find(t[cnt])
    
    if num != -1:
        ans += (num+1)
        s_ = s_[(num+1):]
        cnt += 1
        flag = False
    else:
        if flag:
            print(-1)
            exit(0)
        ans += len(s_)
        s_ = s[:]
        flag = True
        
print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def num__grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]


s = input()
t = input()
ns = len(s)
nt = len(t)
alpha = "abcdefghijklmnopqrstuvwxyz"
aldi = {}
for i in alpha:
    aldi[i] = []

for i in range(ns):
    aldi[s[i]].append(i + 1)


num = []
if aldi[t[0]] == []:
    print("-1")
    exit()
mae = aldi[t[0]][0]
num.append(mae)
for i in range(1, nt):
    if aldi[t[i]] == []:
        print("-1")
        exit()
    else:
        kk = bisect_right(aldi[t[i]], mae)
        if kk == len(aldi[t[i]]):
            kk = aldi[t[i]][0]
        else:
            kk = aldi[t[i]][kk]
        mae = kk
        num.append(kk)

ans += num[0]
for i in range(1, len(num)):
    if num[i] <= num[i - 1]:
        ans += ns - num[i - 1] + num[i]
    else:
        ans += num[i] - num[i - 1]

if ans > 10 ** 100:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

alpha = [[] for _ in range(26)]
c2i = lambda x: ord(x) - ord('a')

for i, sl in enumerate(s):
    alpha[c2i(sl)].append(i)

pos = -1
count = 0
length = len(s)
for tl in t:
    places = alpha[c2i(tl)]
    if len(places) == 0:
        print(-1)
        break

    index = bisect_left(places, pos+1)
    if index != len(places):
        place = places[index]
        count += place - pos
        pos = place
    else:
        count += (length-pos-1) + places[0] + 1
        pos = places[0]
else:
    print(count)