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:
import bisect
S=input()
T=input()

A=set(S)
B=set(T)

if B-A:print(-1)
else:
    d={}
    for b in B:
        d[b]=[i for i in range(len(S)) if S[i]==b]
    c=-1
    p=0
    for t in T:
        idx=bisect.bisect_right(d[t],c)
        if idx == len(d[t]):
            c=d[t][0]
            p+=1
        else:
            c=d[t][idx]
    print(len(S)*p+c+1)

Submission status: Accepted

Solution code:
import sys

s1 = input()
s2 = input()

n1 = 0
t1 = 0
t2 = -1

for i1 in range(len(s2) ):
    t1 =  s1.find(s2[i1],t2 + 1)
    if t1 == -1:
        t1 = s1.find(s2[i1], 0, t2 + 1)
        if t1 == -1:
            print(t1)
            sys.exit()
        else:
            n1 += t1 + (len(s1) - t2)
    else:
        n1 += t1 - t2
    t2 = t1

print(n1)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict

S = input()
T = input()

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

d = defaultdict(list)
l = [0 for _ in range(26)]

for i, v in enumerate(S, 1):
    l[ord(v)-ord('a')] += 1
    d[v].append(i)

len_S = len(S)

# print(l)

ans = 0
c = 0
for t in T:
    i = bisect.bisect_left(d[t], c)
    # print(l[ord(t)-ord('a')])
    if i < l[ord(t)-ord('a')]:
        ans += d[t][i]-c+1
        c = d[t][i]+1
        # print(d[t][i])
    else:
        # print(ans, len_S, c, d[t][0])
        ans += len_S-c+d[t][0]+1
        c = d[t][0]+1
    # print(ans)

if ans > 10**100*len_S:
    print(-1)
else:
    print(ans-1)

Submission status: Accepted

Solution code:
from bisect import *
s=input()
t=input()
a=[[]for i in range(26)]
for i in range(len(s)):
    a[ord(s[i])-97].append(i+1)
p=-1
b=[len(i)for i in a]
r=0
for i in t:
    if b[ord(i)-97]==0:
        print(-1)
        break
    c=bisect_right(a[ord(i)-97],p)
    if c==b[ord(i)-97]:
        r+=1
        p=a[ord(i)-97][0]
    else:
        p=a[ord(i)-97][c]
else:
    print(r*len(s)+p)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict
from bisect import bisect_right

s = ns()
t = ns()

ok = True

sset = set(list(s))
for ti in t:
    if ti not in sset:
        ok = False
        break

if not ok:
    print(-1)

else:
    n = len(s)

    charidx = defaultdict(list)

    for i, si in enumerate(s):
        charidx[si].append(i)
    for i, si in enumerate(s):
        charidx[si].append(n+i)

    ks = charidx.keys()

    move = [{ki: -1 for ki in ks} for _ in range(n)]

    for i, si in enumerate(s):
        for ki in ks:
            idxlist = charidx[ki]
            nexidx = bisect_right(idxlist, i)
            move[i][ki] = (idxlist[nexidx] - i) % (n+1)

    cur = s.index(t[:1])
    ans = cur
    for ti in t[1:]:
        nex = move[cur][ti]
        ans += nex
        cur = (cur + nex) % n

    print(ans+1)

Submission status: Accepted

Solution code:
s = input()
t = input()
count = 0
stock = 0
check = 0

for i in t:
    if check==0:
        if i in s:
            stock = s.index(i)
            check = 1
        else:
            count = -1
            break
    else:
        if i in s:
            if stock==len(s)-1:
                count += 1
                stock = s.index(i)
                continue
            if i in s[stock+1:]:
                stock = s[stock+1:].index(i) + stock + 1
                continue
            else:
                count += 1
                stock = s.index(i)
                continue
        else:
            count = -1
            break
        
if count==-1:
    print(count)
else:
    print(count*len(s)+stock+1)

Submission status: Accepted

Solution code:
import bisect
s = input().rstrip()
t = input().rstrip()

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

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)

Submission status: Accepted

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

import bisect

