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()
T = input()

s_set = set(list(S))
t_set = set(list(T))

if not t_set <= s_set:
    print(-1)
    exit()


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


now_position = -1
t_position = [-1] * len(T)
for i, t in enumerate(T):
    ti = bisect_right(s_position[t], now_position)
    if ti >= len(s_position[t]):
        ti = 0

    t_position[i] = s_position[t][ti]
    now_position = s_position[t][ti]

ans = 0
for i in range(len(T) - 1):
    if t_position[i] >= t_position[i + 1]:
        ans += len(S)

print(ans + t_position[-1] + 1)

Submission status: Accepted

Solution code:
from bisect import bisect_left

s = input()
t = input()
ls, lt = len(s), len(t)

exsist = [[] for _ in range(26)]
for i in range(ls) :
    exsist[ord(s[i])-97].append(i)

ret = 0
now = -1
for i in range(lt) :
    ot = ord(t[i])-97
    if len(exsist[ot]) == 0 :
        print('-1')
        break
    
    a = bisect_left(exsist[ot], now + 1)
    if a == len(exsist[ot]) :
        ret += ls
        now = exsist[ot][bisect_left(exsist[ot], -1)]
    else :
        now = exsist[ot][a]
        
else :
    print(ret+now+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import *

def main():
    idx = defaultdict(list)
    s = input()
    t = input()
    if not set(t) <= set(s):
        print(-1)
        exit()
    for i, c in enumerate(s):
        idx[c] += [i]
    pre = -1
    roop = 0
    for c in t:
        koho = idx[c]
        ki = bisect_left(koho, pre + 1)
        if ki < len(koho):
            pre = koho[ki]
        else:
            pre = koho[0]
            roop += 1
    print(len(s) * roop + pre + 1)

main()

Submission status: Accepted

Solution code:
s = input()
t = input()
N = len(s)
s2 = s + s
cs = set(t)
#print(cs)
table = {}
for c in cs:
  if s.find(c) < 0:
    table[c] = [-1]*N
    continue
  l = [-2] * N
  p = 0
  while p < N:
    i = s2.find(c, p)
    while p <= i:
      if p < N:
        l[p] = i-p
      p += 1
  table[c] = l
#print(table)
r = 0
for c in t:
  d = table[c][r%N]
  if d < 0:
    print(-1)
    exit()
  r += d+1
print(r)

Submission status: Accepted

Solution code:
import bisect


def solve(s, t):
    indexes = {}
    for i, c in enumerate(s):
        indexes.setdefault(c, []).append(i)
    index = 0
    loop_count = 0
    for c in t:
        if c not in indexes:
            return -1
        else:
            found_i = bisect.bisect_left(indexes[c], index)
            if found_i == len(indexes[c]):
                loop_count += 1
                index = indexes[c][0] + 1
            else:
                index = indexes[c][found_i] + 1
    return index + loop_count * len(s)

if __name__ == "__main__":
    s = input()
    t = input()
    print(solve(s, t))

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()

se = set(list(s))
for ti in t:
    if not ti in se:
        print(-1)
        exit()

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

ans = 0
now = 0
for i, ti in enumerate(t):
    j = bisect.bisect_left(word[ord(ti) - ord('a')], now)
    if j < len(word[ord(ti) - ord('a')]):
        j = word[ord(ti) - ord('a')][j]
        ans += j - now + 1
        now = (j + 1) % len(s)
    else:
        ans += len(s) - now
        now = 0
        j = bisect.bisect_left(word[ord(ti) - ord('a')], 0)
        j = word[ord(ti) - ord('a')][j]
        ans += j - now + 1
        now = j + 1


print(ans)

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(T[i],chardict[T[i]],nowpoint,tmp,chardict[T[i]][tmp],cycle,dp[i+1])
print(dp[M]+1)
#print(dp)

Submission status: Accepted

Solution code:
S = input()
T = input()
N = len(S)
def calc(s):
    ret = [0] * 26
    for ss in s:
        ret[ord(ss)-97] += 1
    return ret

X = calc(S)
Y = calc(T)
ma = 0
for i in range(26):
    ma = max(ma, -(-Y[i]//X[i])-1 if X[i] else (1<<100 if Y[i] else 0))
A = [i for i in range(26) if Y[i]]
if ma == 1<<100:
    print(-1)
else:
    NE = [[-1] * N for _ in range(26)]
    for a in A:
        b = -1
        for i in list(range(N)[::-1])*2:
            if NE[a][i] >= 0:
                break
            if b >= 0:
                NE[a][i] = b
            if ord(S[i]) - 97 == a:
                b = i
    ans = 0
    i = -1
    for t in T:
        ni = NE[ord(t)-97][i]
        ans += ni - i + (N if ni <= i else 0)
        i = ni
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left,bisect_right
S = input()
T = input()

s_map = defaultdict(list)

for i, s in enumerate(S + S):
    s_map[s].append(i + 1)

ans = 0
current_index = 0
for t in T:
    if not s_map[t]:
        print(-1)
        exit()

    index = bisect_right(s_map[t],current_index)
    current_index = s_map[t][index]
    # print(current_index,ans)
    if current_index > len(S):
        ans += current_index // len(S) * len(S)
        current_index = current_index % len(S)


print(ans + current_index)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_left

s = str(input())
t = str(input())

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

i = 0
n = 1
for ch in t:
    temp = d[ch]
    if temp == []:
        print(-1)
        exit()
    place = bisect_left(temp,i)
    if place==len(temp):
        n += 1
        i = temp[0]+1
    else:
        i = temp[place]+1

print((n-1)*len(s)+i)

Submission status: Accepted

Solution code:
a_code = ord("a")

s = [ord(c) - a_code for c in input().strip()]
t = [ord(c) - a_code for c in input().strip()]

tl = len(t)
sl = len(s)

s_table = [None] * sl
index_table = [None] * 26
for i in range(sl - 1, -1, -1):
	c = s[i]
	index_table[c] = i
	s_table[i] = list(index_table)

ti = 0
si = 0
count = 0
found = False
while ti < tl:
	c = t[ti]
	index = s_table[si][c]
	if index != None:
		ti += 1
		count += index + 1 - si
		si = index + 1
		found = True
		if si >= sl:
			if not found:
				count = -1
				break
			found = False
			si = 0
	else:
		if not found:
			count = -1
			break
		found = False
		count += sl - si
		si = 0
print(count)

Submission status: Accepted

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

def main():
    # N = int(input())
    # N, K = map(int, input().split())
    # a = list(map(int, input().split()))
    s = input().strip()
    t = input().strip()
    len_s = len(s)

    dic = {}
    for i in range(len_s):
        if s[i] in dic:
            dic[s[i]].append(i)
        else:
            dic[s[i]] = [i]
    # print(dic)
    ok = True
    now = 0
    ans = 0
    for i in range(len(t)):
        if t[i] not in dic:
            ok = False
            break
        else:
            index = bisect.bisect_left(dic[t[i]], now)
            # print(index)
            if index >= len(dic[t[i]]):# １週回ってからしかない
                # print("plus")
                ans += len_s
                now = dic[t[i]][0]+1
            else:# １週回るまでに見つかった
                now = dic[t[i]][index]+1
            # print(now)
            # if i == len(t)-1:
            #     if ans != 0:
            #         now -= 1
    if ok:
        print(ans+now)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

s = input()
N = len(s)
t = input()


d = {chr(i + ord('a')): [] for i in range(26)}

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

acc = 0
b = 0
for c in t:
    if len(d[c]) == 0:
        acc = -1
        break
    q = bisect_right(d[c], b)
    a = d[c][q if q != len(d[c]) else 0]
    if a > b:
        acc, b = acc + a - b, a
    else:
        acc, b = acc + N - b + a, a

print(acc)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from bisect import bisect_left

S = input().rstrip()
T = input().rstrip()

LS = len(S)

index = defaultdict(list) # alphabet to indices

for i,s in enumerate(S):
    index[s].append(i)

index

x = -1 # 今見た場所。次はx+1以上からとる。
for t in T:
    arr = index[t]
    if len(arr) == 0:
        x = -2
        break
    y = (x+1)%LS
    i = bisect_left(arr,y)
    if i < len(arr):
        next_x = (x+1) + arr[i] - y
    else:
        next_x = (x+1) + arr[0] - y + LS
    x = next_x

answer = x+1
print(answer)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from collections import Counter
from itertools import accumulate
def main():
    s = input()
    t = input()
    S = Counter(s)
    T = Counter(t)
    N = len(t)
    M = len(s)
    d = dict()
    for i in range(26):
        d[ chr( ord("a") + i)] = i
    for key in T:
        if S[key] == 0:
            print(-1)
            return
    Al = [[0]*M for _ in range(26)]
    a = ord("a")
    for i in range(M):
        Al[d[s[i]]][i] = 1
    Ac = [[0]*M for _ in range(26)]
    for i in range(26):
        now = -1
        for j in range(M-1,-1,-1):
            Ac[i][j] = now
            if Al[i][j] == 1:
                now = j
    ans = 1
    for i in range(M):
        if t[0] == s[i]:
            now = i
            break
    first = d[s[0]]
    for cnt in range(1,N):
        g = d[t[cnt]]
        if Ac[g][now] == -1:
            ans += 1
            if g == first:
                now = 0
            else:
                now = Ac[g][0]
        else:
            now = Ac[g][now]
    print(M*(ans-1)+now+1)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

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

    if len(set(t) - set(s)) > 0:
        print(-1)
        sys.exit()

    abc_123_dic = defaultdict(int)
    for i in range(26):
        aaa = chr(97 + i)
        abc_123_dic[aaa] = i + 1
        abc_123_dic[i + 1] = aaa


    str_dic = [[] for i in range(27)]

    for i in range(len(s)):
        now_ind = abc_123_dic[s[i]]
        str_dic[now_ind].append(i + 1)


    ans_list = [0 for i in range(len(t))]
    pre_ind = 0
    for i in range(len(t)):
        now_str = t[i]
        now_ind = abc_123_dic[now_str]
        insert_ind = bisect.bisect_right(str_dic[now_ind], pre_ind)
        if insert_ind == len(str_dic[now_ind]):
            ans_list[i] = str_dic[now_ind][0]
        else:
            ans_list[i] = str_dic[now_ind][insert_ind]
        pre_ind = ans_list[i]

    pre_ind = 0
    ans = 0
    # print(ans_list)
    for i in range(len(t)):
        if pre_ind >= ans_list[i]:
           ans += len(s)
        pre_ind = ans_list[i]
        # print(ans)
    ans += ans_list[len(t) - 1]
    print(ans)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect


s = input()
t = input()

memo = {}
alph = "abcdefghijklmnopqrstuvwxyz"

for i, char in enumerate(alph):
    memo[char] = i

li = [[] for i in range(26)]
for i, char in enumerate(s):
    li[memo[char]].append(i)

ans = 0
now_here = -1
# for i, char in enumerate(t):
i = 0
while i < len(t):
    char = t[i]
    if not li[memo[char]]:
        print(-1)
        exit()
    if now_here < li[memo[char]][0]:
        now_here = li[memo[char]][0]
        i += 1
    elif now_here < li[memo[char]][-1]:
        now_here = li[memo[char]][bisect.bisect_right(li[memo[char]], now_here)]
        i += 1
    else:
        ans += 1
        now_here = -1
print(ans*len(s) + now_here + 1)

Submission status: Accepted

Solution code:
import unittest
import collections
import bisect


def solve(s, t):
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)
    i = 0
    n = 0
    for c in t:
        if len(d[c]) == 0:
            return - 1
        k = bisect.bisect_left(d[c], i)
        if k == len(d[c]):
            n += 1
            k = bisect.bisect_left(d[c], 0)
        i = d[c][k]+1
    return len(s)*n+i


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


class TestAbc138_e(unittest.TestCase):
    def test_abc138_e(self):
        self.assertEqual(solve('contest', 'son'), 10)
        self.assertEqual(solve('contest', 'programming'), -1)
        self.assertEqual(solve('contest', 'sentence'), 33)
        self.assertEqual(solve('abc', 'abccccac'), 15)


if __name__ == "__main__":
    # unittest.main()
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect
s = input()
t = input()
d = defaultdict(list)
for i in range(len(s)):
    d[s[i]].append(i)
for i in range(len(s)):
    d[s[i]].append(d[s[i]][0]+len(s))

ans = 0
idx = -1
for i in range(len(t)):
    if d[t[i]] == []:
        ans = -1
        break
    idx = d[t[i]][bisect(d[t[i]],idx)]
    if idx >= len(s):
        ans += 1
        idx %= len(s)
if ans != -1:
    ans *= len(s)
    ans += idx+1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
S = input()
T = input()
Ns = len(S)
S = S + S
ABC = [[] for _ in range(26)]
for i, s in enumerate(S):
    s = ord(s) - 97
    ABC[s].append(i)
ans = 0
l_s = 0
for t in T:
    t = ord(t) - 97
    abc = ABC[t]
    l = bisect_left(abc, l_s)
    if l == len(abc):
        print(-1)
        exit()
    l_s = abc[l]
    l_s += 1
    #print(l_s)
    if l_s >= Ns:
        ans += Ns
        l_s -= Ns
print(ans + l_s)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right
S=input()
T=input()
ls=len(S); lt=len(T)
S_dict=defaultdict(list)
for i,s in enumerate(S):
    S_dict[s].append(i+1)
T_list=[[] for _ in range(lt)]
for i,t in enumerate(T):
    if not S_dict[t]:
        print(-1)
        exit()
    T_list[i]=S_dict[t]
#print(T_list)
ans=T_list[0][0]
prev=T_list[0][0]
cycles=0
#print(ans)
for i in range(1,lt):
    idx=bisect_right(T_list[i],prev)
    if idx==len(T_list[i]):
        cycles+=1
        prev=T_list[i][0]
    else:
        prev=T_list[i][idx]
    ans=prev+(cycles*ls)
    #print(prev,cycles,ans)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def solve(s,t):
    indices = [list() for _ in range(26)]
    for i,v in enumerate(s):
        indices[v].append(i)

    loop = 0
    cur = 0
    for c in t:
        l = indices[c]

        if not l:
            loop = 0
            cur = -1
            break
        if l[-1] < cur:
            cur = l[0]+1
            loop += 1
        else:
            cur = l[bisect_left(l, cur)]+1
            if cur == len(s):
                loop += 1
                cur = 0
    return loop*len(s)+cur

s,t = input(),input()
s = [ord(v)-ord('a') for v in s]
t = [ord(v)-ord('a') for v in t]
print(solve(s,t))

Submission status: Accepted

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

def bs(tl, i, l, r):
  while l < r:
    mid = (l + r) // 2
    if tl[mid] <= i:
      l = mid + 1
    else:
      r = mid
  return r


def main():
  s = input().strip()
  t = input().strip()
  sd = defaultdict(lambda: [])
  for i, _s in enumerate(s):
    sd[_s].append(i)

  for k, v in sd.items():
    sd[k] = list(sorted(v))

  ans = 0
  prev = -1
  for _t in t:
    if _t not in sd:
      break
    else:
      idx = bs(sd[_t], prev, 0, len(sd[_t]))
      if idx == len(sd[_t]):
        idx = sd[_t][0]
      else:
        idx = sd[_t][idx]
      if idx <= prev:
        ans += len(s) - prev + idx
      else:
        ans += idx - prev
      prev = idx
  else:
    print(ans)
    sys.exit(0)

  print(-1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
s=input()
t=input()
n=len(s)
import bisect
import collections
Chk=[False]*26
Fst=collections.defaultdict(int)
Pos=collections.defaultdict(list)
for i in range(n):
  ss=s[i]
  ns=ord(ss)-97
  if not Chk[ns]:
    Fst[ss]=i+1
    Chk[ns]=True
  Pos[ss]+=[i+1]
ans=0
prev=0
for i in range(len(t)):
  tt=t[i]
  if Fst[tt]==0:
    ans=-1
    break
  else:
    f,l=Fst[tt],Pos[tt][-1]
    if prev>=l:
      ans+=n-prev+f
      prev=f
    else:
      P=Pos[tt]
      next=P[bisect.bisect_right(P,prev)]
      ans+=next-prev
      prev=next
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import bisect

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

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

poslen = [len(p) for p in pos]

syu = 0
tmp = -1
fin = False
for c in t:
    tgt = pos[ord(c) - ord("a")]
    tlen = poslen[ord(c) - ord("a")]
    if not tgt:
        print(-1)
        sys.exit()
    else:
        ins = bisect.bisect_left(tgt, tmp+1)
        if ins == tlen:
            syu += 1
            tmp = tgt[0]
            fin = True
        else:
            # print(c, tgt, ins)
            tmp = tgt[ins]
            fin = False

        # print(c, syu, tmp)
# if fin:

print(syu*n + tmp + 1)

Submission status: Accepted

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

s_dic = defaultdict(lambda: [])

for i, s in enumerate(S):
    s_dic[s].append(i)

start_index = -1
repeat_count = 0

T = input()
for t in T:
    if t not in s_dic:
        print(-1)
        exit()
    next_index = bisect.bisect_right(s_dic[t], start_index)
    if next_index == len(s_dic[t]):
        repeat_count += 1
        start_index = s_dic[t][0]
    else:
        start_index = s_dic[t][next_index]

print(repeat_count*len(S) + start_index + 1)

Submission status: Accepted

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

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

L=len(s)

NLIST=[[float("inf")]*26 for i in range(2*L+1)]

s2=s*2

for i in range(2*L-1,-1,-1):
    for j in range(26):
        if j==ord(s2[i])-97:
            NLIST[i][j]=i
            continue
            
        NLIST[i][j]=NLIST[i+1][j]
        


NOW=-1
ANS=0
for al in t:
    x=NLIST[NOW+1][ord(al)-97]
    if x==float("inf"):
        print(-1)
        sys.exit()

    else:
        ANS+=(x-NOW)
        NOW=x%L

print(ANS)

Submission status: Accepted

Solution code:
from bisect import bisect
S = input()
T = input()

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

for c in set(T):
    if not cs[ord(c) - ord('a')]:
        print(-1)
        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]

print(rnd*len(S) + k + 1)

Submission status: Accepted

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

ct = 0
k = 0
for i in t:
    f = s.find(i, k)
    if f < 0:
        ct += 1
        f = s.find(i)
        if f == -1:
            print(-1)
            break
        else:
            k = f+1
    else:
        k = f+1
else:
    print(ct*len(s)+k)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

s, t = input(), input()
se = set(s)
for c in t:
    if c not in se:
        print(-1)
        exit()
dic = defaultdict(list)
for i, c in enumerate(s, 1):
    dic[c].append(i)
n = len(s)
i = ans = dic[t[0]][0]
for c in t[1:]:
    dicc = dic[c]
    j = bisect_right(dicc, i)
    if len(dic[c]) <= j:
        ans += n-i+dicc[0]
        i = dicc[0]
    else:
        ans += dicc[j]-i
        i = dicc[j]
print(ans)

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))
	#print(alph)
	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:
