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 resolve():
    s = input()
    t = input()
    d = {}
    for i, c in enumerate(list(s)):
        d.setdefault(c, [])
        d[c].append(i)
    
    import bisect
    nloops = 0
    prev = -1
    for c in list(t):
        if c not in d:
            print(-1)
            return
        # prevより後ろにあるcのうち、最も近いものの位置
        cidx = bisect.bisect_left(d[c], prev)
        if cidx < len(d[c]) and prev == d[c][cidx]:
            cidx += 1
        nearc = d[c][cidx] if cidx < len(d[c]) else None
        if nearc is None:
            nloops += 1
            nearc = d[c][0]
        prev = nearc
    print(nloops*len(s)+prev+1)



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys

def LS2(): return list(sys.stdin.readline().rstrip())

s = LS2()
t = LS2()

from collections import defaultdict

dict_s = defaultdict(list)

for i in range(len(s)):
    dict_s[s[i]].append(i)

r = 0  # sの文字列を何回用いたか
u = -1  # 最後に用いた文字のindex
for a in t:
    if len(dict_s[a]) == 0:
        print(-1)
        exit()
    else:
        left = -1
        right = len(dict_s[a])
        while left + 1 < right:
            mid = (left + right)//2
            if dict_s[a][mid] > u:
                right = mid
            else:
                left = mid
        if right == len(dict_s[a]):
            r += 1
            u = dict_s[a][0]
        else:
            u = dict_s[a][right]

print(len(s)*r+u+1)

Submission status: Accepted

Solution code:
import sys

def LS2(): return list(sys.stdin.readline().rstrip())

s = LS2()
t = LS2()

from collections import defaultdict

dict_s = defaultdict(list)

for i in range(len(s)):
    dict_s[s[i]].append(i)

d = {}
for a in dict_s.keys():
    d[a] = 0

r = 0
u = -1
for a in t:
    if len(dict_s[a]) == 0:
        print(-1)
        exit()
    else:
        left = -1
        right = len(dict_s[a])
        while left + 1 < right:
            mid = (left + right)//2
            if dict_s[a][mid] > u:
                right = mid
            else:
                left = mid
        if right == len(dict_s[a]):
            r += 1
            u = dict_s[a][0]
        else:
            u = dict_s[a][right]

print(len(s)*r+u+1)

Submission status: Accepted

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

n = len(s)

if set(list(t)) != (set(list(s)) & set(list(t))): ans = -1
else:
    dct = {}

    for i, ss in enumerate(s):
        if ss in dct:
            dct[ss].append(i)
        else: dct[ss] = [i]
    idx = -1
    ans = 0
    for tt in t:
        m = bisect_right(dct[tt], idx)
        if m == len(dct[tt]):
            idx = dct[tt][0]
            ans += n
        else:
            idx = dct[tt][m]
    ans += idx + 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict

s = input()
t = input()
if set(s) & set(t) != set(t):
    print(-1)
    exit()
cnt = defaultdict(list)
for i, c in enumerate(s, 1):
    cnt[c].append(i)
loop = 0
prev = 0
for w in t:
    l = cnt[w]
    idx = bisect.bisect_right(l, prev)
    if idx < len(l):
        prev = l[idx]
    else:
        prev = l[0]
        loop += 1
ans = loop*len(s) + prev
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right
s,t=input(),input()
m=len(s)

dictionary=defaultdict(list)
for i,j in enumerate(s):
    dictionary[j] +=[i+1]

index,ans=0,0
for i in t:
    try:
        point=bisect_right(dictionary[i],index)
        if point==len(dictionary[i]):num=dictionary[i][0]
        else:num=dictionary[i][point]

        if index>=num:
            ans +=m
        index=num
    except:print(-1);exit()

print(ans+index)

Submission status: Accepted

Solution code:
from bisect import bisect_left

s = list(input())

t = list(input())

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

for i in range(len(s)):
    alf[ord(s[i])-97].append(i)

now_alf = -1
sets = 0
i = 0

while i < len(t):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    if now_alf > alf[next_alf][-1]:
        now_alf = -1
        sets += 1
    else:
        serch_next_alf = bisect_left(alf[next_alf], now_alf)
        now_alf = alf[next_alf][serch_next_alf]+1
        i += 1

print(sets*len(s)+now_alf)

Submission status: Accepted