def f(D, T, lenOfS):
    x = 0
    p = -1
    for c in T:
        d = D[ord(c) - 97]
        if len(d) == 0:
            return -1
            
        idx = bisect.bisect_left(d, p+1)

        if idx < len(d):
            p2 = d[idx]
        else:
            p2 = d[0]
            x += lenOfS;

        x += (p2 - p)
        p = p2
            
    return x


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

    D = [[] for _ in range(26)]
    for i, c in enumerate(S):
        D[ord(c) - 97].append(i)

    print(f(D, T, len(S)))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

S  = lambda: input()

s = S()
t = S()

count = 0
loop = -1
s_index = 0
t_index = 0
is_ok = True
while True:
  loop += 1
  s_index = 0
  if t[t_index] not in s:
    is_ok = False
    break

  while t[t_index] in s[s_index:]:
    s_index += s[s_index:].find(t[t_index]) + 1
    t_index += 1
    if t_index == len(t):
      break
  
  if t_index == len(t):
      break

if is_ok:
  print(loop * len(s) + s_index)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return sys.stdin.readline()[:-1]

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

    alfa = defaultdict(list)
    for i, c in enumerate(s):
        alfa[c].append(i)
    pre = -1
    ans = 0
    for i, c in enumerate(t):
        index = alfa[c]
        if len(index) == 0:
            print(-1)
            return
        a = bisect.bisect_right(index, pre)
        if a != len(index):
            pre = index[a]
        else:
            pre = index[0]
            ans += len(s)

    print(ans + pre + 1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right,bisect_left
alphabet_small = [chr(i) for i in range(97, 97+26)]
s = input()
t = input()
m = len(s)
n = len(t)

alpha = [[] for i in range(26)]
for i,let in enumerate(s):
    for j,al in enumerate(alphabet_small):
        if let == al:
            alpha[j].append(i)

#alpha　はsのどこに文字があるか

dp = [0 for i in range(n+1)] #i文字目までの最小
#求めるのはdp[n]
t_num = []
append = t_num.append
for let in t:
    for j,al in enumerate(alphabet_small):
        if let == al:
            t_num.append(j)

#t_num　はtの文字を数字に変換
now = -1
for i,let_num in enumerate(t_num):
    #print(i,let_num,alpha[let_num])
    if len(alpha[let_num]) == 0:
        print(-1)
        exit()
    else:
        q = bisect_right(alpha[let_num], now)
        #print(q)
        if q != len(alpha[let_num]):
            next = alpha[let_num][q]
            #print(now,next,1)
            if now == next:
                dp[i+1] += m
                #print(dp[i+1])
            dp[i+1] += dp[i] + next - now
        else:
            next = alpha[let_num][0]
            dp[i+1] += dp[i] + next - now + m
        now = next



print(dp[n])

Submission status: Accepted

Solution code:
from bisect import bisect_left
s = input()
t = input()
pos = {}
for i, c in enumerate(s):
    if c not in pos:
        pos[c] = [i]
    else:
        pos[c].append(i)
ans = 0
pre = -1
for c in t:
    if c not in pos:
        print(-1)
        exit()
    l = bisect_left(pos[c], pre+1)
    if l >= len(pos[c]):
        p = pos[c][0]
        ans += len(s)
    else:
        p = pos[c][l]
    ans += p - pre
    # print(c, l, pre)
    pre = p

print(ans)

Submission status: Accepted

Solution code:
import bisect
s=list(input())
t=list(input())
N=len(s)
sd={x:[] for x in sorted(set(s))}
if not set(t) <= set(sd.keys()):
    print(-1)
    exit()

for i,c in enumerate(s):
    sd[c].append(i)
index=-1
ans=0
for c in t:
    i=bisect.bisect_left(sd[c],index+1)

    if i==len(sd[c]):
        ans+=1
        i=bisect.bisect_left(sd[c],0)
    index=sd[c][i]
print(ans*N+index+1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
s=input().rstrip()
t=input().rstrip()
m=len(s)
D=[[] for i in range(26)]
for i in range(m):
    D[ord(s[i])-97].append(i)
import sys
import bisect
now=-1
ans=0
for i in t:
    if D[ord(i)-97]==[]:
        print(-1)
        sys.exit()
    p=bisect.bisect(D[ord(i)-97],now)
    if p==len(D[ord(i)-97]):
        ans+=m-1-now
        now=D[ord(i)-97][0]
        ans+=now+1
    else:
        ans+=D[ord(i)-97][p]-now
        now=D[ord(i)-97][p]
print(ans)

Submission status: Accepted

Solution code:
import bisect

s = list(input())
t = list(input())
len_s = len(s)
LEN = [0] * 26
s_set = set(s)
t_set = set(t)
d = [None] * 26
ans = 0
now = -1
if s_set >= t_set:
  for key,i in enumerate(s):
    index = ord(i) - ord("a")
    if d[index] == None:
      d[index] = [key]
    else:
      d[index].append(key)
    LEN[index] += 1
  for j in t:
    ORD = ord(j) - ord("a")
    g = bisect.bisect_right(d[ORD],now)
    if g == LEN[ORD]:
      ans += len_s
      now = d[ORD][0]
    else:
      now = d[ORD][g]
  ans += now + 1
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
S=list(input())

A=["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"]
L=[[]for i in range(26)]
for i in range(len(S)):
    for j in range(26):
        if S[i]==A[j]:
            L[j].append(i+1)
#print(L)
T=list(input())
M=[[]for i in range(26)]
for i in range(len(T)):
    for j in range(26):
        if T[i]==A[j]:
            M[j].append(i+1)
            T[i]=j
#print(M)
#print(T)

for i in range(26):
    if M[i] !=[] and L[i]==[]:
        print(-1)
        exit()

import math
import bisect
ans=0
mo=0
for i in T:
    if L[i][-1]<=ans:
        mo+=ans//len(S)
        ans%=len(S)
        if L[i][-1]<=ans:
            mo+=1
            ans-=len(S)
    ans=L[i][bisect.bisect_right(L[i],ans)]
    #print(mo*len(S)+ans,mo,ans)
print(mo*len(S)+ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
ls,lt = len(s),len(t)
i = j = 0
si = lp = 0
while True:
    tc = t[i]
    si = s.find(tc)
    if si == -1:
        print(-1)
        exit(0)
    else:
        if i == lt-1:
            print(lp*ls + si+1)
            exit(0)
        else:
            while True:
                if t[i+1] in s[si+1:]:
                    si = s[si+1:].find(t[i+1]) + si +1
                    if i+1 == lt-1:
                        print(lp*ls + si+1)
                        exit(0)
                    else:
                        i+=1
                else:
                    i+=1
                    break
    lp += 1
    if i >= lt:
        print(-1)
        break

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right


def main():
    S = list(input())
    T = list(input())
    sl = len(S)

    Sdic = {}
    for i, s in enumerate(S):
        if not s in Sdic.keys():
            Sdic[s] = [i]
        else:
            Sdic[s].append(i)
    pret = -1
    ans = 0
    for t in T:
        try:
            #print(Sdic[t])
            it = bisect_right(Sdic[t], pret)
            #print(it, t)
            if it < len(Sdic[t]):
                pret = Sdic[t][it]
            else:
                ans += sl
                pret = Sdic[t][0]
            #print(t, update, pret)
        except KeyError:
            ans = -1
            break
    if ans != -1:
        ans += pret+1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

idx = {}
l = len(s)

for i in range(l):
  ch = s[i]
  if ch in idx:
    arr = idx[ch]
    _idx = bisect.bisect_right(arr, i + 1)
    arr.insert(_idx, i + 1)
    idx[ch] = arr
  else:
    idx[ch] = [i + 1]

ans = 0

for ch in t:
  if ch in idx:
    arr = idx[ch]
    __idx = bisect.bisect_right(arr, ans % l)
    if __idx == len(arr):
      ans = -(-ans // l) * l + arr[0]
      _idx = arr[0]
    else:
      ans = (ans // l) * l + arr[__idx]
      _idx = arr[__idx]
  else:
    ans = -1
    break

print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

s = input()
t = input()

word = defaultdict(int)
for i in range(len(s)):
	if type(word[s[i]]) == int:
		word[s[i]] = []
	bisect.insort(word[s[i]], i)

loc = 0
ret = 0
for i in range(len(t)):
	if word[t[i]] == 0:
		print(-1)
		exit()
	else:
		select = bisect.bisect_left(word[t[i]], loc)
		if select == len(word[t[i]]):
			ret += 1
			loc = word[t[i]][0] + 1
		else:
			loc = word[t[i]][select] + 1
print(ret*len(s) + loc)

Submission status: Accepted

Solution code:
def solve(s, t):
    ls = len(s)
    nxt = {}
    follow = [{} for _ in range(ls + 1)]
    for i, c in enumerate(s[::-1]):
        i = ls - i
        follow[i] = nxt.copy()
        nxt[c] = i
    follow[0] = nxt.copy()
    ans = 0
    i = 0
    for c in t:
        if c not in follow[i]:
            if c not in follow[0]:
                return -1
            ans += len(s)
            i = follow[0][c]
            continue
        i = follow[i][c]
    return ans + i


s = input()
t = input()
print(solve(s, t))

Submission status: Accepted

Solution code:
import string
import bisect

s=input()
t=input()
tng=len(t)
sng=len(s)

komoji=string.ascii_lowercase
kjlist=[]
kjlist2=[]
mada=[]
for kj in komoji:
    kjlist.append([kj, []])
    kjlist2.append(kj)
    mada.append(kj)

for tt in range(sng):
    ban=kjlist2.index(s[tt])
    kjlist[ban][1].append(tt)

kosu=0
now=-1
nasi=0
zerosw=0
for ss in range(tng):
    ban=kjlist2.index(t[ss])
    if len(kjlist[ban][1])>0:
        basho=bisect.bisect_right(kjlist[ban][1], now)
        if basho==len(kjlist[ban][1]):
            now=kjlist[ban][1][0]
            maekos=kosu
            kosu=(int(kosu/sng)+1)*sng+now
        else:
            now=kjlist[ban][1][basho]
            maekos=kosu
            kosu=int(kosu/sng)*sng+now
    else:
        nasi=1
    
if nasi==0:
    print(kosu+1)
else:
    print(-1)

Submission status: Accepted

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

l = len(s)
dic = {c: [0] * l for c in set(s)}

for i in range(l):
    dic[s[i]][i] = 1

for key in dic.keys():
    lst = dic[key]
    for i in range(l - 1):
        lst[i + 1] += lst[i]

idx = -1
ans = 0
for c in t:
    if not c in dic:
        print(-1)
        exit(0)
    lst = dic[c]
    cur = lst[idx] if idx >= 0 else 0
    i = bisect_left(lst, cur + 1)
    if i == l:
        ans += l
        idx = -1
        cur = 0
        i = bisect_left(lst, 1)

    idx = i
ans += idx
print(ans + 1)

Submission status: Accepted

Solution code:
s = input()
t = input()
pre_index = 0
ans = 0
for i in t:
  if i not in s:
    ans = -1
    break
  else:
    temp = s[pre_index:]
    if i in temp:
      ans += (temp.index(i)+1)
      pre_index+= (temp.index(i)+1)
    else:
      ans += len(temp)
      pre_index = (s.index(i)+1)
      ans += pre_index
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect

from string import ascii_lowercase

s = input()
t = input()

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

N = len(s)
ans = 0
prev = -1
# print(dp)
for c in t:
    if not dp[c]:
        ans = -1
        break
    i = bisect(dp[c], prev)
    if i == len(dp[c]):
        i = 0
    k = dp[c][i]
    # print(k)
    if k > prev:
        d = k - prev
    elif k == prev:
        d = N
    else:
        d = N + k - prev
    # print('d:', d)
    ans += d
    prev = dp[c][i]
print(ans)

Submission status: Accepted

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

d=dict()
for i in "abcdefghijklmnopqrstuvwxyz":
    d[i]=[]
for i,c in enumerate(s):
    d[c].append(i)

now=0
ans=0
for c in t:
    l=len(d[c])
    if l==0:
        print(-1)
        break
    i=bisect.bisect_left(d[c],now)
    if i<l:
        now=d[c][i]+1
    else:
        ans+=len(s)
        i=bisect.bisect_left(d[c],0)
        now=d[c][i]+1
else:
    ans+=now
    print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
sn = len(s)
tn = len(t)

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

for i in range(sn):
    number = ord(s[i]) - ord('a')
    alpha[number].append(i)

dist = [[-1 for i in range(26)] for j in range(sn)]
    
for i in range(26):
    if(len(alpha[i]) >= 1):
        now=0
        prev=0
        for j in range(len(alpha[i])):
            val = alpha[i][j]
            for k in range(val-prev):
                dist[now][i] = val-now
                now += 1
            prev=now
        val = alpha[i][0]
        for k in range(sn-prev):
            dist[now][i] = val-now+sn
            now += 1
            
#print(alpha)
#print(dist)

prev = sn-1
ans = 0
for i in range(tn):
    d = dist[prev][ord(t[i]) - ord('a')]
    if(d==-1):
        ans = -1
        break
    ans += d
    prev = (prev + d)%sn
    
print(ans)

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:

import bisect

s = input()
t = input()

dic = {}

for i in range(len(s)):

    if s[i] not in dic:

        dic[s[i]] = [i]

    else:

        dic[s[i]].append(i)

roop = 0
point = -1
flag = True

for i in range(len(t)):


    if t[i] not in dic:
        flag = False
        break

    ind = bisect.bisect_left(dic[t[i]],point)

    if ind >= len(dic[t[i]]):
        roop += 1
        point = dic[t[i]][0] + 0.1

    else:
        point = dic[t[i]][ind] + 0.1


if flag:
    print (len(s) * roop + int(point) + 1)

else:
    print (-1)

Submission status: Accepted

Solution code:
s=input()
t=input()
x=list(s)
y=list(t)
import sys
if len(set(y)-set(x))!=0:
	print(-1)
	sys.exit()
a=[[] for _ in range(26)]
for i in range(len(s)):
	a[ord(x[i])-97].append(i)
import bisect

repeat=0
last=-1
for i in range(len(t)):
	temp=a[ord(y[i])-97]
	if last>=temp[-1]:
		repeat+=1
		last=temp[0]
	else:
		last=temp[bisect.bisect_right(temp,last)]
	#print(temp,repeat,last)
print(repeat*len(s)+last+1)

Submission status: Accepted

Solution code:
s = input()
t = input()
temp = -1
cycle = 0
ans = True
for tt in t:
    if tt in s[temp+1:]:
        k = s[temp+1:].find(tt)
        temp += k + 1
    elif tt in s:
        temp = s.find(tt)
        cycle += 1
    else:
        ans = False
        break
if ans:    
    print((cycle*len(s)) + temp + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
s = input() # これを繰り返しまくる
t = input() # これを探す

# 判定
s_set = set(s)
s_len = len(s)

if all((t_ in s_set) for t_ in t):
    ans = 0
    ss = s + s
    found_index_old = -1

    for t_ in t:
        found_index = ss.find(t_, found_index_old + 1)
        # print(ss, found_index_old + 1, found_index, found_index + 1 - (found_index_old + 1))
        ans += found_index - found_index_old # found_index + 1 - (found_index_old + 1)
        found_index_old = found_index % s_len
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

S = input()
T = input()

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

cnt = 0
pre = -1
for t in T:
    if t not in memo:
        print(-1)
        quit()
    m = bisect_left(memo[t], pre + 1)
    if m >= len(memo[t]):
        cnt += 1
        pre = memo[t][0]
    else:
        pre = memo[t][m]

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

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect
s=input()
t=input()
n=len(s)
m=len(t)
ord_a=ord("a")
s_=[[] for i in range(26)]
for i in range(n):
  s_[ord(s[i])-ord_a].append(i)
k=ord(t[0])-ord_a  
if (not s_[k]):
    print(-1)
    exit()
ans=s_[k][0]
rep=0
for i in range(1,m):
  k=ord(t[i])-ord_a
  #print(s_[k])
  if (not s_[k]):
    print(-1)
    exit()
  if s_[k][-1]<=ans%n:
    rep+=1
    ans=rep*n+s_[k][0]
  else:
    pos=bisect(s_[k],ans%n)
    #print(pos)
    ans+=s_[k][pos]-ans%n
  #print(ans)
print(ans+1)

Submission status: Accepted

Solution code:
S = [ord(s) - 97 for s in input()]
T = [ord(t) - 97 for t in input()]
ls = len(S)

indexes = [[] for _ in range(26)]
for i, s in enumerate(S):
    indexes[s].append(i)
m = [[-1] * 26 for _ in range(ls)]
for s in range(26):
    inds = indexes[s]
    if not len(inds):
        continue
    for r in range(1, len(inds)):
        for i in range(inds[r-1], inds[r]):
            m[i][s] = inds[r] - i
    l = inds[-1]
    r = inds[0]
    i = l
    while True:
        m[i][s] = (r - i - 1) % ls + 1
        if i == (r - 1) % ls:
            break
        i = (i + 1) % ls

ans = 0
i = ls - 1
for t in T:
    cnt = m[i][t]
    if cnt == -1:
        print(-1)
        exit()
    ans += cnt
    i = (i + cnt) % ls
print(ans)

Submission status: Accepted

Solution code:
import bisect

S = input()
T = input()

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

x = 0
current = 0
impossible = 0
for i, t in enumerate(T):
    if t in idx.keys():
        idx_list = idx[t]
        j = bisect.bisect_right(idx_list, current)
        if j < len(idx_list):
            current = idx_list[j]
        else:
            x += 1
            current = idx_list[0]
    else:
        impossible = 1
        break

if impossible:
    print(-1)
else:
    print(x * len(S) + current)

Submission status: Accepted

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

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    return -1

s = list(input())
t = list(input())
if len(set(t)-set(s)) != 0:
    print(-1)
    exit(0)

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

index = -1
round = 0

for tt in t:
    index = find_gt(sdict[tt], index)
    if index == -1:
        index = sdict[tt][0]
        round += 1
ans = round * len(s) + index + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect
s = input()
t = input()
S = defaultdict(list)
for i, c in enumerate(list(s)):
    S[c].append(i + 1)
now = 0
num = 0
for c in t:
    if c not in S:
        print(-1)
        exit()
    P = S[c]
    x = bisect(P, now)
    if x < len(P):
        num += P[x] - now
        now = P[x]
    else:
        num += len(s) - now
        num += P[0]
        now = P[0]
print(num)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict


def in_sort(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


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

    c_idx = defaultdict(list)

    for i, c in enumerate(s):
        c_idx[c].append(i)

    idx = -1
    ans = 0
    for c in t:
        if len(c_idx[c]) == 0:
            return -1

        idx_in_c = bisect.bisect_right(c_idx[c], idx)
        # next s
        if idx_in_c == len(c_idx[c]):
            idx -= len(s)
            ans += len(s)
            idx_in_c = bisect.bisect_right(c_idx[c], idx)
        
        idx = c_idx[c][idx_in_c]

    return ans + idx + 1


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

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
T = input()
cts = Counter(S)
ctt = Counter(T)
if set(ctt.keys()) - set(cts.keys()):
  print(-1)
  exit()

previdx = {}
L = len(S)
for i, c in enumerate(S):
  if c not in previdx:
    previdx[c] = i

keys = list(previdx.keys())
nxts = [{} for _ in range(L)]
for i in range(L-1, -1, -1):
  nxt = nxts[i]
  for k in keys:
    a = previdx[k] - i
    if a == 0:
      nxt[k] = L
    else:
      nxt[k] = a % L
  previdx[S[i]] = i

ans = previdx[T[0]]
pos = ans
for c in T[1:]:
  d = nxts[pos][c]
  ans += d
  pos = (pos + d) % L
print(ans+1)

Submission status: Accepted

Solution code:
s=input()
t=input()
s_rm = s
ans=0
for i in t:
    if i in s_rm:
        index = s_rm.index(i)
        s_rm = s_rm[index+1:]
        ans += index+1
    elif i in s:
        index = s.index(i)
        ans += len(s_rm) + index +1
        s_rm = s[index+1:]
    else:
        ans=-1
        break
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = input()
n = len(s)
t = input()
m = len(t)
tr = set(s)
for c in t:
  if c not in s:
    print(-1)
    exit(0)
d = {c:[] for c in 'abcdefghijklmnopqrstuvwxyz'}
for i, c in enumerate(s):
  d[c].append(i)
idx = -1
ans = 0
for c in t:
  tmp = bisect_right(d[c], idx)
  if tmp == len(d[c]):
    idx = d[c][0]
    ans += 1
  else:
    idx = d[c][tmp]
print(ans * n + idx + 1)

Submission status: Accepted

Solution code:
import bisect
S,T = input(),input()
lenS = len(S)
alp = [[]for i in range(26)]

for i in range(len(S)):
    alp[ord(S[i])-97].append(i)

if alp[ord(T[0])-97] == []:
    print(-1)
    exit()

l = [alp[ord(T[0])-97][0]]
for c in T[1:]:
    A = alp[ord(c)-97]
    if A == []:
        print(-1)
        exit()
    l.append(A[bisect.bisect_left(A,l[-1]+1)%len(A)])

ans = 0
for i in range(len(l)-1):
    if l[i] >= l[i+1]:
        ans += 1
print(ans*lenS+l[-1]+1)

Submission status: Accepted

Solution code:
from bisect import bisect_right

s = input()
t = input()

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

dup = 0
prev = -1
for i in range(len(t)):
    if t[i] not in table:
        print(-1)
        exit()

    ind_list = table[t[i]]
    if prev < ind_list[-1]:
        temp = bisect_right(ind_list, prev)
        prev = ind_list[temp]
        continue
    else:
        dup += 1
        prev = ind_list[0]

print(dup * len(s) + prev + 1)

Submission status: Accepted

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

d = dict()
for i in range(26):
    d[chr(97+i)] = i

s_index = [[] for i in range(26)]
for i in range(len(s)):
    s_index[d[s[i]]].append(i)


flag = 1
ans = 0
index = -1
for ti in t:
    s_char = s_index[d[ti]]
    if len(s_char) == 0:
        flag = 0
        ans = -1
        break
    next = s_char[bisect_left(s_char, index) % len(s_char)]
    if next == index:
        next = s_char[(bisect_left(s_char, index)+1) % len(s_char)]

    if next == index:
        ans += len(s)
    else:
        if index == -1:
            ans += next - index
        else:
            ans += (next - index) % len(s)

    index = next


print(ans)

Submission status: Accepted

Solution code:
def hersCode(L, n):
  if n >= L[-1]:
    return -1
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] > n:
      ok = mid
    else:
      ng = mid
  return ok


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

R = {}

for i in t:
  if i not in R:
    R[i] = []
    flag = True
    for j in range(len(s)):
      if i == s[j]:
        R[i].append(j)
        flag = False
    if flag:
      print(-1)
      exit()

num = -1
cnt = 0

for i in t:
  t = hersCode(R[i], num)
  if t == -1:
    num = -1
    cnt += 1
    t = hersCode(R[i], num)
  num = R[i][t]
print(cnt * len(s) + num + 1)

Submission status: Accepted

Solution code:
s=input()
t=input()
import bisect
dist=[[]for i in range(30)]


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

cnt=0
nw = 1

for i in range(len(t)):
    chrno=ord(t[i])-ord("a")
    if len(dist[chrno]) == 0:
        print(-1)
        exit()

    neIdx = bisect.bisect_left(dist[chrno], nw)
    if neIdx == len(dist[chrno]):
        cnt+=1
        nw = dist[chrno][0]+1
    else:
        nw=dist[chrno][neIdx]+1

print(len(s)*cnt+nw-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

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

dic = defaultdict(list)

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

loop = 0
mark = -1
for i in t:
    if len(dic[i]) == 0:
        loop = -1
        break
    ind = bisect.bisect_right(dic[i], mark)
    if ind == len(dic[i]):
        ind = 0
        loop += 1
    mark = dic[i][ind]

if loop == -1 :
    print(-1)
else:
    print(loop * len(s) + mark +1)