S = [ord(s)-97 for s in input().strip()]
T = [ord(t)-97 for t in input().strip()]

ls = len(S)

inf = 2*10**9

table = [None]*(2*ls)

ss = S + S
t = [inf]*26
for i in range(2*ls-1, -1, -1):
    z = ss[i]
    t[z] = i
    table[i] = t[:]

if any(table[0][ti] == inf for ti in T):
    print(-1)

else:
    ans = -1
    for ti in T:
       j = ans%ls
       k = table[j+1][ti] % ls
       if j < k:
           ans += k - j
       else:
           ans += ls + k - j
    print(ans + 1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    d = defaultdict(lambda : [])
    for i in range(n):
        d[s[i]].append(i)
    f = [-1]*m
    alp = list("abcdefghijklmnopqrstuvwxyz")
    for i in range(m):
        if not d[t[i]]:
            print(-1)
            return
        j = bisect.bisect_right(d[t[i]],f[i-1])
        if j == len(d[t[i]]):
            f[i] = d[t[i]][0]
        else:
            f[i] = d[t[i]][j]
    ans = 0
    for i in range(m-1):
        if f[i] >= f[i+1]:
            ans += 1
    print(ans*n+f[-1]+1)
    return

#F
def F():

    return

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

Submission status: Accepted

Solution code:
import bisect
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]
c = 0
cur = -1
for i in t:
  if i not in d:
    print(-1)
    exit()
  if cur < d[i][-1]:
    cur = d[i][bisect.bisect_right(d[i],cur)]
    continue
  else:
    cur = d[i][0]
    c += 1