Solution code:
from bisect import bisect_left

s = list(input())

total_s = len(s)

t = list(input())

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

for i in range(len(s)):
    alf[ord(s[i])-97].append(i+1)

coti_alt = 0
now_alf = 0
ans = 0

for i in range(len(t)):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    if 0 < i and t[i-1] == t[i]:
        now_alf += 1
        ans += 1
        if now_alf == total_s and t[i] == s[now_alf-1]:
            continue

    serch_next_alf = bisect_left(alf[next_alf], now_alf)

    if now_alf < alf[next_alf][-1]:
        ans += alf[next_alf][serch_next_alf] - now_alf
        now_alf = alf[next_alf][serch_next_alf]
    else:
        ans += total_s - now_alf + alf[next_alf][0]
        now_alf = alf[next_alf][0]
    #print(ans,now_alf)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

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

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

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>=num:
        ans +=m
    index=num

print(ans+index)

Submission status: Accepted

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

from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

# Sの中での位置
iS = defaultdict(list)
for (idx, ch) in enumerate(S):
    iS[ch].append(idx)

# Tの文字はSに出ていないといけない
for v in T:
    if v not in iS:
        print(-1)
        exit()

# 探索
cnt = 0
cur = -1
for v in T:
    i = bisect_right(iS[v], cur)
    if i == len(iS[v]):
        j = iS[v][0]
    else:
        j = iS[v][i]

    if cur >= j:
        cnt += 1
    cur = j

print(cnt * len(S) + cur + 1)

Submission status: Accepted

Solution code:
s=input()
t=input()
ds={}
for i in range(len(s)):
  if s[i] in ds:
    ds[s[i]].append(i+1)
  else:
    ds[s[i]]=[i+1]
n=len(s)
now=0 # mod n
ans=0
from bisect import bisect_right
for ti in t:
  if ti not in ds:
    print(-1)
    exit()
  tmp=bisect_right(ds[ti],now)
  if tmp==len(ds[ti]):
    get=n+ds[ti][0]
  else:
    get=ds[ti][tmp]
  ans+=get-now
  #print(now,get)
  now=(get)%n
print(ans)
#print(ds)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()

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

cnt = 0
cur = -1
mod = len(s)
flag = False
for v in t:
    if v not in indices:
        flag = True
        break

    i = bisect_right(indices[v], cur)
    if i == len(indices[v]):
        j = indices[v][0]
    else:
        j = indices[v][i]

    if cur >= j:
        cnt += 1
    cur = j

if flag:
    print(-1)
else:
    print(cnt * mod + cur + 1)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

S,T = S(),S()
N = len(S)
dic = DD(list)
for i in range(N):
  dic[S[i]].append(i+1)

now = 0
for t in T:
  if not dic[t]:
    print(-1)
    exit()
  if now%N < dic[t][-1]:
    now += dic[t][bisect.bisect(dic[t],now%N)]-now%N
  else:
    now = -(-now//N)*N + dic[t][0]

print(now)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

s = input()
t = input()

alp = 'abcdefghijklmnopqrstuvwxyz'
alp_pos = {}
for a in alp:
    alp_pos[a] = []

for i,v in enumerate(s):
    alp_pos[v].append(i+1)


loop = 0
curr_pos = 0
for ti in t:
    if not alp_pos[ti]:
        print(-1)
        exit()
    curr_alp_poss = alp_pos[ti]
    ind = bisect_right(curr_alp_poss, curr_pos)
    if ind >= len(curr_alp_poss):
        loop += 1
        curr_pos = curr_alp_poss[0]
    else:
        curr_pos = curr_alp_poss[ind]

print(loop*len(s)+curr_pos)

Submission status: Accepted

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)

    def check(S, T):
        b = {s for s in S}
        for t in T:
            if t not in b:
                return True  # -1
        return False

    def is_ok(mid, now, ans):
        if ans < now[mid]:
            return True
        else:
            return False

    def binary_search_meguru(now, ans):
        ng = -1
        ok = len(now)-1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid, now, ans):
                ok = mid
            else:
                ng = mid
        return now[ok]

    if check(S, T):
        return print(-1)

    from string import ascii_lowercase

    dic = {a: [] for a in ascii_lowercase}
    for i, s in enumerate(S):
        dic[s].append(i+1)
    ans = 0
    cycle = 0
    for t in T:
        now = dic[t]
        if now[-1] <= ans:
            cycle += 1
            ans = 0
        idx = binary_search_meguru(now, ans)
        ans = idx
    print(ans + N*cycle)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    S = input().strip()
    T = input().strip()

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

    for i, s in enumerate(S):
        D[s].append(i)
    
    res = 0
    p = 0
    for t in T:
        if D[t] == []:
            print(-1)
            return
        
        j = bisect.bisect_left(D[t], p)
        if j == len(D[t]):
            p = D[t][0] + 1
            res += 1
        else:
            p = D[t][j] + 1
        
    print(res * len(S) + p)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    S = input()
    N = len(S)
    INF = N + 1
    T = input()
    # S で i 番目の何番目の後で文字 c が出てくるかを計算
    next_loc = [[INF for _ in range(N)] for _ in range(26)]
    for i, s in enumerate(S):
        c = ord(s) - ord('a')
        next_loc[c][i - 1] = 1
    for c in range(26):
        n = INF
        for i in range(N - 1, -(N + 1), -1):
            n = min(next_loc[c][i], n + 1)
            next_loc[c][i] = n
    # 答えを計算
    ans = 0
    index = -1
    for t in T:
        c = ord(t) - ord('a')
        i = next_loc[c][index]
        if i == INF:
            print(-1)
            return
        ans += i
        index = (index + i) % N
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
l_s = len(s)
l_t = len(t)

