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

S = input()
dS = defaultdict(list)
T = input()
for i in range(len(S)):
    dS[S[i]].append(i+1)
if not dS[T[0]]:
    print(-1)
    exit()
now = min(dS[T[0]])
ans = now
for i in range(1, len(T)):
    t = T[i]
    if not dS[t]:
        print(-1)
        exit()
    b = bisect_right(dS[t], now)
    if b == len(dS[t]):
        ans += len(S) - now
        now = min(dS[t])
        ans += now
    else:
        ans += dS[t][b] - now
        now = dS[t][b]
print(ans)

Submission status: Accepted

Solution code:
import collections
import bisect

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

    ns, nt = len(s), len(t)
    cs, ct = set(list(s)), set(list(t))
    for c in ct:
        if c not in cs: return -1

    # def unittest(s, t):
    #     i = 0
    #     for c in t:
    #         while s[i % ns] != c:
    #             i += 1
    #         i += 1
    #     return i

    d = collections.defaultdict(list)
    for i in range(ns):
        if s[i] in ct: d[s[i]].append(i)
    # print(s, t)
    i = 0
    for c in t:
        # binary search
        j = i % ns
        k = bisect.bisect_left(d[c], j)
        if k == len(d[c]):
            i = (i // ns + 1)*ns + d[c][0]
        else:
            if j <= d[c][k]:
                i = (i // ns)*ns + d[c][k]
            else:
                i = (i // ns + 1)*ns + d[c][k]
        # print(i)
        i += 1
    return i
    # return i, unittest(s, t)


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

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys

input = sys.stdin.readline

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

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

string_count = 0
cur = -1
for tt in t:
    cur += 1
    idx = ord(tt) - base
    pos_lst = d[idx]
    lst_len = len(pos_lst)

    if not lst_len:
        print(-1)
        exit()
    pos = bisect_left(pos_lst, cur)  # cur以降で文字ttが見つかる位置
    if lst_len == pos:
        string_count += 1
        cur = pos_lst[0]
    else:
        cur = pos_lst[pos]

    # print(cur, pos_lst, lst_len, string_count * n)

print(string_count * n + cur + 1)

Submission status: Accepted

Solution code:
import bisect
import sys

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

az_pos = [[] for i in range(ord("z") - ord("a") + 1)]
for i, si in enumerate(s):
    az_pos[ord(si) - ord("a")].append(i)

ans = 0

past = 0
for ti in t:
    char = ord(ti) - ord("a")
    if len(az_pos[char]) == 0:
        print(-1)
        sys.exit()

    r = bisect.bisect_left(az_pos[char], past)
    if r >= len(az_pos[char]):
        ans += n
        r = bisect.bisect_left(az_pos[char], 0)
    past = az_pos[char][r] + 1

print(ans + past)

Submission status: Accepted

Solution code:
from bisect import bisect_left
a=input()
b=input()
c=[[]for i in range(26)]
for i in range(len(a)):
  c[ord(a[i])-97].append(i)

m=-1
ans=0
roop=0
for i in range(len(b)):
  s=ord(b[i])-97
  if c[s]==[]:
    print(-1)
    exit()
  else:
    p=bisect_left(c[s],m+1)
    if p<len(c[s]):
      m=c[s][p]
    else:
      roop+=1
      m=c[s][0]
print(roop*len(a)+m+1)

Submission status: Accepted

Solution code:
# ABC138E - Strings of Impurity
from bisect import bisect_left as bs
from collections import defaultdict


def main():
    S = input()
    T = input()
    # idx[c] := indices at which character c appears in S
    idx, ls = defaultdict(list), len(S)
    for i, s in enumerate(S):
        idx[s] += [i]
    roop, cur = 0, -1
    for t in T:  # binary search to find t's index > cur
        tgt = idx[t]  # sorted list of indices of t
        if tgt == []:  # t not in S
            print(-1)
            return
        x = bs(tgt, cur + 1)
        if x < len(tgt):  # find in current roop
            cur = tgt[x]
        else:  # move to next roop and pick up the first one
            cur = tgt[0]
            roop += 1
    print(roop * ls + cur + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC138E - Strings of Impurity
import sys
input = sys.stdin.readline

from bisect import bisect_left as bs
from collections import defaultdict


def main():
    S = input().rstrip()
    T = input().rstrip()
    # idx[c] := indices at which character c appears in S
    idx, ls = defaultdict(list), len(S)
    for i, s in enumerate(S):
        idx[s] += [i]
    roop, cur = 0, -1
    for t in T:  # binary search to find t's index > cur
        tgt = idx[t]  # sorted list of indices of t
        if tgt == []:  # t not in S
            print(-1)
            return
        x = bs(tgt, cur + 1)
        if x < len(tgt):  # find in current roop
            cur = tgt[x]
        else:  # move to next roop and pick up the first one
            cur = tgt[0]
            roop += 1
    print(roop * ls + cur + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

s_dict = {}
for i, si in enumerate(s):
    if si not in s_dict:
        s_dict[si] = [i]
    else:
        s_dict[si].append(i)

# print(s_dict)

s_len = len(s)
counter = 0
fail = False
for ti in t:
    if ti not in s_dict:
        fail = True
        break
    # counter in s
    c_in_s = counter % s_len
    c = bisect.bisect_left(s_dict[ti], c_in_s)
    if c == len(s_dict[ti]):
        counter += s_len - c_in_s
        counter += s_dict[ti][0]
        counter += 1
    else:
        counter += s_dict[ti][c] - c_in_s
        counter += 1

print(counter if not fail else '-1')

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


s = list(input())

t = list(input())
flag = -1
on = [[-1 for j in range(len(s))] for i in range(26)]

al = [-1 for i in range(26)]
alll = [0 for i in range(26)]
for i in range(len(s)):
    k = ord(s[i]) - 97
    on[k][i] = i
    if al[k] == -1:
        al[k] = i

for i in range(26):
    for j in range(len(s)-2,-1,-1):
        if on[i][j+1] != -1 and on[i][j] == -1:
            on[i][j] = on[i][j+1]
co = 0
ppp = 0
t = cl.deque(t)
while t:
    k = t.popleft()
    kkk = al[ord(k)-97]
    ppp = kkk+1
    if kkk == -1:
        print(kkk)
        exit()
    while t:
        kt = t.popleft()
        if k == kt:
            if kkk == len(s)-1:
                t.appendleft(kt)
                break
            else:
                kk = on[ord(kt)-97][kkk+1] 
                if kkk >= kk:
                    t.appendleft(kt)
                    break
                else:
                    ppp = kk+1
                    kkk = kk
                    k = kt
        else:
            kk = on[ord(kt)-97][kkk]
            if kkk >= kk:
                t.appendleft(kt)
                break
            else:
                ppp = kk+1
                kkk = kk
                k = kt
    if len(t) != 0:
        co += 1

print(len(s)*co + ppp)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

lst = [[] for _ in range(30)]
ch = 'abcdefghijklmnopqrstuvwxyz'
for k, i in enumerate(s+s):
    lst[ch.find(i)].append(k)

len_s = len(s)

count = 0
index = -1
for i in t:
    if lst[ch.find(i)] == []:
        print(-1)
        break
    next_index = lst[ch.find(i)][bisect.bisect_right(lst[ch.find(i)], index)]
    count += next_index - index
    if next_index >= len_s:
        next_index -= len_s
    index = next_index
else:
    print(count)

Submission status: Accepted

Solution code:
import bisect
s=input()
t=input()
jisho={}
alphabets = [chr(ord('a') + i) for i in range(26)]
for moji in alphabets:
    jisho[moji] = [i for i,x in enumerate(s) if x==moji]
lis = [jisho[moji] for moji in t]

if [] in lis:
    print(-1)
else:    
    old=-1
    count=0
    for cand in lis:
        z=bisect.bisect(cand,old)
        if z==len(cand):
            num=min(cand)
        else:
            num=cand[z]
#         tes = [temp for temp in cand if temp>old]
#         if len(tes)==0:
#             num = min(cand)
#         else:
#             num = min(tes)
        if num<=old: count+=1
        old=num
    print(count*len(s)+old+1)

Submission status: Accepted

Solution code:
s=input()
t=input()
import bisect
res=0
if len(set(t)-set(s)) > 0:
    res=-1
else:
    pos={}
    set_t=set(t)
    for e_t in t:
        pos[e_t]=[]
    for i in range(len(s)):
        if s[i] in set_t:
            pos[s[i]].append(i+1)
    cur = 0
    nxt=0
    for e_t in t:
        nxt=bisect.bisect_left(pos[e_t], cur+1)
        if nxt < len(pos[e_t]):
            cur=pos[e_t][nxt]
        else:
            cur=pos[e_t][0]
            res+=len(s)
    res+=cur
print(res)

Submission status: Accepted

Solution code:
from bisect import bisect
import sys
s = input()
t = input()
l = {}
for c in set(t):
    cl = [s.find(c)]
    if cl[0] == -1:
        print("-1")
        sys.exit()
    while True:
        i = s.find(c, cl[-1] + 1)
        if (i == -1):
            break
        cl.append(i)
    l[c] = cl
ofs = -1
count = 0
for c in t:
    lens = len(s)
    ref = bisect(l[c], ofs)
    if ref < len(l[c]):
        ofs = l[c][ref]
    else:
        ofs = l[c][0]
        count += 1
print(lens * count + ofs + 1)

Submission status: Accepted

Solution code:
# ABC138E - Strings of Impurity
from bisect import bisect_left as bs
from collections import defaultdict


def main():
    S, T = tuple(input() for _ in range(2))
    idx, ls = defaultdict(list), len(S)
    for i, s in enumerate(S):
        idx[s] += [i]
    roop, cur = 0, -1
    for t in T:
        tgt = idx[t]
        if tgt == []:  # t not in S
            print(-1)
            return
        x = bs(tgt, cur + 1)
        if x < len(tgt):
            cur = tgt[x]
        else:
            cur = tgt[0]
            roop += 1
    print(roop * ls + cur + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections, bisect

s = input()
t = input()

n = len(s)
d = collections.defaultdict(list)
for i, c in enumerate(s):
    d[c].append(i + 1)

m = len(t)
x = [0] * (m + 1) # 長さを記録
y = [0] * (m + 1) # 添え字を記録

for i in range(1, m + 1):
    c = t[i - 1]
    if not c in d:
        print(-1)
        exit()
    
    a = y[i - 1]
    ptr = bisect.bisect_right(d[c], y[i - 1])
    if ptr == len(d[c]):
        b = d[c][0]
    else:
        b = d[c][ptr]
    
    y[i] = b
    if a < b:
        x[i] = x[i - 1] + b - a
    else:
        x[i] = x[i - 1] + n - a + b
    
print(x[-1])

Submission status: Accepted

Solution code:
# ABC138E - Strings of Impurity
from bisect import bisect_left as bs
from collections import defaultdict


def main():
    S, T = tuple(input() for _ in range(2))
    if not set(T) <= set(S):  # corner case
        print(-1)
        return
    idx, ls = defaultdict(list), len(S)
    for i, s in enumerate(S):
        idx[s] += [i]
    cur = -1
    for t in T:
        tgt = idx[t]
        x = (cur + 1) % ls
        i = bs(tgt, x)
        if i < len(tgt):
            cur += 1 + tgt[i] - x
        else:
            cur += 1 + tgt[0] - x + ls
    print(cur + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def solve(positions, s, t):

    if not set(t) <= set(s):
        return -1

    loop = 0
    prev = -1

    for tchar in t:
        candidates = positions[tchar]
        pos = bisect.bisect_right(candidates, prev)

        if pos == len(candidates):
            loop += 1
            pos = 0
        prev = candidates[pos]

    return loop * len(s) + prev + 1


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

    positions = defaultdict(list)
    for i in range(len(s)):
        positions[s[i]].append(i)

    print(solve(positions, s, t))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import *


def p_e():
    s = input()
    t = input()
    l = defaultdict(list)

    for i, c in enumerate(list(s)):
        l[c].append(i + 1)

    for c in list(t):
        if c not in l.keys():
            print(-1)
            exit()

    N = 0
    current = -1
    for c in list(t):
        R = l[c]

        x = bisect(R, current)

        if len(R) == x:
            N += 1
            current = R[0]
        else:
            current = R[x]

    print(N * len(s) + current)


if __name__ == '__main__':
    p_e()

Submission status: Accepted

Solution code:
import bisect
import sys

sys.setrecursionlimit(1000000)

s=input()
t=input()
dic={}
for v in s:
    dic[v]=True

for u in t:
    if not u in dic:
        print(-1)
        exit()

nex={}
for i, v in enumerate(s+s):
    if not v in nex:
        nex[v]=[i]
    else:
        nex[v].append(i)
#print(s)
#print(t)
#print(nex)
sl=len(s)
tl=len(t)
def func(st, tn, su):
    if tn == tl:
        return su
    #print(st, tn, su, t[tn])
    ind=bisect.bisect_left(nex[t[tn]] ,st+1)
    nm=(nex[t[tn]][ind]-st)
    return func((st+nm)%sl, tn+1, su+nm)


res=func(-1, 0, 0)

print(res)

Submission status: Accepted

Solution code:
import bisect
import re

s = input()
t = input()
sett = set(t)
sets = set(s)
for e in sett:
  if e not in sets:
    print(-1)
    exit()

sumidx = 0
tmps = s
#tの各文字についてs内での出現場所をリストアップする
s_dict = {}
count = 1
for e in sett:
  s_dict[e] = [m.start() for m in re.finditer(e, s)]
idx = 0
for e in t:
  l = s_dict[e]
  idx = bisect.bisect_left(l, idx)
  #print(idx)
  if idx == len(l):
    count += 1
    if count > 10 ** 100:
      print(-1)
      exit()
    sumidx += len(s)
    idx = l[0]+1
  else:
    #print(l[idx])
    idx = l[idx]+1
sumidx += idx
print(sumidx)

Submission status: Accepted

Solution code:
import bisect

def main():
    s = input()
    t = input()
    s_set = set(list(s))
    s_dict = {}
    s_len = len(s)
    t_list = list(t)
    t_set = set(t_list)
    c = -1
    ans = []
    ans_append = ans.append
    for i in s_set:
        s_dict[i] = []
    for i in range(s_len):
        s_dict[s[i]].append(i)
    if len(t_set) == len(t_set & s_set):
        for i in t_list:
            idxs = s_dict[i]
            if idxs[-1] <= c:
                c = idxs[0]
                ans_append(c)
            else:
                c = idxs[bisect.bisect(idxs,c)]
                ans_append(c)
        count = 0
        for i in range(len(ans)-1):
            if ans[i] >= ans[i+1]:
                count += 1
        print(s_len*count + ans[-1] + 1)
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    T = str(input().strip())

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

    n = len(S)
    d = defaultdict(list)
    for i, s in enumerate(S, start=1):
        d[s].append(i)

    cnt = 0
    pos = 0
    for t in T:
        if pos >= d[t][-1]:
            cnt += 1
            pos = d[t][0]
        else:
            left = 0
            right = len(d[t])
            while left < right:
                mid = (left + right) // 2
                np = d[t][mid]
                if np <= pos:
                    left = mid + 1
                else:
                    right = mid
            pos = d[t][left]

    return n * cnt + pos


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

Submission status: Accepted

Solution code:
import bisect

GG = [[] for i in range(26)]
L = [chr(i) for i in range(97, 123)]

s = input()
t = input()

N = len(s)
M = len(t)

for i in range(N):
	x = ord(s[i]) - 97
	GG[x].append(i)

for i in range(26):
	GG[i] = sorted(GG[i])


jud = [0] * 26
for i in range(26):
	if GG[i] != []:
		jud[i] = 1
j = "Y"
for i in range(M):
	if jud[ord(t[i]) - 97] == 0:
		j = "N"
		break

if j == "N":
	print(-1)
else:
	v = -1
	ans = 0
	for i in range(M):
		x = ord(t[i]) - 97
		y = bisect.bisect_right(GG[x], v)

		if y == len(GG[x]):
			z = GG[x][0]
		else:
			z = GG[x][y]
		if z <= v:
			ans += N
		v = z


	print(ans + v + 1)

Submission status: Accepted

Solution code:
s=input()
t=input()
leng=len(s)
lent=len(t)
count=0
tmp=0
i=0
while True:
   ans=s[tmp:].find(t[i])
   if ans!=-1:
       i += 1
       tmp += ans+1
       if i ==lent:
           count += tmp
           break
       continue
   if tmp==0:
       count=-1
       break
   tmp=0
   count+=leng
if count>leng*10**100:
    count=-1
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

#s上で各アルファベットがどの位置にあるか
pos_in_s = {}
for i in range(len(s)):
  c = s[i]
  if c not in pos_in_s:
    pos_in_s[c] = []
  pos_in_s[c].append(i)

#t上でどの文字が何回使われているか
pos = -1
rep = 0
#count_on_t = {}
for c in t:
  #文字がなければ終わり
  if c not in pos_in_s:
    pos = -1
    break
    
  #bin search
  right = bisect_right(pos_in_s[c], pos)
  if right == len(pos_in_s[c]):
    pos = pos_in_s[c][0]
    rep += 1
  else:
    pos = pos_in_s[c][right]
    
#print(rep, pos, rep * len(s) + pos + 1)
if pos == -1:
   print(-1)
else:
  print(rep * len(s) + pos + 1)

Submission status: Accepted

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

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

repeat = 0
focus = 0
ans = 0
for i in range(len(t)):
    c = t[i]
    if c not in dic:
        ans = -1
        break
    if dic[c][-1] < focus:
        repeat += 1
        focus = dic[c][0]+1
    else:
        l = 0
        r = len(dic[c])
        while l < r:
            mid = (r+l)//2
            if(dic[c][mid] < focus):
                l = mid + 1
            else:
                r = mid
        focus = dic[c][l]+1
print(ans if ans == -1 else repeat*len(s)+focus)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
N = len(s)

next_map = sorted(zip(s*2,range(N*2)))
br = bisect.bisect_right
ans = 0
i = -1
for c in t:
    map_idx = br(next_map,(c,i))
    if map_idx == N*2:
        ans = -1
        break
    a,j = next_map[map_idx]
    if a != c :
        ans = -1
        break
    ans += j - i
    i = j%N
print(ans)

Submission status: Accepted

Solution code:
s=input()
t=input()
n=0
c=0
for e in t:
    try:
        i=s[c:].index(e)
        n+=i+1
        c=(c+i+1)%len(s)
    except ValueError:
        try:
            i=s.index(e)
            n+=len(s)-c+i+1
            c=i+1
        except ValueError:
            n=-1
            break
print(n)

Submission status: Accepted

Solution code:
import sys

ordA = ord('a')

ss = input()
ts = input()

lenS, lenT = len(ss), len(ts)

setS = set(ss)
for t in ts:
    if t not in setS:
        print(-1)
        sys.exit()

poss = [-1] * 26
for i, s in enumerate(ss):
    ch = ord(s)-ordA
    if poss[ch] == -1:
        poss[ch] = i + lenS

nextss = [[0]*(26) for _ in range(lenS)]
for i in reversed(range(lenS)):
    ch = ord(ss[i])-ordA
    poss[ch] = i
    for ch, pos in enumerate(poss):
        nextss[i][ch] = pos-i

i = 0
ans = 1
for t in ts:
    ch = ord(t)-ordA
    d = nextss[i][ch]
    ans += d+1
    i = (i+d+1) % lenS

print(ans-1)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
lens=len(s)
lent=len(t)
d = {}
s2=s+s
lens2=len(s2)

for i in range(lens2):
    if s2[i] in d:
        d[s2[i]].append(i)
    else:
        d[s2[i]] = [i]

tmp=0
r=0
snum=0
for i in range(lent):
    if(lens<tmp):
        snum+=lens
        tmp-=lens
        
    if d.get(t[i],None)==None:
        print("-1")
        exit()
    else:
        lis=d[t[i]]
        r = bisect.bisect_left(lis,tmp)
        tmp=lis[r]+1
print(snum+tmp)

Submission status: Accepted

Solution code:
import string
import bisect

S, T = input(), input()
lS, lT = len(S), len(T)

l = {s: [] for s in string.ascii_lowercase}
for i in range(lS):
    l[S[i]].append(i)

id, ans = -1, 0
for i in range(lT):
    if len(l[T[i]]) == 0:
        print(-1)
        exit()

    tmp = l[T[i]][(bisect.bisect(l[T[i]], id)) % len(l[T[i]])]
    if id >= tmp:
        ans += lS
    id = tmp

print(ans + id + 1)

Submission status: Accepted

Solution code:
from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)

Submission status: Accepted

Solution code:
from bisect import bisect
s = input()
t = input()
def ctoi(c):
	return ord(c) - ord("a")
if not (set(s) >= set(t)):
	print(-1)
else:
	alph = [[] for _ in range(26)]
	for i in range(len(s)):
		alph[ctoi(s[i])].append(i)
	for a in alph:
		if a:
			a.append(a[0] + len(s))
	cur = len(s)-1
	ans = 0
	for i in range(len(t)):
		ind = bisect(alph[ctoi(t[i])], cur)
		ans += alph[ctoi(t[i])][ind] - cur
		cur = alph[ctoi(t[i])][ind] % len(s)
	print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from bisect import bisect_left as bl
s = input()
t = input()
ind = dd(list)
res = 0
first = 1
for i in range(len(s)):
  ind[s[i]].append(i)
#print(ind)
for i in range(len(t)):
  if len(ind[t[i]]) == 0:
    print(-1)
    exit(0)
  temp = bl(ind[t[i]], res % len(s))
  #print(temp, res, t[i])
  if first == 0:
    if res % len(s) == ind[t[i]][min(temp, len(ind[t[i]]) - 1)]:
      temp += 1
  first = 0
  if temp == len(ind[t[i]]):
    res += (len(s) - res % len(s)) + ind[t[i]][0]
  else:
    res += ind[t[i]][temp] - res % len(s)
print(res + 1)

Submission status: Accepted

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

if __name__ == "__main__":
    n = len(S)
    ans = 0
    pre = -1 
    for c in T: 
        pos = S.find(c, pre + 1, n)
        if pos != -1:
            ans += (pos - pre)
            pre = pos 
        else:
            pos = S.find(c, 0, pre + 1)
            if pos != -1:
                ans += n + pos - pre
                pre = pos  
            else:
                ans = -1
                break
    
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
import bisect
sys.setrecursionlimit(10000000)

def main():
    s = input()
    t = input()
    alphabets = dict.fromkeys(list("abcdefghijklmnopqrstuvwxyz"), None)
    # alphabets = alphabet.copy()
    for key_ in alphabets:
        lists = []
        for i in range(len(s)):
            if key_ == s[i]:
                lists.append(i)
        alphabets[key_] = lists
    now = -1
    count = 0
    for alpha in t:
        if len(alphabets[alpha]) == 0:
            print(-1)
            sys.exit()
        else:
            lists = alphabets[alpha]
            index = bisect.bisect_right(lists, now)
            if index >= len(lists):
                now = -1
                count += len(s)
                now = lists[0]
            else:
                now = lists[index]
            # print(now, count)
    print(count + now + 1)
            







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
S=input()
T=input()
N=len(S)
M=len(T)
chardict=dict()
for i in range(26):
    chardict[chr(i+97)]=[]
for i in range(2*N):
    chardict[S[i%N]].append(i)
dp=[0 for i in range(M+1)]
dp[0]=-1
for i in range(M):
    nowpoint=dp[i]%N
    cycle=dp[i]//N
    #cycle 周していて　nowpoint番目にいる
    if len(chardict[T[i]])==0:
        print(-1)
        exit()
    tmp=bisect.bisect_right(chardict[T[i]],nowpoint)
    dp[i+1]=cycle*N+chardict[T[i]][tmp]
print(dp[M]+1)

Submission status: Accepted

Solution code:
import bisect

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

s_dic = {}
for i,s in enumerate(S):
    if s not in s_dic.keys():
        s_dic[s] = [i]
    else:
        s_dic[s].append(i)

def main():
    pre, n_repeat = -1, 0
    cur = -1
    for t in T:
        if t not in s_dic.keys():
            return -1
        i = bisect.bisect_right(s_dic[t], cur)
        if i >= len(s_dic[t]):
            cur = s_dic[t][0]
            n_repeat += 1
        else:
            cur = s_dic[t][i]
            if cur <= pre:
                n_repeat += 1
        pre = cur
            
    return n_repeat * len(S) + cur + 1

print(main())

Submission status: Accepted

Solution code:
import sys
def SI(): return sys.stdin.readline().strip()

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

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

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        # とり切っていない場合
        posidx = bisect.bisect_right(poslist, currentidx)

        if posidx >= len(poslist):
            # とれないなら次のループでとったことにする
            i_loop += 1
            currentidx = poslist[0]
        else:
            # 同じループでとれるなら取って、現在位置を更新
            pos = poslist[posidx]
            currentidx = pos

    print(len(s)*i_loop + currentidx + 1)

main()

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()
s_length = len(s)
t_length = len(t)

def char2int(char):
    return ord(char) - 97

def search_index(t_atom, last_index, d_list):
    t_atom_int = char2int(t_atom)
    d = d_list[t_atom_int]

    if d == []:
        return -1

    c = bisect.bisect_right(d, last_index)

    if c != len(d):
        return d[c]
    else:
        return d[0]

def solve():
    last_index = -1
    t_index = []
    loop_cost = 1

    d = [[] for _ in range(26)]
    for i in range(s_length):
        char = s[i]
        d[char2int(char)].append(i)

    for i in range(t_length):
        t_atom = t[i]
        t_atom_index = search_index(t_atom, last_index, d)
        if t_atom_index == -1:
            return -1
        else:
            t_index.append(t_atom_index)
            last_index = t_atom_index

    remainder_cost = t_index[-1] + 1

    for i in range(1, t_length):
        if t_index[i - 1] >= t_index[i]:
            loop_cost += 1

    return s_length * (loop_cost - 1) + remainder_cost

print(solve())

Submission status: Accepted

Solution code:
s = input()
t = input()
r = 0
p = 0
x = 0
for i in t:
    if s.find(i) == -1:
        print(-1)
        exit()
    if p > s.find(i):
        if s[p:].find(i) == -1:
            x += 1
            p = s.find(i) + 1
        else:
            p = p + s[p:].find(i) + 1
    else:
        p = s.find(i) + 1
print(x * len(s) + p)

Submission status: Accepted

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

length = len(S)

ans = 0
pre = -1

for t in T:
    x = S.find(t, pre+1, length)
    if x != -1:
        ans += x - pre
        pre = x
    else:
        x = S.find(t, 0, pre+1)
        if x != -1:
            ans += length + x - pre
            pre = x
        else:
            ans = -1
            break

print(ans)

Submission status: Accepted

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

from bisect import bisect_left

s = input()
t = input()

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

s_dict = {}
for i in range(len(s)):
    c = s[i]
    if c not in s_dict.keys():
        s_dict[c] = [i]
    else:
        s_dict[c].append(i)

repeat = 0
s_idx = 0
for c in t:
    idx = bisect_left(s_dict[c], s_idx)
    if idx == len(s_dict[c]):
        s_idx = s_dict[c][0] + 1
        repeat += 1
    else:
        s_idx = s_dict[c][idx] + 1
else:
    ans = repeat * len(s) + s_idx

print(ans)

Submission status: Accepted

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

flag = 0
count = 0
rest_s = s
n = len(s)

for w in t:
  if w not in s:
    flag = 1
    print(-1)
    break

if flag == 0:
  for w in t:
    index = rest_s.find(w)
    #print(index)
    if (index != -1):
      if (rest_s != s):
        count += (index+1)
      else:
        count += (index)
      rest_s = s[count%n+1:]
    else:
      index = s.find(w)
      count = (count // n + 1) * n + index
      rest_s = s[count%n+1:]
    #print(index, count)
  print(count+1)

Submission status: Accepted

Solution code:
# ABC138E - Strings of Impurity
def main():
    S, T = tuple(input() for _ in range(2))
    if not set(T) <= set(S):  # corner case
        print(-1)
        return
    ans, cur, idx, lim = 1, 0, -1, len(T)
    while cur < lim:
        find = S[idx + 1:].find(T[cur])
        if find == -1:
            ans += 1
            idx = -1
        else:
            idx += find + 1
            cur += 1
    ans = (ans - 1) * len(S) + idx + 1
    print(ans)


if __name__ == "__main__":
    main()