print(c*len(s)+cur+1)

Submission status: Accepted

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

cs = Counter(s)
ct = Counter(t)

ok = 1
for k in ct:
    if k not in cs:
        ok = 0
if not ok:
    print("-1")
    exit(0)

N = len(s)
D = [-1]*26
E = [None]*(N+1)
cA = ord('a')
for i in range(N-1, -1, -1):
    E[i+1] = D[:]
    D[ord(s[i])-cA] = i
E[0] = D

ans = 0
p = -1
for c in t:
    v = ord(c) - cA
    q = E[p+1][v]
    if q == -1:
        q = E[0][v]
        ans += q + (N - p)
    else:
        ans += (q - p)
    p = q
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
from heapq import heapify, heappop, heappush
from string import ascii_lowercase as abc
from bisect import bisect
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)
from fractions import gcd
def inpl(): return list(map(int, input().split()))

S = input()
T = input()

D = {k:[] for k in abc}
for i in range(len(S)):
    D[S[i]].append(i)

rap = 0
ix = -1

for j in range(len(T)):
    t = T[j]
    if len(D[t]) == 0:
        print(-1)
        break
    k = bisect(D[t], ix)
    if k == len(D[t]):
        rap += 1
        ix = D[t][0]
    else:
        ix = D[t][k]