s2 = s + s
l_s2 = len(s2)

next_idx = [[l_s2] * 26 for i in range(l_s2)]

for i in reversed(range(1, l_s2)):
    for j in range(26):
        next_idx[i-1][j] = next_idx[i][j]
    next_idx[i-1][ord(s2[i]) - ord("a")] = i

cur_idx = 0
for i in range(l_t):
    if i == 0:
        flg = False
        for j in range(l_s):
            if t[i] == s[j]:
                cur_idx += j
                flg = True
                break
        if flg:
            continue
        else:
            print("-1")
            exit()

    else:
        idx = next_idx[cur_idx%l_s][ord(t[i]) - ord("a")]

    if idx == l_s2:
        print("-1")
        exit()

    cur_idx += idx - (cur_idx % l_s)
    
print(cur_idx+1)

Submission status: Accepted

Solution code:
s=list(input())
t=list(input())
ns=len(s)
nt=len(t)
t_set=list(set(t))
s_set=list(set(s))
for i in range(len(t_set)):
    if t_set[i] not in s_set:
        print(-1)
        exit()

from collections import defaultdict, deque
from bisect import bisect_right
ds=defaultdict(list)
for i in range(ns):
    ds[s[i]].append(i)

components=[0]*26
for i in range(26):
    components[i]=len(ds[chr(i+97)])
lt=[-1]*nt
ord('a')
last=-1
for i in range(nt):
    j=bisect_right(ds[t[i]],last)
    if j==components[ord(t[i])-97]:
        lt[i]=ds[t[i]][0]
    else:
        lt[i]=ds[t[i]][j]
    last=lt[i]

kuriage=0
for i in range(1,nt):
    if lt[i]<=lt[i-1]:
        kuriage+=1

print(kuriage*ns+lt[-1]+1)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    T = readline().strip()
    N = len(S)
    M = len(T)

    SS = S + S

    A = [False] * 26
    for c in S:
        A[ord(c) - 97] = True

    for c in T:
        if not A[ord(c) - 97]:
            print(-1)
            return

    B = [[] for _ in range(26)]
    for i, c in enumerate(SS):
        B[ord(c) - 97].append(i)

    i = B[ord(T[0]) - 97][0]
    ans = i + 1
    for c in T[1:]:
        j = B[ord(c) - 97][bisect_right(B[ord(c) - 97], i)]
        ans += j - i
        if j < N:
            i = j
        else:
            i = j - N

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import bisect
import sys
s = input()
t = input()
sb = Counter(s)
tb = Counter(t)
S = len(s)
T = len(t)

for i in range(26):
    x = chr(i+97)
    
    if sb[x] == 0 and tb[x] >= 1:
        print(-1)
        sys.exit()
        
le = [[] for i in range(26)]
for i in range(S):
    le[ord(s[i]) - 97].append(i+1)
        
loop = 0
hasu = 0

