Problem:


Score : 500 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.

Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').

Notes

A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

Constraints

1 \leq |s| \leq 10^5

1 \leq |t| \leq 10^5

s and t consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If there exists an integer i satisfying the following condition, print the minimum such i; otherwise, print -1.

Sample Input 1

contest
son

Sample Output 1

10

t = son is a subsequence of the string contestcon (the first 10 characters in s' = contestcontestcontest...), so i = 10 satisfies the condition.

On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s'), so i = 9 does not satisfy the condition.

Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10.

Sample Input 2

contest
programming

Sample Output 2

-1

t = programming is not a substring of s' = contestcontestcontest.... Thus, there is no integer i satisfying the condition.

Sample Input 3

contest
sentence

Sample Output 3

33

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.



Sample input:
contest
son


Sample output:
10

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
#def MXI(): return [LI() for i in range(n)]　
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
s=SI()
t=SI()
a=len(s)
b=len(t)
#アルファベットから数字へと変換する辞書
alphasm=[chr(i) for i in range(97, 97+26)]
alphadic={}
for i in range(26):
    alphadic[alphasm[i]]=i
strlis=[[] for i in range(26)]
#print(alphadic)
#print(strlis)
for i in range(a):
    strlis[alphadic[s[i]]].append(i)
#print(strlis)
rd=0
pos=-1
#print(strlis[a])
i=0
while i<b:
    if len(strlis[alphadic[t[i]]])==0:
        print(-1)
        sys.exit()
        #print("a")
    if pos==-1:
        pos=strlis[alphadic[t[i]]][0]
        i+=1
        #print("b")
    elif strlis[alphadic[t[i]]][-1]<=pos:
        rd+=1
        pos=-1
        #print("c")
    else:
        pos=strlis[alphadic[t[i]]][bisect_right(strlis[alphadic[t[i]]],pos)]
        i+=1
        #print("d")
    #print(rd,pos)
print(rd*a+pos+1)


    
        
#現在の周回数、何個目かの情報を持っておく
#次の周回に行くかどうかの判定 行かないなら二分探索

Submission status: Accepted

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

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

m = len(s)
i = 0
last_idx = -1
counter = dict()
for c in t:
    if not c in char_dic:
        print(-1)
        quit()
    j = bisect_right(char_dic[c], last_idx)
    if j == len(char_dic[c]):
        i += 1
        last_idx = char_dic[c][0]
    else:
        last_idx = char_dic[c][j]
print(i * len(s) + last_idx + 1)

Submission status: Accepted

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

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

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


s0 = -1
cnt = 0
for t in T:
    if not dic[t]:
        print(-1)
        exit()
    p = bisect_right(dic[t],s0)
    if p >= len(dic[t]):
        cnt += 1
        s0 = min(dic[t])
    else:
        s0 = dic[t][p]

print(L*cnt+s0 +1)

Submission status: Accepted

Solution code:
def find(base, indexes):
    n = len(indexes)
    ng = -1
    ok = n

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if indexes[mid] > base:
            ok = mid
        else:
            ng = mid

    return indexes[0] if ok == n else indexes[ok]


s = input()
t = input()

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

if t_set.issubset(s_set) is False:
    print(-1)
    exit(0)

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

for i in range(len(s)):
    c = s[i]
    idx = ord(c) - ord("a")
    s_indxes[idx].append(i)

base = -1
loop = 0
for i in range(len(t)):
    c = t[i]
    idx = ord(c) - ord("a")
    n_base = find(base, s_indxes[idx])

    if n_base <= base:
        loop += 1

    base = n_base

print(loop * len(s) + base + 1)

Submission status: Accepted

Solution code:

from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

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

i = -1
cnt = 0
flag = False
for t in T:
    if t not in ctr:
        flag = True
        break

    j = bisect_right(ctr[t], i)
    if j == len(ctr[t]):
        idx = ctr[t][0]
    else:
        idx = ctr[t][j]

    if i >= idx:
        cnt += 1
    i = idx

if flag:
    print(-1)
else:
    print(cnt * len(S) + i + 1)

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    s = input()
    ls = len(s)
    t = input()
    if t[0] in s:
        idx = s.find(t[0])
    else:
        print(-1)
        exit()
    for i in t[1::]:
        nt = s.find(i,idx%ls+1)
        ntl = s.find(i)
        if ntl == -1:
            print(-1)
            exit()
        elif nt == -1:
            idx = (idx//ls)*ls+ls+ntl
        else:
            idx = (idx//ls)*ls+nt
    print(idx+1)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
Tの文字にたいして、Sのインデックスをリストで持たせる
Tの頭から順繰りにたし上げていく（Loop数を数えること）
自分よりも大きい要素があれば、それを使うし、
なければ最も小さい要素を使いつつ、Loop数をCountUp
bisect_left()かな？

0123456
contest

01234567
sentence

s=[5]   -> 5  (6moji)
e=[4]   -> 7*1+4 (12moji)
n=[2]   -> 7*2+2 = 16
t=[3,6] -> 7*2+3 = 17
e=[4]   -> 7*2+4 = 18
n=[2]   -> 7*3+2 = 23
c=[0]   -> 7*4+0 = 28
e=[4]   -> 7*4+4 = 32 ( 33moji)
"""

from bisect import bisect_right, bisect_left
S = input()
T = input()

def calc(ch):
  return ord(ch) - ord('a')

## Tに含まれる文字に対し、Sのインデックスをふる
LST = [[] for _ in range(26)]
for t in T:
  nt = calc(t)
  if len(LST[nt]) > 0:
    continue
  for i in range(len(S)):
    if t == S[i]:
      LST[nt].append(i)
  if len(LST[nt]) == 0:
    print(-1)
    exit(0)
    
NS = len(S)
## Tの文字に対して順繰りにたしあげる
NofLoop = 0
now = 0
for i in range(len(T)):
  t = T[i]
  nt = calc(t)
  rel_now = now - NofLoop * NS
  if rel_now < LST[nt][0] :
    #print("R",t,nt,rel_now)
    now = NofLoop * NS + LST[nt][0] + 1
  elif LST[nt][-1] < rel_now :
    #print(t,i)
    NofLoop += 1
    now = NofLoop * NS + LST[nt][0] + 1
  else:
    idx = bisect_left(LST[nt], rel_now)
    #print(idx)
    now = NofLoop * NS + LST[nt][idx] + 1
    
print(now)

Submission status: Accepted

Solution code:
def main():
    import sys
    import copy
    from bisect import bisect_right
    from collections import defaultdict
    input = sys.stdin.readline
    s, t = input().strip(), input().strip()
    lens = len(s)
    index_list = defaultdict(list)
    leng = defaultdict(int)
    for i, ss in enumerate(s):
        index_list[ss].append(i)

    for s, i in index_list.items():
        if i:
            leng[s] = len(index_list[s])

    prev = -1
    ans = 0
    for tt in t:
        if tt not in leng:
            print(-1)
            return False
        p = bisect_right(index_list[tt], prev)
        # print('tt={}, prev={}, p={}, ans={}'.format(tt, prev, p, ans))
        if p < leng[tt]:
            prev = index_list[tt][p]
        else:
            prev = index_list[tt][0]
            ans += lens

    print(ans+prev+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
S = input()
T = input()
D = dict()
for i in range(len(T)):
    if T[i] in D:
        continue
    else:
        D[T[i]] = []
for i in range(len(S)):
    if S[i] in D:
        D[S[i]].append(i)

if len(set(T)-set(S))>0:
    print(-1)
else:
    r = -1
    cnt = 0
    for i in range(len(T)):
        m = bisect.bisect_right(D[T[i]], r)
        if m < len(D[T[i]]):
            r = D[T[i]][m]
        else:
            r = D[T[i]][0]
            cnt += 1
    print(len(S)*cnt+r+1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

s = input()
t = input()

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

dic = defaultdict(list)
for i, char in enumerate(s, 1):
	dic[char].append(i)

loop = 0
index = -1
for i in range(len(t)):
	idx = bisect(dic[t[i]], index)
	if idx < len(dic[t[i]]):
		index = dic[t[i]][idx]
	else:
		idx = dic[t[i]][0]
		index = idx
		loop += 1

print(len(s)*loop+index)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

s = input()
t = input()

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

for i, char in enumerate(s, 1):
	if char in t_kinds:
		dic[char].append(i)

if len(dic.keys()) < len(t_kinds):
	print(-1)
	exit()

dic_lim = defaultdict(int)
for key in dic.keys():
	dic_lim[key] = len(dic[key])

tmp = -1
ans = 0
loop_cnt = 0
for x in t:
	idx = bisect(dic[x], tmp)
	if idx == dic_lim[x]:
		tmp = dic[x][0]
		loop_cnt += 1
	else:
		tmp = dic[x][idx]
print(len(s)*loop_cnt + tmp)

Submission status: Accepted

Solution code:
INF = 1000000007
s = list(input())
t = list(input())
lis = [[0] for i in range(26)]
for i in range(len(s)):
    lis[ord(s[i])-ord('a')].append(i+1)

for i in range(26):
    lis[i].append(INF)
#print(lis)

def binary_search(val,lis):
    ng = 0
    ok = len(lis)-1
    while abs(ng-ok) > 1:
        mid = (ok+ng)//2
        if lis[mid] > val:
            ok = mid
        else:
            ng = mid
        #print(ok,ng)
    return lis[ok]
# print(binary_search(5,[3,4,5,6,7,8]))

ans = 0
p = 0
for i in t:
    j = ord(i) - ord('a')
    if len(lis[j]) == 2:
        print(-1)
        exit()
    val = binary_search(p,lis[j])
    p = val
    if val == INF:
        ans += len(s)
        p = binary_search(0,lis[j])
    #print(p)
print(ans + p)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    t = collections.deque(list(input()))

    jump = [[0] * 26 for _ in range(len(s) + 1)]

    for i in range(len(s) - 1, -1, -1):
        jump[i] = jump[i + 1].copy()
        jump[i][ord(s[i]) - 97] = i + 1

    ans = 0
    point = 0
    while len(t) > 0:
        tmp = t.popleft()
        character = ord(tmp) - 97
        if jump[point][character] == 0 and point == 0:
            print(-1)
            exit(0)
        point = jump[point][character]
        if point == 0:
            t.appendleft(tmp)
            ans += 1

    print(ans * len(s) + point)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
s=input()
t=input()
dic={}
for i in range(len(t)):
  if t[i] in dic:
    continue
  if t[i] not in dic:
    dic[t[i]]=[]
for i in range(len(s)):
  if s[i] in dic:
    dic[s[i]].append(i)
for k,v in dic.items():
  if v==[]:
    print(-1)
    exit()
n=-1
k=0

for i in range(len(t)):
  l=bisect.bisect_right(dic[t[i]],n)
  if l<len(dic[t[i]]):
    n=dic[t[i]][l]
  else:
    n=dic[t[i]][0]
    k+=1
print(len(s)*k+n+1)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from string import ascii_lowercase

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

dict_s = {c: [] for c in ascii_lowercase}
for i, c in enumerate(s * 2):
    dict_s[c].append(i)

for c in ascii_lowercase:
    if not dict_s[c]:
        del dict_s[c]


dict_next_i = {
    c: [dict_s[c][bisect_left(dict_s[c], i + 1)] for i in range(n)]
    for c in dict_s.keys()
}


def next_i(i, c):
    return n * (i // n) + dict_next_i[c][i % n]


def answer():
    if not all(c in s for c in t):
        return -1
    i = -1
    for c in t:
        i = next_i(i, c)
    return i + 1  # 1-origin


print(answer())

Submission status: Accepted

Solution code:
import sys
from string import ascii_lowercase as a2z

input = sys.stdin.readline


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

    N = len(S)
    memo = [None] * N
    memo[-1] = {alphabet: -1 for alphabet in a2z}
    memo[-1][S[-1]] = N - 1
    for i in reversed(range(N - 1)):
        memo[i] = memo[i + 1].copy()
        memo[i][S[i]] = i

    ans = 0
    idx_S = 0
    for t in T:
        i = memo[idx_S][t]
        if i == -1:
            ans += (N - idx_S)
            idx_S = 0
            i = memo[idx_S][t]
            if i == -1:
                ans = -1
                break
            else:
                ans += i - idx_S + 1
                if i == N - 1:
                    idx_S = 0
                else:
                    idx_S = i + 1
        else:
            ans += i - idx_S + 1
            if i == N - 1:
                idx_S = 0
            else:
                idx_S = i + 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

S = input()
T = input()

ss = set(list(S))
st = set(list(T))
if not (st <= ss):
    print(-1)
    exit()
alpha = {chr(97+i): [] for i in range(26)}
for i, s in enumerate(S):
    alpha[s].append(i+1)
n = len(S)
now = 0
ans = 0
for t in T:
    if alpha[t][-1] <= now:
        ans += (n - now) + alpha[t][0]
        now = alpha[t][0]
    else:
        i = bisect_left(alpha[t], now+1)
        ans += alpha[t][i] - now
        now = alpha[t][i]
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
from bisect import bisect_left, bisect_right

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

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

    chars = {ch: [] for ch in alphabets}

    for i, ch in enumerate(s):
        chars[ch].append(i)

    ans = 0
    last = -1
    for ch in t:
        if len(chars[ch]) == 0:
            print(-1)
            return

        idx = bisect_right(chars[ch], last)
        idx = idx if idx < len(chars[ch]) else 0
        if chars[ch][idx] > last:
            ans += chars[ch][idx] - last
        else:
            ans += len(s) - last + chars[ch][idx]
        last = chars[ch][idx]

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
ns = len(list(s))
t = input()
nt = len(list(t))

jisho = defaultdict(list)


# sの何文字目かどうかのidxを集める
for i in range(ns):
    jisho[s[i]].append(i)

# jishoにない→構成不可能
# 二分探索して今のidxより大きい値を取る。
# 今の値が一番大きいときは0からやり直す。
# 出力するのは先頭から何文字目か
now = -1  # bisect用の現在地
cnt = 0  # 何周したか
for i in range(nt):
    lis = jisho[t[i]]
    if not lis:
        print(-1)
        exit()
    pos = bisect_right(lis, now)
    # print(t[i], now, pos)
    # ここで復習、bisect_right はnow以下のものの個数。
    if pos == len(lis):
        now = -1
        cnt += 1
        pos = bisect_right(lis, now)
    now = lis[pos]
print(cnt * ns + now + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
from collections import Counter, defaultdict
from bisect import bisect_left


def read():
    S = input().strip()
    T = input().strip()
    return S, T


def have_ahswer(S, T):
    cs = Counter(S)
    ct = Counter(T)
    for k in ct.keys():
        if cs[k] == 0:
            return False
    return True


def solve(S, T):
    Z = "abcdefghijklmnopqrstuvwxyz"
    if not have_ahswer(S, T):
        return -1
    D = defaultdict(list)
    for i, s in enumerate(S):
        D[s].append(i)
    ans = 0
    prev_index = -1
    N = len(S)
    for t in T:
        a = D[t]
        i = bisect_left(a, prev_index + 1)
        if i < len(a):
            next_index = a[i]
            ans += next_index - prev_index
        else:
            next_index = a[0]
            ans += N + next_index - prev_index
        prev_index = next_index
    return ans


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
from collections import Counter
import bisect

S = input()
T = input()

ls = len(S)
lt = len(T)

cons = Counter(S)
cont = Counter(T)
dics = {}
dicc = {}

for i in range(ls):
  if S[i] not in dics:
    dics[S[i]] = [i+1]
    dicc[S[i]] = 1
  else:
    dics[S[i]].append(i+1)
    dicc[S[i]] += 1
idx = 0
cic = 0
for t in T:
  if t not in dics:
    print(-1)
    exit()
  i = bisect.bisect_left(dics[t], idx)
  if i == dicc[t]:
    idx = dics[t][0] + 1
    cic += 1
  else:
    idx = dics[t][i] + 1
    
print(cic*ls+idx-1)

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 #
#############

s = input()
t = input()

# 各文字について
p = {c: [] for c in s}
for i in range(len(s)):
    p[s[i]].append(i)

z = 0
l = -1
for c in t:
    if c not in p:
        print(-1)
        break
    # 文字cのうちもっとも近い未来にあるもの
    x = bisect_right(p[c], l)
    # 一周するなら
    if x == len(p[c]):
        x = 0
        z += 1
    l = p[c][x]
else:
    print(z * len(s) + l + 1)

Submission status: Accepted

Solution code:
import bisect
ind = {}
s = input()
t = input()
for i, c in enumerate(s):
    if c in ind:
        ind[c].append(i+1)
    else:
        ind[c] = [i+1]
k = len(s)
nk = 0
if not t[0] in ind:
    print(-1)
    exit()
nw = ind[t[0]][0]
pv = nw
for i in range(1, len(t)):
    c = t[i]
    if not c in ind:
        print(-1)
        exit()
    if ind[c][-1]>pv:
        pv = ind[c][bisect.bisect_left(ind[c], pv+1)]
    else:
        nk += k
        pv = ind[c][0]
    nw = pv + nk
print(nw)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bisect

s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

alp = [[] for i in range(26)]
for i, si in enumerate(s):
    alp[ord(si) - 97].append(i)

ans, cnt = 1 - lens, 0
for i in t:
    li = alp[ord(i) - 97]
    ans += lens * (cnt == 0)
    num = bisect(li, cnt)
    ans += lens * (num == len(li))
    cnt = (li[num % len(li)] + 1) % lens
print(ans + (cnt - 1) % lens)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bisect

s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

alp = [[] for i in range(26)]
for i, si in enumerate(s):
    alp[ord(si) - 97].append(i)

ans, cnt = 1 - lens, 0
for i in t:
    li = alp[ord(i) - 97]
    ans += lens * (cnt == 0)
    num = bisect(li, cnt)
    ans += lens * (num == len(li))
    cnt = (li[num % len(li)] + 1) % lens 
print(ans + (cnt - 1) % lens)

Submission status: Accepted

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


s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

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

ans, cnt = 1 - lens, 0
for i in t:
    ans += lens * (cnt == 0)
    num = bisect(alp[i], cnt)
    ans += lens * (num == len(alp[i]))
    cnt = (alp[i][num % len(alp[i])] + 1) % lens 
print(ans + (cnt - 1) % lens)

Submission status: Accepted

Solution code:
def solve():
    import bisect
    S = input()
    T = input()
    dic = {}
    length = {}

    for i, s in enumerate(S, 1):
        if s not in dic:
            dic[s] = []
        dic[s].append(i)

    for k, v in dic.items():
        if k not in length:
            length[k] = 0
        length[k] = len(v)

    l, turn, prov = len(S), 0, 0

    for t in T:
        if t not in dic:
            print(-1)
            exit()
        x = bisect.bisect(dic[t], prov)
        if x < length[t]:
            prov = dic[t][x]
        else:
            turn += 1
            prov = dic[t][0]
    print(turn * l + prov)

solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect

s = input()
S = len(s)
t = input()
T = len(t)
D = defaultdict(list)
Dc = defaultdict(int)
Exists = True

for i in range(S):
  D[s[i]].append(i+1)
  Dc[s[i]] += 1

ans = 0
temp = 0
for i in range(T):
  if D[t[i]] == []:
    Exists = False
    break
  j = bisect(D[t[i]], temp)
  if j == Dc[t[i]]:
    ans += S - temp + D[t[i]][0]
    temp = D[t[i]][0]
  else:
    ans += D[t[i]][j] - temp
    temp = D[t[i]][j]

if Exists:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
import bisect

def ctoi(char):
  return ord(char)-ord('a')

s=input()
l=len(s)
t=input()
if len(set(t)-set(s))!=0:
  print(-1)
  exit()
pos=[[] for _ in range(26)]
for i in range(2*l):
  pos[ctoi(s[i%l])].append(i+1)
index=0
loop=0
for i in range(len(t)):
  tmp=bisect.bisect_right(pos[ctoi(t[i])],index)
  next_index=pos[ctoi(t[i])][tmp]
  if next_index>=l:
    loop+=1
  index=next_index%l
print(l*loop+index)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
flag = [False] * 26
for si in s:
    flag[ord(si) - ord('a')] = True
for ti in t:
    if not flag[ord(ti) - ord('a')]:
        print(-1)
        quit()
n = len(s)
S = s + s
idx = [[] for _ in range(26)]
for i in range(2*n):
    idx[ord(S[i]) - ord('a')].append(i)

dp = [[inf] * 26 for _ in range(n)]
for i in range(n):
    for j in range(26):
        if idx[j]:
            r = br(idx[j], i)
            dp[i][j] = idx[j][r]
c = ord(t[0]) - ord('a')
i = idx[c][0]
ans = i + 1
for ti in t[1:]:
    c = ord(ti) - ord('a')
    ni = dp[i][c] % n
    ans += dp[i][c] - i
    i = ni
print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
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)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

s = sr()
t = sr()
n = len(s)
dic = {chr(ord('a')+i):[] for i in range(26)}
for i,c in enumerate(s):
    dic[c].append(i+1)
for c in t:
    if not dic[c]:
        print('-1')
        sys.exit()
ans = 0
pre = 0
for c in t:
    ind = bisect.bisect_left(dic[c],pre+1)
    if ind == len(dic[c]):
        ans+=(n-pre)
        pre = dic[c][0]
        ans+=pre
    else:
        ans+=(dic[c][ind]-pre)
        pre = dic[c][ind]
print(ans)

Submission status: Accepted

Solution code:
import copy

s = input()
t = input()

sn = len(s)
tn = len(t)
a = [[] for i in range(26)]
for i in range(sn):
    num = ord(s[i]) - 97
    a[num].append(i)

table = [[0]*sn for i in range(26)]
for i in range(26):
    if a[i]:
        table[i][:] = [copy.deepcopy(a[i][0])]*sn
    f = 0
    for j in a[i]:
        table[i][f:j] = [copy.deepcopy(j)]*(j-f)
        f = copy.deepcopy(j)

flg = True
cnt = 0 # 今何週したか
x = -1 # 今何文字目か
for i in range(tn):
    num = ord(t[i]) - 97
    # sの中に対象の文字が存在しない
    if not a[num]:
        flg = False
        break
    # sの中に対象の文字が存在
    xx = copy.deepcopy(x)
    x = table[num][x]
    if xx >= x:
        cnt += 1
print(cnt*sn + x+1) if flg else print(-1)

Submission status: Accepted

Solution code:
from bisect import bisect_right
s=input()
t=input()
ns=len(s)
nt=len(t)
alp=[[] for i in range(26)]
for i in range(ns):
    alp[ord(s[i])-97].append(i)
alpl=[len(alp[i]) for i in range(26)]
ans=0
now=-1
for i in range(nt):
    if alpl[ord(t[i])-97]==0:
        exit(print(-1))
    b=bisect_right(alp[ord(t[i])-97],now)
    if b==alpl[ord(t[i])-97]:
        now=alp[ord(t[i])-97][0]
        ans+=ns
        if i==nt-1:
            ans+=(now+1)
    else:
        now=alp[ord(t[i])-97][b]
        if i==nt-1:
            ans+=(now+1)
print(ans)