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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import bisect

def main():
  s = input().strip()
  t = input().strip()
  ns = len(s)
  
  if len(set(list(t)) - set(list(s))):
    print(-1)
    return
  
  ichs = defaultdict(list)  
  for i, c in enumerate(s):
    ichs[c].append(i)
    
  ic = -1
  cnt = 0
  for c in t:
    ix = bisect.bisect_right(ichs[c], ic)
    
    if ix >= len(ichs[c]):
      cnt += 1
      ix = 0
    else:
      if ic == ichs[c][ix]:
        if ix + 1 >= len(ichs[c]):
          cnt += 1
          ix = 0
        else:
          ix += 1
    ic = ichs[c][ix]
  print(cnt*ns + ic + 1)
    
      
    
  

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  s = str(input())
  s_ = set(list(s))
  t =  str(input())
  t_ =  set(list(t))
  alphabet = "abcdefghijklmnopqrstuvwxyz"
  if t_ <= s_:
    length_s = len(s)
    
    res = [[length_s]*(26)  for _ in range(length_s+1)]
    for i in range(length_s-1, -1, -1):
      for j in range(26):
        if s[i] == alphabet[j]:
          res[i][j] = i+1
        else:
          res[i][j] = res[i+1][j]
    ans = 0
    now = 0
    for i in range(len(t)):
      for j in range(26):
        if t[i] == alphabet[j]:
          ans += res[now][j]-now
          now = res[now][j]
          if now == length_s:
            if t[i] == s[-1]:
              now = 0
            else:
              ans += res[0][j]
              now = res[0][j]
    print(ans)
  else:
    print(-1)
if  __name__  == "__main__":
  main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(S, T):
    if len(set(c for c in T) - set(c for c in S)) > 0:
        return -1

    from collections import defaultdict
    si = defaultdict(list)
    for i, c in enumerate(S):
        si[c].append(i)

    ans = 0
    ci = 0
    from bisect import bisect_left
    for i, c in enumerate(T):
        j = bisect_left(si[c], ci)
        if j == len(si[c]):
            j = 0
            ans += 1
        ci = si[c][j] + 1
    return (ans)*len(S) + ci





def main():
    S = read_str()
    T = read_str()
    print(slv(S, T))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def atoNum(s):
    return ord(s)-97
where = [[]for i in range(0,26,1)]
from bisect import bisect_right

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

for i in range(0,len(s),1):
    where[atoNum(s[i])].append(i)
ans = 0
cersol = -1

for i in range(0,len(t),1):
    if len(where[atoNum(t[i])])==0:
        print(-1)
        exit()
    tmpCersol = bisect_right(where[atoNum(t[i])],cersol)
    if tmpCersol < len(where[atoNum(t[i])]):
        cersol = where[atoNum(t[i])][tmpCersol]
    else:
        ans += len(s)
        cersol = where[atoNum(t[i])][0]
ans += cersol
print(ans+1)

Submission status: Accepted

Solution code:
from collections import Counter
import bisect

s = input()
t = input()
"""
TLE問題なのは間違いないが、工夫も結構厳しい必要がありそう
二分探索を用いれば, O(|t| log|s|)の定数倍で解ける？
"""

# 絶対に作れないやつは-1を出す、それ以外は絶対に作れる.
sc = Counter(s)
tc = Counter(t)
for i, j in tc.most_common():
	if sc[i] == 0:
		print(-1)
		exit()

"""
O(|t| |s|)で解けるが、TLE確実.
bisectを使う。
"""

target = ord("a")
ordl = [[] for _ in range(26)]
for i, j in enumerate(s):
	ordl[ord(j)-target].append(i)
ordllen = [len(ordl[i]) for i in range(26)]

# ordl := 各文字のindex番号.

times = 0
cnt = -1
ans = 0
for i in t:
	k = ord(i)-target
	m = bisect.bisect_right(ordl[k], cnt)
	if m == ordllen[k]:
		times += 1
		cnt = ordl[k][0]
	else:
		cnt = ordl[k][m]

ans = times * len(s) + cnt + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
from bisect import bisect_right

s = input()
t = input()

c = Counter(s)
for e in t:
    if c[e] == 0:
        print(-1)
        exit()

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