for i in range(T):
    x = ord(t[i]) - 97
    c = bisect.bisect(le[x],hasu)
    if c == len(le[x]):
        loop += 1
        hasu = le[x][0]
    else:
        hasu = le[x][c]
        
print(loop*S + hasu)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    T = readline().strip()
    N = len(S)
    M = len(T)

    SS = S + S

    A = [False] * 26
    for c in S:
        A[ord(c) - 97] = True

    for c in T:
        if not A[ord(c) - 97]:
            print(-1)
            return

    B = [[-1] * N for _ in range(26)]
    for c in set(T):
        code = ord(c) - 97
        row = B[code]

        left = right = 0
        while True:
            right = SS.find(c, left + 1)
            if right < N:
                row[left:right] = [right] * (right - left)
                left = right
            else:
                row[left:N] = [right] * (N - left)
                break

    ans = i = S.find(T[0])
    for c in T[1:]:
        j = B[ord(c) - 97][i]
        ans += j - i
        if j < N:
            i = j
        else:
            i = j - N

    print(ans + 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

s = rs()
t = rs()


import collections
pos = collections.defaultdict(list)
for i, c in enumerate(s):
	pos[c].append(i)

import bisect

def search(arr, x):
	l, r = 0, len(arr)
	while r-l >= 1:
		mid = (r+l)//2
		if x < arr[mid]:
			r = mid
		else:
			l = mid+1
	return l

num = 0
cur = -1

for c in t:
	if c not in pos:
		print(-1)
		exit()
	#i = bisect.bisect_right(pos[c], cur)
	i = search(pos[c], cur)
	if i == len(pos[c]):
		i = 0
		num += 1
	cur = pos[c][i]
print(num*len(s)+cur+1)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

s = rs()
t = rs()


import collections
pos = collections.defaultdict(list)
for i, c in enumerate(s):
	pos[c].append(i)

import bisect

num = 0
cur = -1

for c in t:
	if c not in pos:
		print(-1)
		exit()
	i = bisect.bisect_right(pos[c], cur)
	if i == len(pos[c]):
		i = 0
		num += 1
	cur = pos[c][i]
print(num*len(s)+cur+1)

Submission status: Accepted

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


def solve(s: str, t: str):
    """
    >>> solve("aaa", "aaa")
    3
    >>> solve("a", "a")
    1
    >>> solve("contest", "son")
    10
    """
    from collections import defaultdict
    from bisect import bisect
    d = defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)
    ans, i = 0, -1
    for c in t:
        #print(ans, i, end=" ")
        if not d[c]:
            return -1
        j = bisect(d[c], i)
        if len(d[c]) == j:
            ans += len(s) - i + d[c][0]
            i = d[c][0]
        else:
            ans += d[c][j] - i
            i = d[c][j]
        #print("->", ans, i)
    return ans

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    print(solve(s, t))

     
def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Submission status: Accepted

Solution code:
import bisect

en2asc = lambda s: ord(s) - 97

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

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

