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:
from collections import defaultdict
from bisect import bisect_right

def main():
    S = input()
    T = input()
    Ls = len(S)
    Lt = len(T)
    d = defaultdict(list)
    for i in range(Ls):
        d[S[i]].append(i+1)

    now = 0
    ans = 0
    for i in range(Lt):
        if not d[T[i]]:
            print(-1)
            exit()
        ni = bisect_right(d[T[i]], now)
        if ni >= len(d[T[i]]):
            now = 0
            ans += Ls
            ni = bisect_right(d[T[i]], now)
            now = d[T[i]][ni]
        else:
            now = d[T[i]][ni]

    ans += now
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# inputna
s = input()
t = input()

l = [chr(v) for v in range(ord("a"), ord("z")+1)]
d = {c:i for i,c in enumerate(l)}

def snx(s, target=None, reverse=False, loop=False):
    """文字列sの各要素について、cがiより→で最初に現れる位置n[i][c]
    loop=Trueのとき周回した先のインデックスまで求める
    """
    if target is None:
        target = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:None for c in target}
    nx = [[None]*len(target) for _ in range(len(s))]
    if not reverse:
        i = len(s)-1
        for c in reversed(s):
            d[c] = i
            for j,t in enumerate(target):
                nx[i][j] = d[t]
            i -= 1
        if loop:
            for i in range(len(s)):
                for j in range(len(target)):
                    if nx[i][j] is None:
                        nx[i][j] = nx[0][j]
    else:
        i = 0
        for c in s:
            d[c] = i
            for j,t in enumerate(target):
                nx[i][j] = d[t]
            i += 1
        if loop:
            for i in range(len(s)):
                for j in range(len(target)):
                    if nx[i][j] is None:
                        nx[i][j] = nx[-1][j]
    return nx
nx = snx(s, loop=True)
c = -1
ans = 0
for i in range(len(t)):
    nc = nx[(c+1)%len(nx)][d[t[i]]]
    if nc is None:
        ans = -1
        break
    elif nc>c:
        ans += nc-c
    else:
        ans += nc+len(s)-c
    c = nc
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, deque
from bisect import *
alphabets = list("abcdefghijklmnopqrstuvwxyz")
s = input()
t = input()
cs = Counter(list(s))
ct = Counter(list(t))
for char in alphabets:
    if ct[char] > 0 and cs[char]==0:
        print(-1)
        exit()

l_s = len(s)
l_t = len(t)
ss = list(s+s)
c2loc = {char: [] for char in alphabets}
for i in range(l_s*2):
    c2loc[ss[i]].append(i)

ans = 0
now = -1
for i in range(l_t):
    target = t[i]
    target_idxes = c2loc[target]
    idx = bisect_right(target_idxes, now)
    ans += target_idxes[idx] - now
    now = target_idxes[idx]%l_s
print(ans)

Submission status: Accepted

Solution code:
s=input()
t=input()
ls=len(s)
alpha="abcdefghijklmnopqrstuvwxyz"
c={}
l={}
for i in alpha:
  c[i]=[]
  l[i]=0
  
for i in range(ls):
  c[s[i]].append(i)
  l[s[i]]+=1

f=True
x,y=0,-1
for i in t:
  if l[i]==0:
    f=False
    break
  left,right=-1,l[i]
  while right-left!=1:
    a=(left+right)//2
    if c[i][a]>y:
      right=a
    else:
      left=a
  if right==l[i]:
    x+=1
    y=c[i][0]
  else:
    y=c[i][right]