else:
    print(len(S)*rap + ix+1)

Submission status: Accepted

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

n = len(s)

p = [[] for _ in range(26)]
for i in range(n):
    p[ord(s[i])-97].append(i+1) 


res = 0
b = 0
for e in t:
    k = ord(e)-97
    if len(p[k]) == 0:
        print(-1)
        exit()
    else:
        r = bisect.bisect_right(p[k],b)
        if len(p[k]) > r:
            res += p[k][r]-b
            b = p[k][r]
        else:
            res += n-b+p[k][0]
            b = p[k][0]

print(res)

Submission status: Accepted

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

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

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

cnt = 1

prev = -1
i = 0 
while(i < len(t)):
	l = t[i]
	indi = ord(l) - ord('a')
	li = a[indi]

	if(li == []):
		print(-1)
		exit(0)

	if li[-1] <= prev:
		prev = -1
		cnt += 1

	start = 0
	end = len(li) - 1
	ans = -1
	while(start <= end):
		mid = (start + end)//2
		if li[mid] > prev:
			ans = mid
			end = mid - 1
		else:
			start = mid + 1
	# print(l,ans,li)
	prev = li[ans]

	i += 1

# print(cnt,prev)
final = cnt*len(s) - (len(s) - prev - 1)
print(final)

Submission status: Accepted