now = -1
ans = 0
for e in t:
    i = bisect_right(d[e], now)
    nxt = d[e][i]
    ans += nxt - now
    now = nxt % len(s)

print(ans)

Submission status: Accepted

Solution code:

import sys
import bisect

s = input()
t = input()

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

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

numbered_t = [0]*len(t)
for i in range(len(t)):
    numbered_t[i] = (ord(t[i])-97)

# confirmation each necessary alphabet exists
all_necessary_alphabets = set()
for i in range(len(t)):
    all_necessary_alphabets.add(numbered_t[i])

for necessary_alphabet in all_necessary_alphabets:
    if len(existing_alphabets[necessary_alphabet])==0:
        print(-1)
        sys.exit()

# counting order process
now = -1
cycled = 0
for i in range(len(numbered_t)):
    existing_alphabet = existing_alphabets[numbered_t[i]]
    can_insert = bisect.bisect_right(existing_alphabet,now)
    if can_insert == len(existing_alphabet):
        can_insert = 0
        cycled += 1
    now = existing_alphabet[can_insert]

ans = len(s) * cycled + now + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import bisect

s = input()
t = input()
ss = s*2

S = Counter(s)
T = Counter(t)

for i in T.keys():
    if i not in S:
        print(-1)
        exit()

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

for i,j in enumerate(ss):
    alpha[ord(j)-ord("a")].append(i)

rep,now = 0,-1

for i in t:
    alp = alpha[ord(i) - ord('a')]
    i = bisect.bisect_left(alp,now+1)
    now = alp[i]
    if now >= len(s):
        now -= len(s)
        rep += 1

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

Submission status: Accepted

Solution code:
def solve():
  s = input()
  t = input()
  ans = 0
  alp = [[] for _ in range(27)]
  length_s = len(s)
  for i in range(length_s):
    char = ord(s[i]) - ord('a')
    alp[char].append(i + 1)
  length_t = len(t)
  import bisect
  for i in range(length_t):
    char = ord(t[i]) - ord('a')
    if alp[char]:
      if ans % length_s >= alp[char][-1]:
        ans = (ans // length_s + 1) * length_s
      index = bisect.bisect_right(alp[char], ans % length_s)
      ans += alp[char][index] - ans % length_s
    else:
      return -1
  return ans
print(solve())

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = tuple(map(lambda c: ord(c) - ord("a"), input()))
t = tuple(map(lambda c: ord(c) - ord("a"), input()))
S, T = set(s), set(t)
if T & S != T:
    print(-1)
    quit()
d, l = [[] for _ in range(26)], [0] * 26
for idx, c in enumerate(s):
    d[c].append(idx)
    l[c] += 1
prev = -1
loop = 0
for c in t:
    idx = bisect_right(d[c], prev)
    if idx >= l[c]:
        loop += 1
        prev = d[c][0]
    else:
        prev = d[c][idx]
print((loop) * len(s) + prev + 1)

Submission status: Accepted

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

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        if not T[i] in seen:
            print(-1)
            exit()

        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,rep)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,rep)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + pre + 1
    print(ans)




if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
def solve():
    s = input()
    t = input()
    d = defaultdict(list)
    st_s = set(s)

    for i in range(len(s)):
        d[s[i]].append(i)
    
    round = 0
    prev = -1
    for i in range(len(t)):
        if not t[i] in st_s:
            print(-1)
            return
        now = getNextIdx(prev,d[t[i]])
        if now <= prev:
            round += 1
        
        prev = now
    
    print(prev + round*len(s) + 1)

def getNextIdx(prev,idx_list):
    ret_idx = bisect.bisect_right(idx_list, prev)
    if ret_idx == len(idx_list):
        return idx_list[0]

    return idx_list[ret_idx]

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from string import ascii_lowercase


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

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

    if not(set_t <= set_s):
        print(-1)
        exit()

    ans = 0
    d = {c:[] for c in ascii_lowercase}
    
    for i, c in enumerate(s):
        d[c].append(i+1)
    
    now = 0
    for c in t:
        
        idx = bisect_left(d[c], now+1)

        if idx == len(d[c]):
            ans += len(s)
            now = 0
            idx = bisect_left(d[c], now+1)
            
        now = d[c][idx]

    ans += now
    print(ans)

        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect


def main() -> None:
    S = input()
    T = input()
    SS = S + S
    alphas = [[] for _ in range(26)]
    for i, s in enumerate(SS):
        alphas[ord(s) - ord('a')].append(i)
    rep, now = 0, -1
    for t in T:
        alpha = alphas[ord(t) - ord('a')]
        i = bisect.bisect_left(alpha, now + 1)
        if i == len(alpha):
            print(-1)
            return
        now = alpha[i]
        if now >= len(S):
            now -= len(S)
            rep += 1
    print(rep * len(S) + now + 1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s, t = [x.strip() for x in open(0).readlines()]
if set(t) - set(s) != set():
    print(-1)
else:
    d = defaultdict(list)
    n = len(s)
    for i, c in enumerate(s, 1):
        d[c].append(i)
    for k in d:
        d[k].append(d[k][0] + n)
    ans = 0
    for c in t:
        q, r = divmod(ans, n)
        x = d[c][bisect.bisect(d[c], r)]
        ans = n*q + x
    print(ans)

Submission status: Accepted

Solution code:
import collections

s = input()
t = input()
s_len = len(s)
s_idx = dict([])
for i, key in enumerate(s):
    try:
        s_idx[key].append(i + 1)
    except KeyError:
        s_idx[key] = [i + 1]

def binary_search(li, tmp, ng, ok):
    mid = (ng + ok) // 2
    if ok - ng < 2:
        if ok == len(li):
            return s_len + li[0]
        else:
            return li[ok]
    if li[mid] <= tmp: return binary_search(li, tmp, mid, ok)
    else: return binary_search(li, tmp, ng, mid)

ans = 0
ex_i = 0
for key in t:
    try:
        i = binary_search(s_idx[key], ex_i, -1, len(s_idx[key]))
        ans += i - ex_i
        ex_i = i % s_len
    except KeyError:
        ans = -1
        break
print(ans)

Submission status: Accepted

Solution code:
import collections

s = input()
t = input()
mod = len(s)
s_idx = dict([])
for i, key in enumerate(s):
    try:
        s_idx[key].append(i + 1)
    except KeyError:
        s_idx[key] = [i + 1]

def binary_search(li, tmp, ng, ok):
    mid = (ng + ok) // 2
    if ok - ng < 2:
        if ok == len(li):
            return mod + li[0]
        else:
            return li[ok]
    if li[mid] <= tmp: return binary_search(li, tmp, mid, ok)
    else: return binary_search(li, tmp, ng, mid)

ans = 0
tmp = 0
for key in t:
    try:
        i = binary_search(s_idx[key], tmp, -1, len(s_idx[key]))
        ans += i - tmp
        tmp = i % mod
    except KeyError:
        ans = -1
        break
print(ans)

Submission status: Accepted

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

S_ = set(list(S))
T_ = set(list(T))
for c in T:
    if c not in S_:
        print(-1)
        exit()

d = [[] for _ in range(26)]
for i, s in enumerate(S):
    d[ord(s)-ord('a')].append(i)
#print(d)

q = 0
pre = -1
import bisect
for t in T:
    j = ord(t)-ord('a')
    idx = bisect.bisect_right(d[j], pre)
    if idx == len(d[j]):
        q += 1
        pre = d[j][0]
    else:
        pre = d[j][idx]
print(q*len(S)+pre+1)

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = input()
t = input()
alpha = [[] for _ in range(26)]
def f(c): return ord(c)-ord("a")

for i,c in enumerate(s): alpha[f(c)].append(i)
idx = -1
loop = 0
for c in t:
    lst = alpha[f(c)]
    if not lst:
        ans = -1
        break
    i = bisect_right(lst,idx)
    if i == len(lst):
        loop += 1
        idx = lst[0]
    else:
        idx = lst[i]
else:
    ans = len(s)*loop+idx+1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = input()
t = input()
alpha = [[] for _ in range(26)]
def f(c): return ord(c)-ord("a")

for i,c in enumerate(s): alpha[f(c)].append(i)
idx = -1
roop = 0
for c in t:
    lst = alpha[f(c)]
    if not lst:
        ans = -1
        break
    i = bisect_right(lst,idx)
    if i == len(lst):
        roop += 1
        idx = lst[0]
    else:
        idx = lst[i]
else:
    ans = len(s)*roop+idx+1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = input()
t = input()
alpha = [[] for _ in range(26)]
def f(c): return ord(c)-ord("a")


for i,c in enumerate(s): alpha[f(c)].append(i)
# print(alpha)
idx = -1
roop = 0
for c in t:
    lst = alpha[f(c)]
    if not lst:
        ans = -1
        break
    i = bisect_right(lst,idx)
    if i == len(lst):
        roop += 1
        idx = lst[0]
    else:
        idx = lst[i]
else:
    ans = len(s)*roop+idx+1
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    s = list(map(lambda x: ord(x) - ord('a'), input()))
    t = list(map(lambda x: ord(x) - ord('a'), input()))
    n = len(s)
    a_list = [[] for _ in range(26)]

    for i in range(n):
        a_list[s[i]].append(i)

    for tt in list(set(t)):
        if len(a_list[tt]) == 0:
            print(-1)
            exit()

    now_i = -1
    count = 0
    t = deque(t)
    ts = t.popleft()
    while True:
        index = bisect.bisect_right(a_list[ts], now_i)
        if index == len(a_list[ts]):
            count += 1
            now_i = -1
        else:
            now_i = a_list[ts][index]
            if not t:
                break
            ts = t.popleft()

    print(n * count + now_i + 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
S = list(input())
T = list(input())
C = {}
for i in range(97, 97+26):
    C[chr(i)] = -1

k = len(T)
for i in range(len(S)):
    if C[S[i]] == -1:
        C[S[i]] = [i]
    else:
        C[S[i]].append(i)

p = 0
now = -1
ans = 0
used = {}
L = {}
for i in range(97, 97+26):
    used[chr(i)] = 0
    if C[chr(i)] == -1:
        L[chr(i)] = 0
    else:
        L[chr(i)] = len(C[chr(i)])

while(True):
    n = T[p]
    if C[n] == -1:
        print(-1)
        sys.exit()
    else:
        if used[n] >= L[n]:
            p -= 1
            for i in range(97, 97 + 26):
                used[chr(i)] = 0
            ans += len(S) - now - 1
            now = -1
        elif C[n][used[n]] >= now:
            ans += C[n][used[n]] - now
            now = C[n][used[n]]
            used[n] += 1
        else:
            used[n] += 1
            p -= 1
    p += 1
    if p == k:
        print(ans)
        break

Submission status: Accepted

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

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

from bisect import bisect_left

ans = 0
before = -1
flag = True
for char in t:
    if pos[char] == []:
        flag = False
        break

    if before > pos[char][-1]:
        ans += len(s)
        before = pos[char][0] + 1
    else:
        idx = bisect_left(pos[char], before)
        before = pos[char][idx] + 1

if flag:
    print(ans + before)
else:
    print(-1)

Submission status: Accepted

Solution code:
import collections
s = raw_input()
t = raw_input()
sb = s + s
h = {chr(ord('a') + i):-1 for i in range(26)}
dp = []
for j in range(len(sb)-1,-1,-1):
	dp.append({k:h[k] for k in h})
	h[sb[j]] = j
special = h
dp = dp[::-1]
i = -1
j = 0
c = 0
while(j < len(t)):
	ha = dp[i] if i >= 0 else special
	letter = t[j]
	if ha[letter] != -1:
		i = ha[letter]
		j += 1
	else:
		j = -1
		break

	if i >= len(s):
		i %= len(s)
		c+=1

print (c * len(s) + i + 1) if j != -1 else -1

Submission status: Accepted

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

S = readline().rstrip()
T = readline().rstrip()

if len(set(T) - set(S)) > 0:
  print(-1)
  exit(0)
  
import bisect
S2 = S * 2
from collections import defaultdict
dic = defaultdict(list)

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

ind = -1
ans = 0
for t in T:
  targets = dic[t]
  newind = targets[bisect.bisect_left(targets, ind + 1)]
  ans += (newind - ind)
  if newind >= len(S):
    newind -= len(S)
  ind = newind

print(ans)

Submission status: Accepted

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

S = readline().rstrip()
T = readline().rstrip()

if len(set(T) - set(S)) > 0:
  print(-1)
  exit(0)
  
import bisect
# Tの各文字を探す
S2 = S * 2
from collections import defaultdict
# ある文字が何文字目にあるか辞書
dic = defaultdict(list)

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

ind = -1
ans = 0
for t in T:
  # 探す文字はt
  targets = dic[t]
#  print("targets",targets,"t",t,"ind + 1",ind + 1)
  newind = targets[bisect.bisect_left(targets, ind + 1)]
#  print("t",t,"S2",S2,"newind",newind)
  ans += (newind - ind)
  if newind >= len(S):
    newind -= len(S)
  ind = newind

print(ans)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left

    S = input()
    T = input()

    L = len(S)

    pos = tuple(list() for _ in range(26))
    orda = ord('a')
    for i, c in enumerate(S):
        j = ord(c) - orda
        pos[j].append(i)

    rep = 0
    curr = 0
    for c in T:
        j = ord(c) - orda

        if not pos[j]:
            print(-1)
            return

        i = bisect_left(pos[j], curr)
        if i == len(pos[j]):
            rep += 1
            i = 0  # pos[j][0]文字目がc
        curr = pos[j][i] + 1  # pos[j][i]にしたら同じ文字が続くケースでWA

    print(rep * L + curr)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

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

if not set(t).issubset(set(s)):
    print(-1)
    exit()

indices = [[] for _ in range(26)]
idx = [0]*26

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

now = 0
rep = 1
for i in range(len(t)):
    x = ord(t[i]) - 97
    y = bisect.bisect_left(indices[x], now)
    if y == len(indices[x]):
        rep += 1
        now = indices[x][0] + 1
    else:
        now = indices[x][y] + 1

print(len(s)*(rep-1) + now)

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

d = {}
N = len(s)
for i in range(N):
    if s[i] not in d:
        d[s[i]] = [i]
    else:
        d[s[i]].append(i)

now = -1
c = 0
for i in range(len(t)):
    if t[i] in d:
        next = bisect.bisect_right(d[t[i]],now)
        if next < len(d[t[i]]):
            nnum = d[t[i]][next]
            now = nnum
        else:
            c += 1
            now = -1
            next = bisect.bisect_right(d[t[i]],now)
            nnum = d[t[i]][next]
            now = nnum
    else:
        print(-1)
        break
else:
    print(c*N+now+1)

Submission status: Accepted

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

sbasic=[[] for _ in range(26)]
for i,s in enumerate(S):
  sbasic[ord(s)-ord("a")].append(i)

for t in set(T):
    if len(sbasic[ord(t)-ord("a")])==0:
        print(-1)
        exit()

slist=copy.deepcopy(sbasic)
index=-1
roop=0
for t in T:
  if len(sbasic[ord(t)-ord("a")])==0:
    roop+=1
    #slist=copy.deepcopy(sbasic)
    index=-1
  pos=bisect.bisect_right(sbasic[ord(t)-ord("a")],index)
  if pos==len(sbasic[ord(t)-ord("a")]):
    roop+=1
    #slist=copy.deepcopy(sbasic)
    index=-1
    pos=0
  index=sbasic[ord(t)-ord("a")][pos]
  
print(len(S)*roop+index+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappushpop, heapify, heapreplace
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
input = sys.stdin.readline
 
S = input().rstrip()
T = input().rstrip()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()

# set:T が set:S に含まれない => S にない文字を T で使っていたら
if not set(T) <= set(S):
    print(-1)
    sys.exit()

ind = -1
cnt = 0
for t in T:
    # 現在の index 以降から探索する
    ind = S.find(t,ind+1)
    # 見つからない場合は先頭から探索し直し, loop countを+1
    if ind == -1:
        cnt += 1
        ind = S.find(t)

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

Submission status: Accepted

Solution code:
A = tuple(range(10**5))

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import heapq
import bisect
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import math
import heapq
import bisect
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
import bisect
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
import heapq
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import math
import heapq
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import heapq

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
import heapq
from collections import defaultdict

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
from heapq import heappush
from collections import defaultdict

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
from heapq import heappush, heappop,heappushpop
from collections import defaultdict

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)