if f:
  print(x*ls+y+1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from math import *
from bisect import *
s=input()
t=input()
n=len(s)
nn=len(t)
ss=[[]for i in range(26)]
tt=[[] for i in range(26)]
ans=0
k=0
for i in range(n):
    ss[ord(s[i])-97].append(i+1)
for i in t:
    j=ss[ord(i)-97]
    if len(j)==0:
        print(-1)
        exit()
    else:
        if j[-1]<=ans:
            ans=j[0]
            k+=1
        else:
            ans=j[bisect(j,ans)]
print(k*n+ans)

Submission status: Accepted

Solution code:
def Binary_Search_Big_Count(A,x,equal=False,sort=False):
    """2分探索によって,xを超える要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    """

    if sort:
        A.sort()

    if A[-1]<x or ((not equal) and A[-1]==x):
        return 0

    L,R=-1,len(A)-1
    while R-L>1:
        C=L+(R-L)//2
        if A[C]>x or (equal and A[C]==x):
            R=C
        else:
            L=C
    return len(A)-R

def Binary_Search_High_Value(A,x,equal=False,sort=False):
    """Aのxを超える要素の中で最小のものを出力する.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    ※全ての要素がx以上(超える)場合はNoneが返される.
    """

    if sort:
        A.sort()

    K=Binary_Search_Big_Count(A,x,equal=equal,sort=False)
    if K:
        return A[-K]
    else:
        return None
#================================================
S=input()
T=input()

N=len(S)

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

D={x:[] for x in set(S)}

for i in range(N):
    D[S[i]].append(i)


X=0
A=-1
for t in T:
    P=Binary_Search_High_Value(D[t],A)

    if P==None:
        X+=1
        A=D[t][0]
    else:
        A=P

print(N*X+A+1)

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect
    
    mod=10**9+7
    s=input()
    t=input()
    
    L=[[]for _ in range(26)]
    
    N=len(s)
    for i in range(N):
        c=ord(s[i])-97
        L[c].append(i)
        
    cur=-1
    rep=0
    
    M=len(t)
    for i in range(M):
        c=ord(t[i])-97
        if len(L[c])==0:
            print(-1)
            exit()
            
        num=bisect.bisect_right(L[c],cur)
        if num>=len(L[c]):
            rep+=1
            num=0
        cur=L[c][num]
        
    ans=N*rep + cur + 1
    print(ans)
        
        
        

main()

Submission status: Accepted

Solution code:
s = input()
t = input()
if set(t) & set(s) == set(t):
    n = -1
    c = 0
    for i in t:
        n = s.find(i, n + 1)
        if n == -1:
            c += 1
            n = s.find(i)
    print(n + len(s) * c + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
def abc138_e():
    s = str(input())
    t = str(input())
    sd = dict()
    for i, c in enumerate(s):
        if sd.get(c) == None: sd[c] = []
        sd[c].append(i)
    from bisect import bisect_left
    k = 0
    p = 0
    for c in t:
        if sd.get(c) == None: return print(-1)
        idx = bisect_left(sd[c], p)
        if idx == len(sd[c]):
            k += 1
            p = 0
            idx = bisect_left(sd[c], p)
        p = sd[c][idx] + 1
    ans = k * len(s) + p
    return print(ans)

if __name__ == '__main__':
    abc138_e()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left


def solve(s, t):
    dd = defaultdict(list)
    for i, c in enumerate(s):
        dd[c].append(i)
    inv = 0
    index = 0
    for c in t:
        x = bisect_left(dd[c], index)
        if x == len(dd[c]):
            inv += 1
            if not dd[c]:
                return -1
            index = dd[c][0] + 1
        else:
            index = dd[c][x] + 1
    return len(s) * inv + index


def main():
    s = input()
    t = input()
    print(solve(s, t))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

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

dict = defaultdict(list)
for i, c in enumerate(S):
    dict[c].append(i + 1)
# print(dict)

# Sの繰り返し数
div_cnt = 0
# 現在のindex
now = 0

for i, c in enumerate(T):

    # cがS中に存在しない場合
    if dict[c] == []:
        print(-1)
        exit()

    next = bisect.bisect_right(dict[c], now)
    # print(c, now, next)

    # nextがdictの右端になる場合
    # 次のsブロックを使う
    if next == len(dict[c]):
        div_cnt += 1
        now = dict[c][0]
    # 現在のsブロックがまだ使える場合
    else:
        now = dict[c][next]

ans = div_cnt * len(S) + now
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

X = [[] for _ in range(26)]
for i, c in enumerate(S):
    # a = 0, b = 1, ..., z = 25
    j = ord(c) - ord('a')
    X[j].append(i + 1)

# print(X)

# Sの繰り返し数
div_cnt = 0
# 現在のindex
now = 0

for c in T:
    # a = 0, b = 1, ..., z = 25
    j = ord(c) - ord('a')

    # Sにない文字がTにある場合
    if len(X[j]) == 0:
        print(-1)
        exit()

    next = bisect.bisect_right(X[j], now)
    # print(c,now,next)

    if next == len(X[j]):
        div_cnt += 1
        now = X[j][0]
    else:
        now = X[j][next]

ans = div_cnt * len(S) + now
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

X = [[] for _ in range(26)]
for i, c in enumerate(S):
    # a = 0, b = 1, ..., z = 25
    j = ord(c) - ord('a')
    X[j].append(i + 1)

q = 0
r = 0

for c in T:
    # a = 0, b = 1, ..., z = 25
    j = ord(c) - ord('a')

    if len(X[j]) == 0:
        print(-1)
        exit()

    idx = bisect.bisect_right(X[j], r)

    if idx == len(X[j]):
        q += 1
        r = X[j][0]
    else:
        r = X[j][idx]

ans = q * len(S) + r
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import copy
import sys
s = input()
n_s = len(s)
t = input()
n_t = len(t)

chr_firstind = defaultdict(lambda:-1)
chr_nextind = defaultdict(lambda:-1)
i_to_chr_nextind = [0] * n_s
for i in range(n_s-1,-1,-1):
    chr_firstind[s[i]] = i
    i_to_chr_nextind[i] = copy.copy(chr_nextind)
    chr_nextind[s[i]] = i 

first_target = t[0]
previous_ind = chr_firstind[first_target]
if previous_ind == -1:
    print(-1)
    sys.exit()
if n_t == 1:
    print(previous_ind+1)
    sys.exit()
s_used = 0
for i in range(1,n_t):
    # 一つ前のtarget_indを使って、次のtargetのs内でのindexを求める
    d = i_to_chr_nextind[previous_ind]
    next_ind = d[t[i]]
    if next_ind == -1:
        s_used += 1
        next_ind = chr_firstind[t[i]]
        if next_ind == -1:
            print(-1)
            sys.exit()
    previous_ind = next_ind
print(n_s*s_used+previous_ind+1)

Submission status: Accepted

Solution code:
import bisect

# d := {"a":[], "b":[], ..., "z":[]}
d = {}
key = list("abcdefghijklmnopqrstuvwxyz")
for i in range(26):
    d[key[i]] = []

# 1文字ずつ分割してリスト化
S = list(input())
N = len(S)

T = list(input())
M = len(T)

for i in range(N):
    d[S[i]].append(i + 1)

# print(d)

S_set = set(S)

ans = 0
now = 0
# Tの1文字目, 2文字目, ...
for i in range(M):
    if T[i] in S_set:
        next = bisect.bisect_right(d[T[i]], now)
        # print("i,next = ", i, next)
        # 右端ではない場合
        if next < len(d[T[i]]):
            now = d[T[i]][next]
        # 右端になる場合
        else:
            now = d[T[i]][0]
            ans += N
    else:
        print(-1)
        exit()

ans += now
print(ans)

Submission status: Accepted

Solution code:
from bisect import*
s=input()
t=input()
n=len(s)
d=dict(zip([chr(i+97) for i in range(26)],[[] for _ in range(26)]))
for i,j in enumerate(s,1):
  d[j]+=[i]
ans=0
cnt=0
for i in t:
  if d[i]:
    j=bisect(d[i],ans)
    if j==len(d[i]):
      cnt+=1
      ans=d[i][0]
    else:ans=d[i][j]
  else:
    cnt,ans=0,-1
    break
print(cnt*n+ans)

Submission status: Accepted

Solution code:
#このプログラムはpypyじゃ通らない
import collections,math
s = input()
t = input()
#tを構成文字で、sにない文字があったらダメ。
#構成できるなら最大でもlen(t)個しかないから、10^100の連結は必要ない

#最も不足する文字を探す
ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0#一番少ないやつ
for t_key,t_val in lt.items():
    if t_key not in ls:#sの中にtの文字がない
        print(-1)
        exit()

#文字をカウントしていく
cnt = 0
tt = list(t[::-1])#指定したい文字へのアクセス時間を1にしたいので反転
idx=0
ss = s#ssは検索文字列
while tt!=[]:#ttが空っぽになったらおしまい
    next_t = tt.pop()#つぎに構成したい文字= next_t
    idx=ss.find(next_t)#検索文字列にnext_tがあるか
    if idx == -1:#ない
        cnt += len(ss)#検索文字列の長さを全部足す
        idx = s.find(next_t)#新たにsを検索文字列として探す
        ss = s[idx+1:]#next_t以降の文字列を次回の検索文字列をセット
        cnt += idx+1 #nex_tが見つかった文字までの長さ
    else:#ある
        cnt += idx+1 #文字長さを足す 
        ss = ss[idx+1:]#次回の検索文字列をセット
print(cnt)

Submission status: Accepted

Solution code:
import collections,math
s = input()
t = input()
#tを構成文字で、sにない文字があったらダメ。
#構成できるなら最大でもlen(t)個しかないから、10^100の連結は必要ない

#最も不足する文字を探す
ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0#一番少ないやつ
for t_key,t_val in lt.items():
    if t_key not in ls:#sの中にtの文字がない
        print(-1)
        exit()

#多分TLEするかも。。
cnt = 0
tt = list(t[::-1])
idx=0
ss = s
while tt!=[]:
    next_t = tt.pop()
    idx=ss.find(next_t)
    if idx == -1:
        cnt += len(ss)
        idx = s.find(next_t)
        ss = s[idx+1:]
        cnt += idx+1
    else:
        cnt += idx+1
        ss = ss[idx+1:]
print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import bisect
def input(): return sys.stdin.readline().rstrip()


def main():
    s = list(input())
    t = list(input())
    dic = defaultdict(list)
    for index, string in enumerate(s):
        dic[string].append(index)
    cycle = 0
    ind = -1
    for string in t:
        if dic[string] == []:
            print(-1)
            exit()
        elif dic[string][-1] <= ind:
            cycle += 1
            ind = dic[string][0]
        else:  # [2,6,7,10] 6の次は？
            ind = dic[string][bisect.bisect_right(
                dic[string], ind)]  # n以下の個数を数える
    print(cycle*len(s)+ind+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
set_ = set()
for i in s:
    set_.add(i)
for i in t:
    if i not in set_:print(-1);exit()
dic = [[0]*26 for _ in range(len(s))]
tmp = [[] for _ in range(26)]
for i in range(len(s)):
    tmp[ord(s[i])-ord('a')].append(i)
import bisect
for i in range(len(s)):
    for nxt in set_:
        idx = bisect.bisect_right(tmp[ord(nxt)-ord('a')],i)

        if idx==len(tmp[ord(nxt)-ord('a')]):
            dic[i][ord(nxt)-ord('a')] = tmp[ord(nxt)-ord('a')][0] + len(s)-i
            # idx = tmp[ord(nxt)-ord('a')][0]+len(s)
        else:
            dic[i][ord(nxt)-ord('a')] = tmp[ord(nxt)-ord('a')][idx]-i
cnt = tmp[ord(t[0])-ord('a')][0]
for i in range(1,len(t)):
    cnt += dic[cnt%len(s)][ord(t[i])-ord('a')]
print(cnt+1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
dic = defaultdict(list)
s = input()
t = input()
n = len(s)
for i in range(n):
    dic[s[i]].append(i+1)

#print(dic)

for i in t:
    if dic[i]==[]:
        print(-1)
        sys.exit()
        
ans = dic[t[0]][0]

if len(t)==1:
    print(ans)
    sys.exit()

count=0
#print(ans)
for i in range(1, len(t)):
    #print("ans:{}, count:{}, n:{}".format(ans, count, n))
    if ans >= dic[t[i]][-1]:
        count += 1
        ans = dic[t[i]][0]
    elif ans < dic[t[i]][0]:
        ans = dic[t[i]][0]
    else:
        sm = 0
        la = len(dic[t[i]])-1
        while sm+1<la:
            mi = (sm + la)//2
            if ans >= dic[t[i]][mi]:
                sm = mi
            else:
                la = mi
        ans = dic[t[i]][la]
#print("ans:{}, count:{}, n:{}".format(ans, count, n))
print(ans+count*n)

Submission status: Accepted

Solution code:
key= list('abcdefghijklmnopqrstuvwxyz')
value=[[] for i in range(26)]
d = dict(zip(key,value))
import bisect    
s = input()
s = list(s)
n = len(s)
ans = 0
for i in range(len(s)):
    d[s[i]].append(i+1)
st = set(s)
t = input()
t = list(t)
b = 0
for i in range(len(t)):
    if t[i] in st:
        p = bisect.bisect(d[t[i]],b) 
        if p < len(d[t[i]]):
            b = d[t[i]][p]
        else:
            b = d[t[i]][0]
            ans += n
    else:
        ans = -1
        break
if ans != -1:
    ans += b
print(ans)

Submission status: Accepted

Solution code:
from string import ascii_lowercase
from bisect import bisect_right, bisect_left


def main():
    s = input()
    t = input()
    len_s = len(s)
    s_all = {s: [] for s in ascii_lowercase}
    for i in range(len_s):
        s_all[s[i]].append(i + 1)
    ans = 0
    if any(s_all[tt] == [] for tt in t):
        ans = -1
    else:
        s_ind = 1
        for ss in ascii_lowercase:
            s_all[ss].sort()
        for i in range(len(t)):
            next_ind = bisect_left(s_all[t[i]], s_ind)
            if next_ind == len(s_all[t[i]]):
                ans += len_s - s_ind + 1
                ans += s_all[t[i]][0]
                s_ind = s_all[t[i]][0] + 1
            else:
                ans += s_all[t[i]][next_ind] - s_ind + 1
                s_ind = s_all[t[i]][next_ind] + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import bisect
from collections import defaultdict

def main():
	s=RD()
	t=RD()
	d=defaultdict(list)

	for i,ss in enumerate(s):
		d[ss].append(i)
	#print(d)

	now=-1
	cnt=0

	for tt in t:
		if d[tt]==[]:
			print(-1)
			exit()
		else:
			i=bisect.bisect_right(d[tt],now)
			if len(d[tt])==i:
				cnt+=1
				now=d[tt][0]
			else:
				now=d[tt][i]
		#print(tt,i,now,cnt)
	print(len(s)*cnt+now+1)

























if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from bisect import bisect_left


def solve():
    S = input()
    T = input()
    if not set(T) <= set(S):
        return -1

    pos = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, c in enumerate(S):
        pos[c].append(i)
    ans = 0
    cur_pos = 0
    for t in T:
        nxt_idx = bisect_left(pos[t], cur_pos)
        if nxt_idx == len(pos[t]):
            ans += len(S)
            cur_pos = 0
            nxt_idx = bisect_left(pos[t], cur_pos)
            cur_pos = pos[t][nxt_idx] + 1
        else:
            cur_pos = pos[t][nxt_idx] + 1

    return ans + cur_pos


print(solve())

Submission status: Accepted

Solution code:
import bisect

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

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

for i in range(len(s)):
    pos[ord(s[i]) - ord('a')].append(i)

ans = 0
now = -1
for i in range(len(t)):
    c = ord(t[i]) - ord('a')
    j = bisect.bisect_right(pos[c], now)

    if j == len(pos[c]):
        print(-1)
        exit()
    now = pos[c][j]

    if now >= n:
        now -= n
        ans += n
print(ans + now + 1)

Submission status: Accepted

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

X = [[] for _ in range(26)]
for i, c in enumerate(s):
    j = ord(c)-ord('a')
    X[j].append(i)

n = len(s)
q = 0
r = -1
import bisect
for c in t:
    j = ord(c)-ord('a')
    if len(X[j]) == 0:
        print(-1)
        exit()
    idx = bisect.bisect_right(X[j], r)
    #print(X[j], idx)
    if idx == len(X[j]):
        q += 1
        r = X[j][0]
    else:
        r = X[j][idx]
    #print(q, r)
ans = q*n + r+1
print(ans)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
u = s
while len(s) <= len(t):
    s += u
p = [[] for k in range(26)]
for k in range(len(s)):
    p[ord(s[k])-97].append(k)
for e in p:
    e.append(10**6)
ans = 0
now = -1
for e in t:
#    print(p[ord(e)-97][bisect.bisect_left(p[ord(e)-97],now)])
    if len(p[ord(e)-97]) == 1:
        print(-1)
        exit(0)
    q = p[ord(e)-97][bisect.bisect_right(p[ord(e)-97],now)]
    if q == 10**6:
        ans += len(s)-now+p[ord(e)-97][0]
        now = p[ord(e)-97][0]
    else:
        ans += q-now
        now = q
print(ans)

Submission status: Accepted

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

from collections import defaultdict

nx = [defaultdict(lambda: -1) for i in range(len(S)+1)]
lastpos = defaultdict(lambda: 0)

SS = S+S
for i,c in enumerate(SS[::-1]):
    i = len(SS)-1-i
    if i < len(S):
        for k,v in lastpos.items():
            nx[i+1][k] = v-i
    lastpos[c] = i
for k,v in lastpos.items():
    nx[0][k] = v+1

ans = 0
for c in T:
    if nx[ans%len(S)][c] == -1:
        print(-1)
        exit()
    ans += nx[ans%len(S)][c]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

s = input()
t = input()

alp_d = {chr(ord('a') + i): [] for i in range(26)}
for i,si in enumerate(s):
    alp_d[si].append(i)

# print(alp_d)

curr_i = -1
loop = 0
for ti in t:
    # print('---',ti)
    if not alp_d[ti]:
        print(-1)
        exit()
    # bより大きい最小要素のindex/value
    ind = bisect_right(alp_d[ti], curr_i)
    ind = ind if 0 <= ind < len(alp_d[ti]) else None
    detected_i = alp_d[ti][ind] if ind is not None else None
    # print(ind)
    if detected_i is not None:
        curr_i = detected_i
    else:
        loop += 1
        curr_i = min(alp_d[ti])

ans = loop*(len(s)) + curr_i+1
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
def alph_to_num(s):
  return ord(s)-ord('a')
def solve():
  ans = 0
  S = input()
  T = input()
  lis = [[] for _ in range(26)]
  for i,s in enumerate(S):
    lis[alph_to_num(s)].append(i)
  ind = -1
  for t in T:
    n = alph_to_num(t)
    if not len(lis[n]):
      return -1
    if ind>=lis[n][-1]:
      ans += len(S)
      ind = lis[n][0]
    else:
      ind = lis[n][bisect_right(lis[n],ind)]
  ans += ind+1
  return ans
print(solve())

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from bisect import bisect_left
from collections import defaultdict
import sys
def main(S, T):
    D = defaultdict(list)
    for i, s in enumerate(S):
        D[s].append(i + 1)
    cycle = 0
    idx = 0
    N = len(S)
    for t in T:
        if not D[t]:
            return -1
        i = bisect_left(D[t], idx + 1)
        if i >= len(D[t]):
            cycle += 1
            idx = D[t][0]
        else:
            idx = D[t][i]
    return cycle * N + idx

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    t = input().rstrip()
    ans = main(s, t)
    print(ans)

Submission status: Accepted

Solution code:
from bisect import *
S=input()
T=input()
N=len(S)
M=len(T)
O=ord('a')
X=[[0]*26 for i in range(N+1)]
Y=[[] for i in range(26)]
for i in range(N):
  Y[ord(S[i])-O].append(i)
for i in range(N):
  Y[ord(S[i])-O].append(N+i)
for i in range(M):
  if len(Y[ord(T[i])-O])==0:
    print(-1)
    exit()
for i in range(-1,N):
  for j in range(26):
    if len(Y[j]):
      X[i][j]=Y[j][bisect_right(Y[j],i)]
P=0
Z=-1
for i in range(M):
  P+=X[Z][ord(T[i])-O]-Z
  Z=X[Z][ord(T[i])-O]
  if Z>=N:
    Z-=N
print(P)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict
from bisect import bisect_left
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    s = input()
    t = input()
    # 各アルファベットについてsの何文字目に現れたかを保持するリストの辞書
    alphabets = defaultdict(list)
    for i,c in enumerate(s):
        alphabets[c].append(i)
    # sの繰り返した数,周期,0-indexed
    period = 0
    # sの何文字目までを使ったか
    looking = -1
    # 各アルファベットをその周期で何回使ったかを保持する辞書
    alphabet_index = defaultdict(int)
    for i,c in enumerate(t):
        index = bisect_left(alphabets[c],looking+1, alphabet_index[c])
        # その周期で使えるアルファベットがない場合
        if index == len(alphabets[c]):
            # そのアルファベットが存在しない場合は解なし
            if len(alphabets[c]) == 0:
                print(-1)
                return
            
            # 次の周期に移る
            period += 1
            alphabet_index = defaultdict(int)
            looking = alphabets[c][0]

        else:
            looking = alphabets[c][index]

        alphabet_index[c] += 1
    print(period * len(s) + looking + 1)






    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import bisect_right

s = input()
N = len(s)
si = [[] for _ in range(26)]
for i in range(N):
    si[ord(s[i])-ord('a')].append(i+1)

ans = 0
t = input()
M = len(t)
for j in range(M):
    ti = si[ord(t[j])-ord('a')]
    if len(ti)==0:
        print(-1)
        exit()
    d = bisect_right(ti,ans%N)
    if d == len(ti):
        ans += ti[0]+N-ans%N
    else:
        ans += ti[d]-ans%N
print(ans)

Submission status: Accepted

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

alpha2num = lambda c: ord(c) - ord('a')

S2 = [[] for i in range(26)]
for i in range(len(s)):
  S2[alpha2num(s[i])].append(i)
  
#print(S2)
time = 0
place = -1
for i in range(len(t)):
  now = alpha2num(t[i])
  if S2[now] == []:
    print(-1)
    quit()
  else:
    index = bisect.bisect_left(S2[now], place)
    #if index == place:
    #  index += 1
    #print(index, S2[now])  

    
    if index == len(S2[now]):
      place = S2[now][0]
      time += 1
    else:  
      if S2[now][index] == place:
        index += 1
        if index == len(S2[now]):
          place = S2[now][0]
          time += 1
        else:
          place = S2[now][index]
      else:  
        place = S2[now][index]
  #print(place, time)  
    
    
ans = len(s) * time + place + 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

s,t = input(),input()
n,nx,r = len(s),{},0

for i,c in enumerate(s+s):
	if nx.get(c) is None:
		nx[c] = []
	nx[c].append(i+1)

for c in t:
	l = nx.get(c)
	if l is None:
		print(-1)
		exit()
	r += l[bisect.bisect(l,r%n)]-r%n
print(r)

Submission status: Accepted

Solution code:
from bisect import bisect

s,t = input(),input()
n,x,nx,r = len(s),s+s,{},0

for i,c in enumerate(x):
	if nx.get(c) is None:
		nx[c] = []
	nx[c].append(i+1)

for c in t:
	l = nx.get(c)
	if l is None:
		print(-1)
		exit()
	r += l[bisect(l,r%n)]-r%n
print(r)

Submission status: Accepted

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

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

prev = 10**10
cycle = 0
for i,c in enumerate(t):
  if c not in counter:
    print(-1)
    exit()

  idx = counter[c]
  found = bisect.bisect_right(idx, prev)

  if found >= len(idx):
    cycle += 1
    prev = idx[0]
  else:
    prev = idx[found]

print( (cycle-1)*len(s) + prev+1 )

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
s=list(input())
n=len(s)
t=input()
m=len(t)
dic={}
ans=0
for i in range(len(s)):
    if s[i] not in dic:
        dic[s[i]]=[i]
    else:
        dic[s[i]].append(i)
b=-1
for i in range(m):
    if t[i] not in dic:
        print(-1)
        exit()
    res=dic[t[i]]
    if res[-1]<=b:
        ans+=res[0]+1+(n-b-1)
        b=res[0]
    else:
        idx=bisect.bisect_right(res,b)
        ans+=res[idx]-b
        b=res[idx]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

f = defaultdict(list)
d = {}


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

len_s = len(s)

for i in range(len_s):
    f[s[i]].append(i)

next_char = [[0] * len_s for _ in range(len(f))]

j = 0
for k, v in f.items():
    d[k] = j
    l = 0
    for i in range(len_s):
        if v[l] == i:
            l += 1
            if l == len(v):
                l = 0
        next_char[j][i] = v[l]
    j += 1

m = 0

for i in range(len(t)):
    x = t[i]
    if i == 0 and t[i] == s[i]:
        continue 
    if d.get(x) == None:
        m = -2
        break
    else:
        j = d[x]
        r = m % len_s
        n = next_char[j][r]
        if r >= n:
            m += len_s - (r-n)
        else:
            m += n - r

print(m+1)

Submission status: Accepted

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

position = [[] for i in range(26)]
for i, ss in enumerate(s):
    pos = ord(ss)-ord("a")
    position[pos].append(i)

for tt in set(t):
    if not position[ord(tt)-ord("a")]:
        print(-1)
        exit(0)

count = 0
idx = -1
for tt in t:
    t_i = ord(tt)-ord("a")
    pos = bisect_right(position[t_i], idx)
    if pos == len(position[t_i]):
        idx = position[t_i][0]
        count += 1
    else:
        idx = position[t_i][pos]

print(count*n+idx+1)

Submission status: Accepted

Solution code:
from bisect import bisect
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
alp = []

for i in range(26):
  array = []
  now = chr(ord('a') + i)
  for j in range(lenS):
    if s[j] == now:
      array.append(j+1)
  alp.append(array)

count,now = 0,0

for i in range(lenT):
  j = ord(t[i])-ord('a')
  if alp[j]:
    next = bisect(alp[j],now)
    if next == len(alp[j]):
      count += 1
      now = alp[j][0]
    else:
      now = alp[j][next]
  else:
    print(-1)
    exit()

ans = count*lenS+now

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
alp = []

for i in range(26):
  array = []
  now = chr(ord('a') + i)
  for j in range(lenS):
    if s[j] == now:
      array.append(j)
  alp.append(array)

count,now = 0,-1

for i in range(lenT):
  j = ord(t[i])-ord('a')
  if alp[j]:
    next = bisect(alp[j],now)
    if next == len(alp[j]):
      count += 1
      now = alp[j][0]
    else:
      now = alp[j][next]
  else:
    print(-1)
    exit()

ans = count*lenS+now+1

print(ans)