Solution code:
import bisect
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

S = sys.stdin.readline().rstrip()
T = sys.stdin.readline().rstrip()

pos = defaultdict(list)
for i, c in enumerate(S):
    pos[c].append(i)
for c in pos.keys():
    pos[c] += [p + len(S) for p in pos[c]]

ans = 0
i = 0
for t in T:
    if not pos[t]:
        print(-1)
        exit()
    p = bisect.bisect_left(pos[t], i)
    ans += pos[t][p] - i + 1
    i = pos[t][p] % len(S) + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

S = input()
T = input()

ALPs = defaultdict(list)

for i,s in enumerate(S):
    ALPs[s].append(i+1)

Ls = [len(ALPs[chr(i)]) for i in range(97,97+28)]


itr = 0
cnt = 0 # 周回数
for t in T:
    L = Ls[ord(t)-97]
    if L == 0:
        print(-1)
        exit()
    else:
        ind = bisect.bisect_right(ALPs[t],itr)
        if ind == L:
            itr = ALPs[t][0]
            cnt += 1
        else:
            itr = ALPs[t][ind]
        #print(ALPs[t],ind,itr)


ans = cnt*len(S) + itr

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

s = ns()
t = ns()

hey = set(list(s))
for c in t:
    if c not in hey:
        print(-1)
        sys.exit(0)

n = len(s)
nex = [[n] * 26 for _ in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(26):
        nex[i][j] = nex[i+1][j]
    nex[i][ord(s[i])-ord("a")] = i

ans = 0
pos = 0
for i in range(len(t)):
    v = ord(t[i]) - ord("a")
    ne = nex[pos][v]
    ans += ne - pos + 1
    if ne == n:
        ne = nex[0][v]
        ans += ne
    pos = ne + 1
print(ans)