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:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
t = ins()
oa = ord('a')
ls = len(s)
nxt = [[-1]*26 for i in range(ls)]
nx = [-1]*26
for i in range(2*ls-1,-1,-1):
    c = ord(s[i%ls])-oa
    for j in range(26):
        if i<ls and nx[j]>=0:
            nxt[i][j] = nx[j]-i
    nx[c] = i
if DBG:
    for i in range(ls):
        #printn(f"{i} ")
        print(nxt[i])

prevpos = nxt[ls-1][ord(t[0])-oa]-1
if prevpos<0:
    print(-1)
    exit()
for i in range(1,len(t)):
    c = ord(t[i])-oa
    nx = nxt[prevpos%ls][c]
    if nx<0:
        print(-1)
        exit()
    prevpos += nx
    #ddprint(f"i {i} pp {prevpos} c {c} ti {t[i]}")
print(prevpos+1)

Submission status: Accepted

Solution code:
s=input()
t=input()
cnt=0
mod=-1
tmp_s=""
for cha in t:
    if cha not in s:
        print(-1)
        exit()
    elif cha in tmp_s:
        idx=tmp_s.find(cha)
        mod+=idx+1   
    else:
        idx=s.find(cha)
        if idx<=mod:
            cnt+=1  
        mod=idx
    
    if mod==len(s)-1:
        tmp_s=" "
    else:
        tmp_s=s[mod+1:]

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

Submission status: Accepted

Solution code:
#138-e
from collections import defaultdict
import bisect

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

ans=0
pos=-1

d = defaultdict(list)
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i)
        
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i+n)
        
for v in t:
    l = d[v]
    ind = bisect.bisect_right(l, pos)
    if l:
        ans += l[ind]-pos
        if l[ind]<n:
            pos = l[ind]
        else:
            pos = l[ind] - n
    else:
        ans = -1
        break
        
print(ans)

Submission status: Accepted

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

d = {char:[] for char in 'abcdefghijklmnopqrstuvwxyz'}
for i in range(len(s)):
    d[s[i]].append(i)

cnt = 0
index = 0
for char in t:
    if not d[char]:
        print(-1)
        sys.exit()
    i = bisect_left(d[char], index)
    if i == len(d[char]):
        cnt += 1
        index = d[char][0]
    else:
        index = d[char][i]
    index += 1

ans = cnt * len(s) + index
print(ans)

Submission status: Accepted

Solution code:
def sn(a):
    return ord(a) - ord("a")

def isok(idx,prev):##適宜変更
    return prev>=idx+n*loops


def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ

S = input()
T = input()
lt = list(T)
ls = list(S)
set_s = set(list(S))
set_t = set(lt)
if not set_t <= set_s:
    print(-1)
    exit()
cnts = [[] for i in range(26)]
cnts_idx = [0]*26
for i,w in enumerate(ls):
    cnts[sn(w)].append(i)

loops = 0
n = len(S)
prev = -1
for t in lt:
    idx = bisect(cnts[sn(t)],prev)+1
    if idx==len(cnts[sn(t)]):
        loops+=1
        idx = 0
    prev = cnts[sn(t)][idx] + loops*n

print(prev+1)

Submission status: Accepted

Solution code:
import bisect
s = list(input())
t = list(input())
n = len(s)
m = len(t)
alphabet = [[] for _ in range(26)]
for i in range(n):
  alphabet[ord(s[i])-ord('a')] += [i] 
loop = 0
pre = -1
for i in range(m):
  c = ord(t[i]) - ord('a')
  if len(alphabet[c]) == 0:
    print(-1)
    exit()
  idx = bisect.bisect_left(alphabet[c], pre+1)
  if idx == len(alphabet[c]):
    loop += 1
    pre = alphabet[c][0]
  else:
    pre = alphabet[c][idx]