L = len(S)
cur = 0
for t in T:
    t = en2asc(t)
    b = bisect.bisect_left(lst[t], cur % L)
    if b == len(lst[t]):
        cur = (cur // L + 1) * L
        b = bisect.bisect_left(lst[t], cur % L)
    cur = cur // L * L + lst[t][b] + 1
print(cur)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import bisect
from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    s=input()

    ss=s*2
    d={}
    for k,v in enumerate(ss):
        if v in d:
            d[v].append(k)
        else: d[v]=[k]
    

    

    ls=len(s)
    t=input()
    cur=-1 #見終えた場所
    flag=False
    for i in t:
        if i in d:
            idx=d[i][bisect.bisect_left(d[i],(cur+1)%ls)]
            dif=idx-(cur+1)%ls+1
            cur+=dif
        else:
            flag=True
            break
    print(cur+1 if not flag else -1)




    
resolve()

Submission status: Accepted

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

if len(set(t)-set(s)) > 0:
  print(-1)
  exit()

c = set(s)
dic = {}
for char in c:
  dic[char] = []

for i in range(len(s)):
  dic[s[i]] += [i]

last = -1
r = 0
for char in t:
  tmp = last
  idx = bisect.bisect_right(dic[char], last)
  if idx < len(dic[char]):
    last = dic[char][idx]

  if tmp == last:
    r += 1
    last = dic[char][0]

print(len(s)*r + last + 1)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
s = input()
n = len(s)
t = input()
if set(s) & set(t) != set(t):
    print(-1)
else:
    cnt = defaultdict(list)
    for i in range(n):
        cnt[s[i]].append(i+1)
    loop = 0
    prev = 0
    for c in t:
        x = cnt[c]
        idx = bisect.bisect_right(x, prev)
        if idx < len(x):
            prev = x[idx]
        else:
            prev = x[0]
            loop += 1
    print(loop*n+prev)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect
s = list(input())
sn = len(s)
t = list(input())
tn = len(t)
kouho = []
for i in range(26):
    kar = []
    now = chr(ord('a') + i)
    for j in range(sn):
        if s[j] == now:
            kar.append(j)
    kouho.append(kar)

cou = 0
now = -1
for i in range(tn):
    u = ord(t[i])-ord("a")
    if kouho[u]:
        tugi = bisect(kouho[u],now)
        if tugi == len(kouho[u]):
            cou += 1
            now = kouho[u][0]
        else:
            now = kouho[u][tugi]
    else:
        print(-1)
        exit()

print(cou*sn + now + 1)

Submission status: Accepted

Solution code:
from collections import Counter
import bisect


S = input()
S = S + S
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

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

N = len(S) // 2
ans = 0
now = -1

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    now = At[x]
    if now + 1 >= N:
        ans += 1
    now += 1
    now %= N

print(ans * N + now)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

def rand_letter(size):
    ascii_original='programing'
    digits_original='01'

    digits='0123456789'
    ascii_lowercase='abcdefghijklmnopqrstuvwxyz'
    ascii_uppercase='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    # 好きなものを使ってね
    psuedo = ascii_original

    return ''.join([random.choice(psuedo) for i in range(size)])


S = input()
N_S = len(S)
T = input()
N_T = len(T)

dict_s = defaultdict(int)
dict_order = defaultdict(list)
for i in range(N_S):
    dict_s[S[i]] += 1
    dict_order[S[i]].append(i + 1)

dict_t = defaultdict(int)
for i in range(N_T):
    dict_t[T[i]] += 1

flag = True
for i in dict_t:
    if dict_s[i] == 0:
        flag = False
        break

if not flag:
    print(-1)
    exit()

now = dict_order[T[0]][0]
ans = [dict_order[T[0]][0]]

for i in range(1, N_T):
    index = bisect_right(dict_order[T[i]], now)
    if index == len(dict_order[T[i]]):
        now = dict_order[T[i]][0]
    else:
        now = dict_order[T[i]][index]
    ans.append(now)

cnt = 0
for i in range(1, N_T):
    if ans[i] <= ans[i - 1]:
        cnt += 1
print(cnt * N_S + ans[-1])

Submission status: Accepted

Solution code:
def f():
    import sys
    input=sys.stdin.buffer.readline
    sys.setrecursionlimit(10**9)
    from collections import defaultdict
    table=defaultdict(list)
    
    s,t=input().rstrip(),input().rstrip()
    n=len(s)
    for j in range(n):
        table[s[j]-97].append(j)
    now=0
    ind=0
    if set(t)-set(s):print(-1);exit()
    from bisect import bisect_left as bl
    for p in t:
        if ind>table[p-97][-1]:now+=1;ind=0
        ind=table[p-97][bl(table[p-97],ind)]+1

    print(now*n+ind)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
def f():
    s,t=input(),input()
    n,m=len(s),len(t)
    table=[[]for i in  range(26)]
    d={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

    for j in range(n):
        table[d[s[j]]].append(j)
    now=0
    ind=0
    if set(list(t))-set(list(s)):print(-1);exit()
    from bisect import bisect_left as bl
    for p in t:
        if ind>table[d[p]][-1]:now+=1;ind=0
        ind=table[d[p]][bl(table[d[p]],ind)]+1

    print(now*n+ind)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    S = SI()
    T = SI()
    if set(S) | set(T) != set(S):
        print(-1)
        exit()
    s2i = {}

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

    now = 0
    digit = -1
    for t in T:
        target = bisect.bisect_right(s2i[t], digit)
        if target == len(s2i[t]):
            digit = s2i[t][0]
            now += 1
        else:
            digit = s2i[t][target]

    print(now * len(S) + digit + 1)


if __name__ == "__main__":
    main()