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

def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)

    l = [[] for _ in range(26)]
    for i in range(n):
        l[ord(s[i]) - ord('a')].append(i)
    for i in range(n):
        l[ord(s[i]) - ord('a')].append(i+n)

    ans = 0
    p = 0
    for i in range(m):
        c = ord(t[i]) - ord('a')
        if len(l[c]) == 0:
            print(-1)
            return
        p = l[c][bisect.bisect_left(l[c], p)] + 1
        if p >= n:
            p -= n
            ans += n
    ans += p
    print(ans)
    return

main()

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = input()
t = input()
d = {}

for i in range(len(s)):
    if s[i] in d:
        d[s[i]] += [i]
    else:
        d[s[i]] = [i]

count = 0
cur = -1
for i in t:
    if i not in d:
        print(-1)
        exit()
    if cur < d[i][-1]:
        cur = d[i][bisect_right(d[i], cur)]
        continue
    else:
        count += 1
        cur = d[i][0]
print(count*len(s)+cur+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()
N = len(S)

# SにT中の文字が含まれていない場合
set_s = set(S)
set_t = set(T)
for c in set_t:
    if not c in set_s:
        print(-1)
        exit()

# それぞれのアルファベットの位置を格納
idxs = defaultdict(list)
for i in range(N):
    idxs[S[i]].append(i)

p = -1
loop_cnt = 0
for c in T:
    idx = bisect_right(idxs[c], p)
    #print(idxs[c], p, idx)
    if idx >= len(idxs[c]):
        loop_cnt += 1
        p = idxs[c][0]
    else:
        p = idxs[c][idx]

ans = N * loop_cnt + p + 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
ai = [[] for i in range(26)]
s = list(input())
t = list(input())
n = len(s)
for i in range(n):
    ai[int(ord(s[i])-97)].append(i)
n2 = len(t)
count = 0
if len(ai[int(ord(t[0]))-97]) > 0:
    now = ai[int(ord(t[0]))-97][0]
    for i in range(1,n2):
        nex = int(ord(t[i]))-97
        n3 = len(ai[nex])
        if n3 == 0:
            count = 0
            now = -2
            break
        else:
            ni = bisect.bisect_right(ai[nex],now)
            #print(ni,count,now)
            if ni == n3:
                ni = 0
            if ai[nex][ni] > now:
                now = ai[nex][ni]
            else:
                count += 1
                now = ai[nex][ni]
    print(count*n+now+1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_right

S = [ord(x)-ord('a') for x in readline().rstrip().decode('utf-8')]
T = [ord(x)-ord('a') for x in readline().rstrip().decode('utf-8')]

index = [[] for _ in range(26)]
for i,x in enumerate(S):
    index[x].append(i)

LS = len(S)
for x in index:
    if x:
        x.append(x[0] + LS)

ptr = -1 # 最後に使った文字
complete = True
for t in T:
    seq = index[t]
    if not seq:
        complete = False
        break
    i = ptr%LS
    j = bisect_right(seq,i)
    ptr += seq[j]-i

if complete:
    answer = ptr + 1
else:
    answer = -1
print(answer)

Submission status: Accepted

Solution code:
import bisect

S = input()
T = input()

#dict型 各アルファベットのインデックスを登録
alp = {} #{str:list[int,int,~~],:,:}
for i,s in enumerate(S):
    alp.setdefault(s,[]).append(i)
# print(alp)


bef_idx = -1
ans = 0
for t in T:
    # print(t)
    if t not in alp:
        ans = -(bef_idx+2)
        break

    idx_list = alp[t]
    #bef_idxより右にtが無ければ次の連結
    #bef_idxは一番最後に足す
    if idx_list[-1] <= bef_idx:
        ans += len(S)
        bef_idx = -1
    idx = bisect.bisect_left(idx_list,bef_idx+1)
    bef_idx = idx_list[idx]
    # print(bef_idx,idx)
    # print(ans)
ans += (bef_idx+1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    S=input()
    T=input()
    if(set(T)-set(S)):
        print(-1)
        return
    n=len(S)
    C=[[] for _ in range(26)]
    for i,s in enumerate(S*2): C[ord(s)-97].append(i)
    from bisect import bisect_left
    ans=0
    for s in T:
        j=bisect_left(C[ord(s)-97],ans%n)
        ans+=C[ord(s)-97][j]-ans%n+1
    print(ans)
resolve()

Submission status: Accepted

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

l = len(s)
d = dict()
for i in range(l):
    if s[i] in d.keys():
        d[s[i]].append(i+1)
    else:
        d[s[i]] = [i+1]

ans = 0
now = 0
for i in t:
    if i not in d.keys():
        print(-1)
        exit()

    a = bisect.bisect_right(d[i], now)
    if a == len(d[i]):
        now = d[i][0]
        ans += l
    else:
        now = d[i][a]

print(ans + now)

Submission status: Accepted

Solution code:
import bisect

S = input()
T = input()

Sset = set(list(S))
Tset = set(list(T))
if len(Tset-Sset) > 0:
  print(-1)
  exit()

SS = S * 2
SSpos = {}
for i in range(len(SS)):
  if SS[i] in SSpos:
    SSpos[SS[i]].append(i)
  else:
    SSpos[SS[i]] = [i]
for i in SSpos:
  SSpos[i].sort()
#print(SSpos)

ans = 0
i = 0
for t in T:
  j = bisect.bisect_left(SSpos[t],i)
  ans += SSpos[t][j] - i + 1
  #print(t,SSpos[t],ans,i,j)
  i = SSpos[t][j] + 1
  if i >= len(S):
    i -= len(S)
print(ans)

Submission status: Accepted

Solution code:
from sys import exit

s = input()
t = input()

tset = set(t)
slen = len(s)
aord = ord('a')
if len(tset - set(s)) != 0:
    print(-1)
    exit()

s2t = [i - aord for i in (s + s).encode('ascii')]
lut = [[-1] * slen for _ in range(26)]
for c in tset:
    b = ord(c) - aord
    j = 0
    for i in range(slen * 2 - 1, -1, -1):
        if s2t[i] == b:
            j = 0
        else:
            j += 1
        if i < slen:
            lut[b][i] = j

p = 0
for c in t:
    b = ord(c) - aord
    p += lut[b][p % slen] + 1
print(p)

Submission status: Accepted

Solution code:

# import sys
# input = sys.stdin.readline
import bisect


def ch_to_int(c):
    return ord(c) - 96


def main():
    s = input()
    t = input()
    pos = 0
    count = 0
    ch = [[] for i in range(27)]

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

    for i in range(len(t)):
        c = ch_to_int(t[i])
        li = ch[c]

        if len(li) == 0:
            pos = -1
            count = 0
            break

        next_index = bisect.bisect_left(li, pos)
        # print(next_index, pos, li)
        if next_index >= len(li):
            next_pos = li[0]
            count += 1
            pos = next_pos + 1
        else:
            if pos == li[next_index]:
                pos += 1
            else:
                pos = li[next_index] + 1
        # print(li, next_index, pos, count)

    print(pos + count * len(s))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import collections

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

counter_s = collections.Counter(s)
counter_t = collections.Counter(t)
for c in counter_t.keys():
    if c not in counter_s.keys():
        print(-1)
        exit()

s_indices = collections.defaultdict(list)
for i, c in enumerate(s):
    if c in counter_t.keys():
        s_indices[c].append(i)

index = 0
count = 0
offset = 0
while index < len(t):
    c = t[index]
    i = bisect.bisect_left(s_indices[c], offset)
    if i == len(s_indices[c]):
        count += 1
        offset = 0
    else:
        offset = s_indices[c][i] + 1
        index += 1
print(len(s) * count + offset)

Submission status: Accepted

Solution code:
# O (T * log(S))
from bisect import bisect_left

S = list(input())
T = list(input())
# S = 'a' * (10 ** 5) + 'b'
# T = 'b' * (10 ** 5)
#条件を満たせるかを調べる
setS = set(S)
for t in T:
    if t not in setS:
        print (-1)
        exit()

lst = [[] for _ in range(26)]
for index, x in enumerate(S):
    lst[ord(x) - 97].append(index)

tmp = 0 #現在地
roop = 0
for t in T:
    tmp = bisect_left(lst[ord(t) - 97], tmp)
    if tmp == len(lst[ord(t) - 97]):
        roop += 1
        tmp = lst[ord(t) - 97][0] + 1
    else:
        tmp = lst[ord(t) - 97][tmp] + 1

# print (roop)
# print (tmp)
print (roop * len(S) + tmp)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from bisect import bisect_right
s = input()
t = input()
n = len(s)
cmap = dd(list)
for i, c in enumerate(s):
    cmap[c].append(i)
for i, c in enumerate(s):
    cmap[c].append(i+n)
cmap = dict(cmap)
a = 0
pos = -1
for c in t:
    try:
        i = bisect_right(cmap[c], pos)
        ind = cmap[c][i]
    except:
        print(-1)
        exit()
    if ind >= n:
        a += n
        pos = ind - n
    else:
        pos = ind
print(a + pos + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

s = input()
t = input()

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

d = defaultdict(list)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i+n)

pos = -1
ans = 0

for c in t:
    l = d[c]
    if l:
        i = bisect.bisect_right(l, pos)
        ind = l[i]
        if ind >= n:
            pos = ind - n
            ans += n
        else:
            pos = ind    
    else:
        ans = -1
        break

print(ans if ans==-1 else ans+pos+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

s = input()
t = input()

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

d = defaultdict(list)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i+n)

pos = -1
ans = 0

for c in t:
    l = d[c]
    if l:
        ind = bisect.bisect_right(l, pos)
        ans += l[ind]-pos
        if l[ind] >= n:
            pos = l[ind] - n
        else:
            pos = l[ind]    
    else:
        ans = -1
        break

print(ans)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
d = { c: [] for c in t }
for i, c in enumerate(s):
  if c in d:
    d[c].append(i)

n = -1
ans = 0


for j, c in enumerate(t):
  l = d[c]
  if l:
    i = bisect.bisect_right(l, n)
    if i == len(l):
      ans += len(s)
      n = l[0]
    else:
      n = l[i]
    if j == len(t) - 1:
      if i == len(l):
        ans += l[0] + 1
      else:
        ans += l[i]+1
  else:
    ans = -1
    break

print(ans)

Submission status: Accepted

Solution code:
import bisect
s = input()
t = input()
d = { c: [] for c in t }
for i, c in enumerate(s):
  if c in d:
    d[c].append(i)
for dc in d.values():
  dc.sort()

n = -1
ans = 0


for j, c in enumerate(t):
  l = d[c]
  if l:
    i = bisect.bisect_right(l, n)
    if i == len(l):
      ans += len(s)
      n = l[0]
    else:
      n = l[i]
    if j == len(t) - 1:
      if i == len(l):
        ans += l[0] + 1
      else:
        ans += l[i]+1
  else:
    ans = -1
    break

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect

#Aのなかでlより大きな最小の値を得る.Aはソート済み

s = input()
t = input()
a = 'abcdefghijklmnopqrstuvwxyz'
d = {}
for ch in a:
  d[ch] = []
for ch,n in zip(s,range(len(s))):
  d[ch].append(n)

rep = 0
p = -1
for ch in t:
  if len(d[ch])==0:
    print("-1")
    exit()
  else:
    i = bisect(d[ch],p)
    if i!=len(d[ch]):p=d[ch][i]
    else:
      p = d[ch][0]
      rep+=1

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

Submission status: Accepted

Solution code:
from bisect import bisect


def search_alphabet_index(string):
    cs = [[] for i in range(26)]
    for i, s in enumerate(string):
        j = ord(s) - ord("a")
        cs[j].append(i)
    return cs


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

    cs = search_alphabet_index(S)

    for c in set(T):
        if not cs[ord(c) - ord("a")]:
            ans = -1
            print(ans)
            exit()

    rnd = 0
    k = -1
    for t in T:
        ti = ord(t) - ord("a")
        i = bisect(cs[ti], k)
        if i == len(cs[ti]):
            k = cs[ti][0]
            rnd += 1
        else:
            k = cs[ti][i]
    ans = rnd * N + k + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    s = input()
    t = input()
    dictPos = defaultdict(list)
    N = len(s) - 1
    for i in range(N):
        ch = s[i]
        dictPos[ch].append(i+1)
    countLoop = 0
    lastPos = -1
    M = len(t) - 1
    for i in range(M):
        ch = t[i]
        listPos = dictPos[ch]
        if len(listPos) == 0:
            print(-1)
            exit()
        if listPos[-1] <= lastPos:
            lastPos = listPos[0]
            countLoop += 1
        else:
            lastPos = listPos[bisect_right(listPos, lastPos)]
    ans = N * countLoop + lastPos
    print(ans)

if __name__ == '__main__': main()

Submission status: Accepted

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

dict_pos = collections.defaultdict(list) # dict of index 
for i, ch in enumerate(s, 1): 
    dict_pos[ch].append(i)

count_loop = 0
last_pos = -1
for ch in t:
    list_pos = dict_pos[ch]
    if len(list_pos) == 0:
        print(-1)
        quit()
    if list_pos[-1] <= last_pos:
        last_pos = list_pos[0]
        count_loop += 1
    else:
        last_pos = list_pos[bisect.bisect_right(list_pos, last_pos)]

print(count_loop * len(s) + last_pos)

Submission status: Accepted

Solution code:
def main():
    s = str(input())
    t = str(input())
    if set(t) <= set(s):
        x = -1
        counter = 0
        for i in t:
            x = s.find(i, x+1)
            if x == -1:
                counter += 1
                x = s.find(i)
        print(x+1+counter*len(s))
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
D = {}
for i, item in enumerate(s):
    try:
        D[item].append(i)
    except:
        D[item] = [i]

for i in D.keys():
    # print(D[i][0])
    D[i].append(D[i][0] + ls)

# print(D)

import bisect

def e():
    ans = 0
    ind = -1
    for i in range(lt):
        try:
            L = D[t[i]]
            # print(L)
            bs = L[bisect.bisect_right(L, ind)]
            # print(ans,bs,ind)
            ans += bs - ind
            ind = bs % ls
        except:
            return -1
    return ans

print(e())

Submission status: Accepted

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

N = len(s)

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

for c in set_t:
    if c not in set_s:
        print(-1)
        exit()

# それぞれの文字のインデックスを記録
idxs = defaultdict(list)
for i in range(N):
    idxs[s[i]].append(i)


current_idx = -1 # ここ0にしているとsの1文字目にtの1文字めと同じのがある時にずれるので注意
total = 0
for c in t:
    next_idx = bisect.bisect(idxs[c], current_idx) # bisect(bisect_right)だと同じやつがある場合その右のidxになる

    if next_idx == len(idxs[c]):
        total += N
        current_idx = idxs[c][0]
    else:
        current_idx = idxs[c][next_idx]


print(total + current_idx + 1)
#print(total , current_idx , 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    d = {"Sunny":1 , "Cloudy":2, "Rainy":0}
    a = ["Sunny", "Cloudy", "Rainy"]
    print(a[d[input().rstrip()]])
    return

#B
def B():
    s = S()
    for i, si in enumerate(s):
        if i % 2:
            if si == "R":
                print("No")
                return
        else:
            if si == "L":
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n, k, q = LI()
    d = [0] * n
    for _ in range(q):
        a = II() - 1
        d[a] += 1
    for a in d:
        if k - (q - a) > 0:
            print("Yes")
        else:
            print("No")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for ai in a:
        heappush(q, -ai)
    for _ in range(m):
        heappush(q, heappop(q) / 2)
    ans = 0
    while q:
        ans += int(-heappop(q))
    print(ans)
    return

#E
def E():
    s = S()
    t = S()
    d = defaultdict(list)
    for i,si in enumerate(s):
        d[si].append(i)
    if d[t[0]] == []:
        print(-1)
        return
    before = d[t[0]][0]
    ans = 0
    for ti in t[1:]:
        if d[ti] == []:
            print(-1)
            return
        a = d[ti]
        index = bisect_right(a, before)
        if index == len(a):
            ans += 1
            before = a[0]
        else:
            before = a[index]
    print(ans * len(s) + before + 1)
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

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

Submission status: Accepted

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


# analysis on S
ch = [[] for _ in range(26)]
for i, c in enumerate(s):
    ascii = ord(c) - 97
    ch[ascii].append(i)

bi_left = bisect.bisect_left
bi_right = bisect.bisect_right
now = -1
ans = 0
for i, t in enumerate(t):
    ascii = ord(t) - 97
    if len(ch[ascii]) == 0:
        print("-1")
        exit()
    check = bi_right(ch[ascii], now)

    if check == len(ch[ascii]):
        now = ch[ascii][0]
        ans += 1
    else:
        now = ch[ascii][check]

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

Submission status: Accepted

Solution code:
from sys import exit
s = input()
t = input()
tset = set(t)
slen = len(s)
aord = ord('a')
if len(tset - set(s)) != 0:
    print(-1)
    exit()
s2t = [i - aord for i in (s + s).encode('ascii')]
lut = [[-1] * slen for _ in range(26)]
for c in tset:
    b = ord(c) - aord
    j = 0
    for i in range(slen * 2 - 1, -1, -1):
        if s2t[i] == b:
            j = 0
        else:
            j += 1
        if i < slen:
            lut[b][i] = j
p = 0
for c in t:
    b = ord(c) - aord
    p += lut[b][p % slen] + 1
print(p)

Submission status: Accepted

Solution code:
from sys import exit
s = input()
t = input()
tset = set(t)
slen = len(s)
aord = ord('a')
if len(tset - set(s)) != 0:
    print(-1)
    exit()
s2t = [i - aord for i in (s + s).encode('ascii')]
lut = [[-1 for _ in range(slen)] for _ in range(26)]
for c in tset:
    b = ord(c) - aord
    j = 0
    for i in range(slen * 2 - 1, -1, -1):
        if s2t[i] == b:
            j = 0
        else:
            j += 1
        if i < slen:
            lut[b][i] = j
p = 0
for c in t:
    b = ord(c) - aord
    p += lut[b][p % slen] + 1
print(p)

Submission status: Accepted

Solution code:
def main():
    from sys import exit
    from builtins import ord, range
    s = input()
    t = input()
    tset = set(t)
    slen = len(s)
    aord = ord('a')
    if len(tset - set(s)) != 0:
        print(-1)
        exit()
    s2t = [i - aord for i in (s + s).encode('ascii')]
    lut = [[-1 for _ in range(slen)] for _ in range(26)]
    for c in tset:
        b = ord(c) - aord
        j = 0
        for i in range(slen * 2 - 1, -1, -1):
            if s2t[i] == b:
                j = 0
            else:
                j += 1
            if i < slen:
                lut[b][i] = j
    p = 0
    for c in t:
        b = ord(c) - aord
        p += lut[b][p % slen] + 1
    print(p)


main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import insort_right as ir
from collections import defaultdict

s = input()
t = input()
len_s = len(s)

index = defaultdict(list)
for i, c in enumerate(s):
    ir(index[c], i)

ans = 0
now = 0
for c in t:
    if not index[c]:
        print('-1')
        break
    idx = bl(index[c], now)
    if idx == len(index[c]):
        ans += len_s
        now = index[c][0] + 1
    else:
        now = index[c][idx] + 1
else:
    print(ans + now)

Submission status: Accepted

Solution code:
from bisect import bisect_left

s = input()
t = input()

n = len(s)

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

for i, x in enumerate(s + s):
    c[ord(x) - ord('a')].append(i)

ans = 0
p = -1
for x in t:
    d = ord(x) - ord('a')
    if len(c[d]) == 0:
        print(-1)
        exit()
    p = c[d][bisect_left(c[d], p+1)]
    if p >= n:
        p -= n
        ans += 1

print(ans * n + p + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right
s = input()
t = input()
ss = set(s)
tt = set(t)
count = 0
for i in tt:
  if not i in ss:
    print(-1)
    break
else:
  dic = defaultdict(list)
  for i in range(len(s)):
    dic[s[i]] += [i+1]
  ans = 0
  for i in range(len(t)):
    x = ans%len(s)
    if dic[t[i]][-1]<=x:
      ans = ans - x + len(s) + dic[t[i]][0]
    else:
      ind = bisect_right(dic[t[i]], x)
      ans = ans - x + dic[t[i]][ind]
  print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
import bisect
s = raw_input()
t = raw_input()
p, e, n = 0, 1, len(s)
ss = set(s)
idx = collections.defaultdict(list)
for i in xrange(n):
    idx[s[i]].append(i)
# print(idx)
for tt in t:
    q = p % n
    if not tt in idx:
        e = 0
        break
    indexs = idx[tt]
    # print(bisect.bisect(indexs, q), indexs)
    res = bisect.bisect_left(indexs, q)
    p += indexs[res] - q + 1 if res < len(indexs) else -q + n + indexs[0] + 1
print((p+1)*e-1)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    import bisect
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    t = str(input().rstrip('\n'))
    d = collections.defaultdict(list)
    for i in range(len(s)):
        d[s[i]] += [i]
    loop = 0
    cur = 0
    for i in range(len(t)):
        p = bisect.bisect_left(d[t[i]], cur)
        if p == 0 and len(d[t[i]]) == 0:
            print(-1)
            exit()
        elif p == len(d[t[i]]):
            loop += 1
            cur = d[t[i]][0] + 1
        else:
            cur = d[t[i]][p] + 1
    print(len(s) * loop + cur)


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

ind_dict = {i : [] for i in t}
for i, _s in enumerate(s):
    if _s in t:
        ind_dict[_s] += [i]

def get_least(last, s, dic):
    ls = dic[s]
    ind = bisect.bisect_right(ls, last)
    if ind >= len(ls):
        return ls[0]
    else:
        return ls[ind]

if -1 in [s.find(_t) for _t in t]:
    print(-1)
else:
    cnt = 0
    last = get_least(-1, t[0], ind_dict)
    _next = last
    for _t in t[1:]:
        _next = get_least(last, _t, ind_dict)
        if _next <= last:
            cnt += 1
        last = _next
    print(cnt * len(s) + _next + 1)

Submission status: Accepted

Solution code:
from bisect import bisect

S = input()
T = input()
N = len(S)
# Sにおいてある文字が出てくる位置を調べる
idxs_S = [[] for _ in range(26)] # a~zの分
for i, c in enumerate(S):
    idx = ord(c) - ord("a")
    idxs_S[idx].append(i)

# Tに出てくる文字がSになければ無理
for c in set(T):
    if len(idxs_S[ord(c) - ord("a")]) == 0:
        print(-1)
        exit()

cnt_all_S = 0
idx_c = -1
for c in T:
    tmp = ord(c) - ord("a")
    idx = bisect(idxs_S[tmp], idx_c)
    if idx == len(idxs_S[tmp]): # 現行のSにこれ以上使えるcがない場合、新たにSを連結してその中からcを取り出す
        idx_c = idxs_S[tmp][0] # Sの中の初めのcの位置まで
        cnt_all_S += 1
    else:
        idx_c = idxs_S[tmp][idx]

print(N*cnt_all_S + idx_c + 1)

Submission status: Accepted

Solution code:
slist = input()
tlist = input()
scounter = 0
slength=len(slist)
slist=slist+slist
preposition=-1
for tchar in tlist:
    preposition=slist.find(tchar, preposition+1)
    if preposition==-1:
        scounter=-1
        break
    elif preposition>=slength:
        scounter+=slength
        preposition-=slength
    # print(tchar, scounter, preposition)
if (scounter==-1):
    print(scounter)
else:
    print(scounter+preposition+1)

Submission status: Accepted

Solution code:
import sys

s = input()
t = input()
s_len = len(s)
t_len = len(t)
index_list = [0]*t_len
rt1 = 0
rt2 = 0
s = s + s
for m in range(t_len):
	rt1 = s.find(t[m],rt1)
	if rt1 == -1:
		print(rt1)
		sys.exit()
	else:
		#rt1 = rt1 % s_len + 1
		#index_list[m] = rt1
		if rt1 < s_len:
			pass
		else:
			rt1 = rt1 % s_len
			rt2 += 1
	rt1 += 1
rt = rt1 + rt2 * s_len
print(rt)

Submission status: Accepted

Solution code:
s=input()
t=input()
ans1=0
ans2=0
m=len(s)
n=len(t)
s=s+s
for i in range(n):
  a=s.find(t[i],ans2)
  if a==-1:
    print(-1)
    exit()
  if a>=m:
    ans1+=1
  ans2=a%m+1
print((ans1*m)+ans2)

Submission status: Accepted

Solution code:
import sys
import bisect

s = input()
t = input()

dic = {}

for i, c in enumerate(s):
    if c not in dic:
        dic[c] = []
        
    dic[c].append(i)

currentIndex = -1
roop = 0

for c in t:
    if c not in dic:
        print(-1)
        sys.exit()
    
    if currentIndex >= dic[c][-1]:
        roop += 1
        currentIndex = dic[c][0]
    else:
        index =  bisect.bisect_right(dic[c], currentIndex)
        currentIndex = dic[c][index]

result = (roop * len(s)) + currentIndex + 1
print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
s = input()
t = input()
ls = len(s)
dbls = s*2
idx = 0
ans = 0
dic = defaultdict(list)

for i, c in enumerate(dbls):
    dic[c] += [i+1]

for c in t:
    if not c in dic.keys():
        print(-1)
        exit()
    lst = dic[c]
    i = bisect.bisect_right(lst, idx)
    idx = lst[i]
    if idx > ls:
        ans += ls
        idx -= ls
    else:
        idx = lst[i]

if not idx == 0:
    ans += idx
print(ans)

Submission status: Accepted

Solution code:
S=input();T=input();p=0;e=1
for s in T:
  q=p%len(S)
  if not s in S:e=0;break
  if s in S[q:]:p+=S[q:].index(s)+1
  else:p+=S.index(s)+len(S[q:])+1
print((p+1)*e-1)

Submission status: Accepted

Solution code:
s = str(input().strip())
t = str(input().strip())

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

for i, v in enumerate(s):
    pos[ord(v) - ord('a')].append(i + 1)

pre = 0
ans = 0
from bisect import bisect_right

for i in t:
    g = ord(i) - ord('a')
    p = bisect_right(pos[g], pre)
    if p >= len(pos[g]):
        if len(pos[g]):
            ans += len(s)
            pre = pos[g][0]
            continue
        else:
            print(-1)
            exit(0)
    pre = pos[g][p]

ans += pre
print(ans)

Submission status: Accepted

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

s_ = s[:]

ti = 0
ans = 0
flag = True

while ti < len(t):
    si = s_.find(t[ti])
    
    if si != -1:
        ans += si + 1
        s_ = s_[si+1:]
        ti += 1
        flag = False
    else:
        if flag:
            print(-1)
            exit(0)
        ans += len(s_)
        s_ = s[:]
        flag = True
        
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
# import numpy as np
import bisect #bisect.bisect_left 値の挿入位置を返す関数


s = input()
t = input()
l = len(s)

idx_dict = defaultdict(list)

#各文字の index を取得
for i, v in enumerate(s):
    idx_dict[v].append(i)

#リストを ndarray に変換
#for key, value in idx_dict.items():
#    idx_dict[key] = np.array(value)

l = len(s)
rnd = 0
idx = 0
ans = 0
p_v = ''
# index のリストを取り出し、現在の idx と比べる
# idx より大きい値がない場合は一周ふやす
for v in t:
    # idx_dict の key に　v が存在しなかったら -1
    if v not in idx_dict:
        ans = -1
        break
    # 同じ文字が続いたら idx を 1 増やす
    if v == p_v:
        idx += 1
    arr = idx_dict[v]
    i = bisect.bisect_left(arr, idx)
    try:
        idx = arr[i]
    except IndexError:
        idx = arr[0]
        rnd += 1
    p_v = v

if not ans:
        ans = ((rnd * l) + idx) + 1
        
print(ans)

Submission status: Accepted

Solution code:
import bisect
S = input()
T = input()
D = [[] for _ in range(26)]
for i in range(26):
  D[i] = [0] * S.count(chr(97 + i))
P = [0] * 26
for i, s in enumerate(S):
  n = ord(s) - 97
  D[n][P[n]] = i + 1
  P[n] += 1
pos = 0
loop = 0
for t in T:
  n = ord(t) - 97
  if D[n] == []:
    print(-1)
    break
  _d = bisect.bisect(D[n], pos)
  _pos = D[n][_d % len(D[n])]
  if _pos <= pos:
    loop += 1
  pos = _pos
else:
  print(len(S) * loop + pos)