print(pre + loop * n + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = input().strip()
t = input().strip()
chk = [[] for i in range(26)]
ma = [0]*26
ex = [False]*26
for i,si in enumerate(s):
  num = ord(si)-97
  chk[num].append(i+1)
  if not ex[num]:
    ex[num] = True
  ma[num] = i+1
  
import math,bisect
now = 0
ans = 0
l = len(s)
for i,ti in enumerate(t):
  ans += 1
  j = i+1
  n = ord(ti)-97
  if not ex[n]:
    ans = -1
    break
  if ans > now*l + ma[n]:
    now = math.ceil((ans-ma[n])/l)
  ind = bisect.bisect_left(chk[n],ans-now*l)
  ans = chk[n][ind] + now*l
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = input()
t = input()

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

for i in range(len(s)):
    A[ord(s[i]) - ord("a")].append(i+1)

from bisect import bisect_left as bl
'''index  =  bl(list,num)'''
nagasa = len(s)
ans = 0
ima = 0
mae = 0
for i in range(len(t)):
    tmp = bl(A[ord(t[i]) -ord("a")],ima+1)
    if tmp == len(A[ord(t[i]) -ord("a")]):
        ans += nagasa - ima
        ima = 0
        tmp = bl(A[ord(t[i]) -ord("a")],ima+1)
        if tmp == len(A[ord(t[i]) -ord("a")]):
            print(-1)
            exit()
    mae = ima
    ima = A[ord(t[i]) -ord("a")][tmp]
    ans += ima - mae
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    T = input()
    N = len(S)
    idx = defaultdict(list)
    for i, s in enumerate(S):
        idx[s].append(i)

    # 直前にみたx
    x = -1
    n_loop = 0
    for t in T:
        arr = idx[t]
        if len(arr) == 0:
            print(-1)
            return

        x += 1
        i = bisect.bisect_left(arr, x)
        if i < len(arr):
            x = arr[i]
        else:
            n_loop += 1
            x = arr[0]

    print(n_loop * N + x + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#O(|S|log|s|)
def main():
	s=input()
	t=input()
	n=len(s)
	now=-1
	ans=1
	if not set(t)<=set(s):#tがsの部分集合でない
		print(-1)
		exit()
	for x in t:
		now=s.find(x,now+1)#nowより大きいところからxを探す
		if now==-1:#nowより大きいところでxが見つからなかったら
			ans+=n
			now=s.find(x)
	print(ans+now)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
s=input()
t=input()
s*=2
next=[[-1]*26 for _ in range(len(s))]
alph=[[]for _ in range(26)]
for i in range(len(s)):
	alph[ord(s[i])-ord("a")].append(i)
from bisect import bisect_right
for i in range(len(s)//2):
	for j in range(26):
		if len(alph[j])>bisect_right(alph[j],i):
			next[i][j]=alph[j][bisect_right(alph[j],i)]
ans=1
now=len(s)//2-1
for x in t:
	r=ord(x)-ord("a")
	now=next[now][r]
	if now==-1:
		print(-1)
		exit()
	if now>=len(s)//2:
		ans+=len(s)//2
		now-=len(s)//2
print(ans+now-len(s)//2)

Submission status: Accepted

Solution code:
s=input()
t=input()
from bisect import bisect
points=[[]for i in range(26)]
a=ord("a")
for i,c in enumerate(s):
    points[ord(c)-a].append(i)
for p in points:
    p.append(10**9)

n=len(s)
idx=-1
stage=0
for c in t:
    c=ord(c)-a
    p=points[c]
    if len(p)==1:
        stage=0
        idx=-2
        break
    idx = p[bisect(p,idx)]
    if idx>10**6:
        idx=p[0]
        stage+=1
print(stage*n+idx+1)

Submission status: Accepted

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    t = input()

    # 構成不可能な場合
    set_s = set(s)
    for char_t in t:
        if char_t not in set_s:
            print(-1)
            exit()

    # 構成可能な場合    
    # 前処理 O(n)
    s_table = [[] for _ in range(ord('z') - ord('a') + 1)]
    for i, s_char in enumerate(s):
        s_table[ord(s_char) - ord('a')].append(i)
    # print(s_table)
    # O(nlgn)
    loop_count = 0
    prev = -1
    for t_char in t:
        candidate = s_table[ord(t_char) - ord('a')]
        j = bisect_left(candidate, prev+1)    # prev より大きくないとだめ
        if j == len(candidate):
            loop_count += 1
            prev = candidate[0]
        else:
            prev = candidate[j]
    print(prev + loop_count * len(s) + 1)


if __name__ == "__main__":
    main()

    """
    解説
    俺の二分探索の方針以外にも「ある index 以降で次に char(a-z) が出現する index を O(alpha)*O(|s|) で求めておく」と言った方法がある。
    こちらは O(|s|) + O(alpha) * O(|s|) + O(|t|)
    二分探は O(|s|) + O(lg|s|) * O(|t|)
    O(alpha) = 26, O(lg|10**5|) = 16, O(|s|) = O(|t|) より今回最悪計算量に変わりはない

    s を二つ連結した文字列を用意して調べると楽らしい。確かに。(必ず探索場所がヒットするので)
    """

Submission status: Accepted

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    t = input()

    # 構成不可能な場合
    set_s = set(s)
    for char_t in t:
        if char_t not in set_s:
            print(-1)
            exit()

    # 構成可能な場合    
    # 前処理 O(n)
    s_table = [[] for _ in range(ord('z') - ord('a') + 1)]
    for i, s_char in enumerate(s):
        s_table[ord(s_char) - ord('a')].append(i)
    # print(s_table)
    # O(nlgn)
    loop_count = 0
    prev = -1
    for t_char in t:
        candidate = s_table[ord(t_char) - ord('a')]
        j = bisect_left(candidate, prev+1)    # prev より大きくないとだめ
        if j == len(candidate):
            loop_count += 1
            prev = candidate[0]
        else:
            prev = candidate[j]
    print(prev + loop_count * len(s) + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    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
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    s = input().rstrip()
    ls = len(s)
    t = input().rstrip()
    lt = len(t)
    alphabet = 'abcdefghijklmnopqrstuvwxyz' #26
    moji = [[] for _ in range(26)]
    for i in range(ls):
        idx = alphabet.index(s[i])
        moji[idx].append(i+1)
    
    cnt = 0
    res = 0
    while cnt < lt:
        for i in range(cnt, lt):
            idx = alphabet.index(t[i])
            if not moji[idx]:
                print(-1)
                exit()
            if i == cnt:
                now = moji[idx][0] + 1
            else:
                nex = bisect_left(moji[idx], now)
                if nex == len(moji[idx]):
                    res += ls
                    cnt = i
                    break
                now = moji[idx][nex] + 1
        else:
            res += now - 1
            break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    s = input().rstrip()
    ls = len(s)
    t = input().rstrip()
    lt = len(t)
    alphabet = 'abcdefghijklmnopqrstuvwxyz' #26
    dic = {}
    for i in range(26):
        dic[alphabet[i]] = i
    moji = [[] for _ in range(26)]
    for i in range(ls):
        moji[dic[s[i]]].append(i+1)
    
    cnt = 0
    res = 0
    while cnt < lt:
        for i in range(cnt, lt):
            if not moji[dic[t[i]]]:
                print(-1)
                exit()
            if i == cnt:
                now = moji[dic[t[i]]][0] + 1
            else:
                nex = bisect_left(moji[dic[t[i]]], now)
                if nex == len(moji[dic[t[i]]]):
                    res += ls
                    cnt = i
                    break
                now = moji[dic[t[i]]][nex] + 1
        else:
            res += now - 1
            break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    a=ord('a')
    s=list(map(lambda x:ord(x)-a,input()))
    N=len(s)
    t=list(map(lambda x:ord(x)-a,input()))
    l=[[-1]*26 for _ in range(len(s))]
    for i in range(N-1,-N,-1):
        for j in range(26):
            if s[i]==j:
                l[i-1][j]=i%N
            else:
                l[i-1][j]=l[i][j]
    ans=0
    index=N-1
    for a in t:
        n=l[index][a]
        if n==-1:
            print(-1)
            exit()
        if n>index:
            ans+=n-index
        else:
            ans+=n+N-index
        index=n
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a = ord('a')

s = [ord(x)-a for x in list(input())]
t = [ord(x)-a for x in list(input())]

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

positions = [[0]*26 for i in range(n+1)]

for i in range(n):
    for j in range(26):
        if j == s[-1-i]:
            positions[-2-i][j] = n-i
        else:
            positions[-2-i][j] = positions[-1-i][j]

roop = 0
p = 0
flag = 1
for i in range(m):
    a = t[i]
    if positions[p][a]==0:
        roop += 1
        p = 0
    p = positions[p][a]
    if p == 0:
        flag = 0
        break

print(roop*n+p if flag else -1)

Submission status: Accepted

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

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

a = set(list(t))
b = set(list(s))

for x in a:
    if x not in b:
        print(-1)
        exit()

positions = [[0]*26 for i in range(n+1)]

for i in range(n):
    for j in range(26):
        if j == ord(s[-1-i])-97:
            positions[-2-i][j] = n-i
        else:
            positions[-2-i][j] = positions[-1-i][j]

roop = 0
p = 0
for i in range(m):
    a = ord(t[i])-97
    if positions[p][a]==0:
        roop += 1
        p = 0
    p = positions[p][a]

print(roop*n+p)

Submission status: Accepted

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

s = input()[:-1]
t = input()[:-1]
idx = defaultdict(list)

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

now = -1
cnt = 0

for i in range(len(t)):
    if t[i] not in idx:
        print(-1)
        exit()
        
    mark = bisect_right(idx[t[i]], now)
    
    if mark==len(idx[t[i]]):
        now = idx[t[i]][0]
        cnt += 1
    else:
        now = idx[t[i]][mark]
    
print(len(s)*cnt+now+1)

Submission status: Accepted

Solution code:
s = input()
t = input()
alpha = "abcdefghijklmnopqrstuvwxyz"
n = len(s)
m = len(t)
D = {}
E = {}
for i in range(n):
  if s[i] in D:
    D[s[i]][i] = i
  else:
    D[s[i]] = [-1 for _ in range(n)]
    D[s[i]][i] = i
  E[s[i]] = i
for i in D:
  p = E[i]
  for j in range(E[i], E[i] - n, -1):
    if D[i][(j+n)%n] == -1:
      D[i][(j+n)%n] = p
    else:
      p = j
x = 0
p = 0
for i in range(m):
  if t[i] in D:
    y = D[t[i]][p]
    if y < p:
      x += 1
    if i != m - 1:
      if y == n - 1:
        x += 1
        p = 0
      else:
        p = (y + 1) % n
    else:
      p = y
  else:
    x = -1
    break
if x == -1:
  print(x)
else:
  print(x*n+p+1)

Submission status: Accepted

Solution code:
from bisect import bisect_left

S = input()
T = input()
N = len(S)
NN = len(T)
S = [ord(S[i]) - 97 for i in range(N)]
T = [ord(T[i]) - 97 for i in range(NN)]

ind = [[] for _ in range(26)]
cnt = [0] * 26
for i in range(N):
    s = S[i]
    ind[s].append(i)
    cnt[s] += 1

part = 0
i = 0
j = -1
cond = 0
while i < NN:
    obj = T[i]
    if cnt[obj] == 0:
        cond = 1
        break

    tmp = bisect_left(ind[obj], j)
    if tmp == cnt[obj]:
        j = ind[obj][0]
        part += 1
        i += 1
        continue
    if ind[obj][tmp] == j:
        tmp += 1

    if tmp == cnt[obj]:
        j = ind[obj][0]
        part += 1
    else:
        j = ind[obj][tmp]

    i += 1


if cond:
    ans = -1
else:

    ans = N * part + (j + 1)

print(ans)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

li = [[] for _ in range(26)]
for i in range(len(s)):
    li[ord(s[i]) - ord('a')].append(i)

count = [0,-1]

for i in range(len(t)):
    t1 = t[i]
    num = ord(t1) - ord('a')
    if not li[num]:
        print(-1)
        exit()
    else:
        if count[1] >= li[num][-1]:
            count[0] += 1
            count[1] = li[num][0]
        else:
            idx = bisect.bisect_right(li[num], count[1])
            count[1] = li[num][idx]

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

Submission status: Accepted

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

from bisect import bisect_right

def main():
    s = input()
    t = input()
    indices = [[] for i in range(26)]
    n = len(s)
    for i in range(n):
        c = s[i]
        ic = ord(c) - ord("a")
        indices[ic].append(i)
    for i in range(26):
        if not indices[i]:
            continue
        indices[i].append(indices[i][0] + n)

    ptr = -1
    for c in t:
        ic = ord(c) - ord("a")
        if len(indices[ic]) == 0:
            print(-1)
            return
        nptr = bisect_right(indices[ic], ptr % n)
        ptr += indices[ic][nptr] - (ptr % n)

    print(ptr + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import exit

s = input()
t = input()

alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
alph_list = dict()
for i in range(26):
  alph_list[alphabet[i]] = i

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

for i in range(len(s)):
  key = s[i]
  counter[alph_list[key]].append(i)

ans = 0
ans_mod = 0
flag = True
for i in range(len(t)):
  key = alph_list[t[i]]
  if not counter[key]:
    flag = False
    break
  l, r = 0, len(counter[key])
  while r-l > 1:
    bit = (r+l)//2
    if counter[key][bit] >= ans:
      r = bit
    else:
      l = bit
  if r == len(counter[key]) and counter[key][l] < ans:
    ans_mod += 1
    ans = counter[key][0]+1
  elif l == 0 and counter[key][l] >= ans:
    ans = counter[key][l]+1
  else:
    ans = counter[key][r]+1
if flag:
  print(ans_mod*len(s)+ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
import bisect

def resolve():
    S = input()
    T=input()

    indexes = dict()

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

    point =-1
    roops = 0
    for i in T:
        if not i in indexes:
            print(-1)
            return
        
        nxt = bisect.bisect_right(indexes[i],point)

        if nxt == len(indexes[i]):
            roops += 1
            point = indexes[i][0]
        else:
            point = indexes[i][nxt]


    print(len(S)*roops+point + 1)





resolve()

Submission status: Accepted

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

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

def srch(num,li):
    if len(li)==0:
        return -10

    fst = 0
    lst = len(li)-1
    while(lst>fst):
        mid = (fst+lst)//2
        if li[mid] <= num:
            fst = mid+1
        else:
            lst = mid
    return li[fst]

def main():
    N = len(S)
    li = [[] for _ in range(26)]
    for i in range(N):
        mm = ord(S[i])-97
        li[mm].append(i)
    for i in range(26):
        if len(li[i])>0:
            li[i].append(li[i][0]+N)
    
    cnt1 = 0
    cnt2 = -1
    for i in range(len(T)):
        mm = ord(T[i])-97
        cnt2 = srch(cnt2,li[mm])
        if cnt2 == -10:
            print(-1)
            return

        if cnt2>=N:
            cnt2 %= N
            cnt1 += 1
    print(cnt1*N+cnt2+1)


    

    
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [[inf] * i for _ in range(26)]
            break
        else:
            i *= 2
    return tree

def update(i, x, tree):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = min(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(s, t, tree):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = inf
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = min(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = min(ans, tree[t])
            t = (t - 1) // 2
    return ans

s = list(input())
t = list(input())
inf = 10 ** 6
n = len(s)
first = [-2] * 26
tree = make_tree(n)
for i in range(n):
    m = ord(s[i]) - 97
    update(i, i, tree[m])
    if first[m] == -2:
        first[m] = i
ans = 1
c = -1
for i in t:
    m = ord(i) - 97
    if not c == -1:
        u = -1
        u = find(c + 1, n - 1, tree[m])
        if u == -1 or u == inf:
            ans += n
            c = -1
        else:
            c = u
    if c == -1:
        c = first[m]
        if c == -2:
            print(-1)
            exit()
ans += c
print(ans)

Submission status: Accepted

Solution code:
#ABC138-E Strings of Impurity
"""
sの好きなだけのループに対する部分文字列tを求める
tにあってsにない文字がある時点でno
そうでないならば必ず達成可能で、
tに対してループを回し(i)、
sのj文字目に関して、それより後に初めて出てくるt[i+1]の場所をindexで返し,i+=1,j=そのindex
にする。
そのようなindexがないならば、j=0とし、またはじめから回す。
"""
import sys
import bisect
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

s = readline().rstrip().decode('utf-8')
t = readline().rstrip().decode('utf-8')
s_s = set(list(s))
t_s = set(list(t))
flag = 1 if s_s & t_s == t_s else 0

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

#lst1:各アルファベットごとに、何番目に出てくるか
lst1 = [[] for _ in range(26)]
kijun = ord("a")
for idx,i in enumerate(s):
    lst1[ord(i)-kijun].append(idx)

i = 0
roop = 0
count = 0
while True:
    if i >= len(t):
        print(roop*len(s)+count)
        break
    now = ord(t[i])-kijun
    res = bisect.bisect_left(lst1[now],count)
    if res == len(lst1[now]):
        roop += 1
        count = 0
        res = bisect.bisect_left(lst1[now],count)
        count = lst1[now][res]+1 #その次の文字から
    else:
        count = lst1[now][res]+1
    i += 1

Submission status: Accepted

Solution code:
#ABC138-E Strings of Impurity
"""
sの好きなだけのループに対する部分文字列tを求める
tにあってsにない文字がある時点でno
そうでないならば必ず達成可能で、
tに対してループを回し(i)、
sのj文字目に関して、それより後に初めて出てくるt[i+1]の場所をindexで返し,i+=1,j=そのindex
にする。
そのようなindexがないならば、j=0とし、またはじめから回す。
"""
import sys
import bisect
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

s = readline().rstrip().decode('utf-8')
t = readline().rstrip().decode('utf-8')
s_s = set(list(s))
t_s = set(list(t))
flag = 1 if s_s & t_s == t_s else 0

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

#2進数で、
lst1 = [[] for _ in range(26)]
kijun = ord("a")
for idx,i in enumerate(s):
    lst1[ord(i)-kijun].append(idx)

i = 0
roop = 0
count = 0
while True:
    if i >= len(t):
        print(roop*len(s)+count) #countは0-indexedの為
        break
    now = ord(t[i])-kijun
    res = bisect.bisect_left(lst1[now],count)
    if res == len(lst1[now]):
        roop += 1
        count = 0
        res = bisect.bisect_left(lst1[now],count)
        count = lst1[now][res]+1 #その次の文字から
    else:
        count = lst1[now][res]+1
    i += 1

Submission status: Accepted

Solution code:
s=input()
t=input()
lens=len(s)
lent=len(t)

alp="abcdefghijklmnopqrstuvwxyz"

D={c : {i:-1 for i in range(lens*2)} for c in alp}

tab={c:0 for c in alp}

for i in range(lens*2):
    nowc=s[i%lens]
    for q in range(tab[nowc],i+1):
        D[nowc][q]=i
    tab[nowc]=i+1

ans=0
pos=0
for i in range(lent):
    nowc=t[i]
    if D[nowc][pos]==-1:
        print(-1)
        break
    ans+=D[nowc][pos]-pos+1
    #print(ans)
    pos=D[nowc][pos]+1
    pos%=lens
else:
    print(ans)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()
p = {}
for i in range(len(s)):
    c = s[i]
    if c not in p:
        p[c] = []
    p[c].append(i)

over = 0
ret = 0
for c in t:
    if c not in p:
        print(-1)
        exit(0)
    ind = bisect.bisect_left(p[c], ret)
    if ind < len(p[c]):
        ret = p[c][ind] + 1
    else:
        ret = p[c][0] + 1
        over += 1

print(over * len(s) + ret)

Submission status: Accepted

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

import bisect
point_dic = {}
for i in range(26):
    alp = chr( ord('a') + i )
    point_dic[alp] = []

for i in range(len_s):
    i_alp = s[i]
    point_dic[i_alp].append(i+1)

now = 1
cycle = 0
for i in t:
    points = point_dic[i]
    if(len(points) == 0):
        print(-1)
        exit()
    tmp = bisect.bisect_left(points, now)
    if(tmp == len(points)):
        now = points[0]+1
        cycle += 1
    else:
        now = points[tmp]+1

ans = cycle * len_s + now - 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
S=list(input())
T=list(input())
A=[[] for i in range(26)]
for i in range(len(S)):
  A[ord(S[i])-97].append(i+1)
a=0
b=0
for i in range(len(T)):
  k=ord(T[i])-97
  if len(A[k])==0:
    print(-1)
    exit()
  if b>=A[k][-1]:
    a=a+1
    b=A[k][0]
    continue
  else:
    b=A[k][bisect.bisect_right(A[k],b,lo=0,hi=len(A[k]))]
print(a*len(S)+b)