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: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    s = input()
    s = [ord(i) - ord("a") for i in s]
    N = len(s)
    t = input()
    t = [ord(i) - ord("a") for i in t]

    posit = {}
    for i in range(0, ord("z")-ord("a")+1):
        posit[i] = []

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

    ans = 0
    cur = -1
    for src_target in t:
        if not posit[src_target]:
            return -1
        if posit[src_target][-1] <= cur: # 使い捨て処理
            ans += (N-cur)
            cur = 0
            #print("a", ans)
        idx = bisect_left(posit[src_target], cur) # 次のがあるindexを探す
        next = posit[src_target][idx]
        ans += next - cur
        cur = next
        #print(ans, src_target)

    return ans



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    s = input()
    s = [ord(i) - ord("a") for i in s]
    N = len(s)
    t = input()
    t = [ord(i) - ord("a") for i in t]

    posit = {}
    for i in range(0, ord("z")-ord("a")+1):
        posit[i] = []

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

    ans = 0
    cur = -1
    for src_target in t:
        if not posit[src_target]:
            return -1
        if posit[src_target][-1] < cur: # 使い捨て処理
            ans += (N-cur)
            cur = 0
            #print("a", ans)
        idx = bisect_left(posit[src_target], cur) # 次のがあるindexを探す
        next = posit[src_target][idx]
        ans += next - cur
        cur = next
        #print(ans, src_target)

    return ans



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans1=0
ans2=0

ss=s*2

for i in range(len(t)):
    a=ss.find(t[i],ans2)
    if a==-1:
        ans=-1
        break
    if a>=len(s):
        ans1+=1
    ans2=a%(len(s))+1
ans=ans1*len(s)+ans2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
s = list(input())
t = list(input())
ls = len(s)
check = [[] for i in range(26)]
for i in range(len(s)):
    o = ord(s[i])-ord("a")

    check[o].append(i+1)
ans = 0
count = [0 for i in range(26)]
c1 = 0

for i in t:
    o =ord(i)-ord("a")
    if check[o]:
        com = False
        lo = len(check[o])
        for j in range(lo):
            if j+count[o] == lo:
                break
            x = j+count[o]
            if ans < check[o][x]:
                ans = check[o][x]
                count[o] = x
                com = True
                break   
        if not com:
            c1 += 1
            ans = check[o][0]
            count[o] = 0 

    else:
        print(-1)
        exit()
 
print(ans+c1*ls)

Submission status: Wrong Answer

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

t = list(input())
ls = len(s)
check = [[] for i in range(26)]
for i in range(len(s)):
    o = ord(s[i])-ord("a")

    check[o].append(i+1)
ans = 0
count = [0 for i in range(26)]
c1 = 0

for i in t:
    o =ord(i)-ord("a")
    if check[o]:
        com = False
        lo = len(check[o])
        for j in range(lo):
            if j+count[o] == lo:
                break
            x = j+count[o]
            if ans < c1*len(s)+check[o][x]:
                ans = c1*len(s)+check[o][x]
                count[o] = x
                com = True
                break   
        if not com:
            c1 += 1
            for j in range(lo):
                if ans < c1*len(s)+check[o][j]:
                    ans = c1*len(s)+check[o][j]
                    count[o] = j
    
                    break 

    else:
        print(-1)
        exit()
 
print(ans)

Submission status: Wrong Answer

Solution code:
sl = list(input())
tl = list(input())
n = len(sl)
from collections import defaultdict
dic = defaultdict(list)

for idx, s in enumerate(sl):
    dic[s].append(idx)
    dic[s].append(idx + n)

for s in dic:
    dic[s] = sorted(dic[s])

import bisect
ans = 1
now = 0
for t in tl:
    if dic[t] == []:
        print(-1)
        exit()
    idx = bisect.bisect_right(dic[t], now)
    ans += dic[t][idx] - now
    now = dic[t][idx]
    now %= n

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
s = list(input())
t = list(input())
ls = len(s)
check = [[] for i in range(26)]
for i in range(len(s)):
    o = ord(s[i])-ord("a")

    check[o].append(i+1)
ans = 0
count = [0 for i in range(26)]
c1 = 0
for i in t:
    o =ord(i)-ord("a")
    if check[o]:
        com = False
        lo = len(check[o])
        for j in range(lo):
            if j+count[o] >= lo:
                c1 += 1
                count[o] = -j
            if ans < c1*len(s)+check[o][j+count[o]]:
                ans = c1*len(s)+check[o][j+count[o]]
                count[o] += j
                com = True
                break   
        if not com:
            c1 += 1
            for j in range(lo):
                if ans < c1*len(s)+check[o][j]:
                    ans = c1*len(s)+check[o][j]
                    count[o] = j
                    com = True
                    break   

    else:
        print(-1)
        exit()
    
print(ans)

Submission status: Wrong Answer

Solution code:
sl = list(input())
tl = list(input())
n = len(sl)
from collections import defaultdict
dic = defaultdict(list)

for idx, s in enumerate(sl):
    dic[s].append(idx)
    dic[s].append(idx + n)

for s in dic:
    dic[s] = sorted(dic[s])

import bisect
ans = 1
now = 0
for t in tl:
    if dic[t] == []:
        print(-1)
        exit()
    idx = bisect.bisect_left(dic[t], now)
    ans += dic[t][idx] - now
    now = dic[t][idx]
    now %= n

print(ans)

Submission status: Wrong Answer

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

check = [[] for i in range(26)]
for i in range(len(s)):
    o = ord(s[i])-ord("a")

    check[o].append(i+1)

tl = Counter(t)

ans = 0
count = 0
for i in t:
    o =ord(i)-ord("a")
    if check[o]:
        c = False
        for j in check[o]:
            if ans < count*len(s)+j:
                ans = count*len(s)+j
                c = True
                break
        if c:
            count = ans//(len(s))
        else:
            count += 1
        for j in check[o]:
            if ans < count*len(s)+j:
                ans = count*len(s)+j
                c = True
                break
        count = ans//(len(s))   
    else:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
l = len(s)
sl = [[] for _ in range(26)]
for i in range(l):
	j = ord(s[i])-97
	sl[j].append(i)
sord = [[-1 for _ in range(l)] for _ in range(26)]
checksord = [0 for _ in range(26)]
for i in range(26):
	for j in range(len(sl[i])):
		cnt = sl[i][j]
		for q in range(checksord[i], cnt):
			sord[i][q] = cnt
		checksord[i] = cnt

for i in range(26):
	for j in range(l):
		if (sl[i] != []) & (sord[i][j] == -1):
			sord[i][j] = sl[i][0] + l
ans = 0
for i in range(len(t)):
	j = ord(t[i])-97
	if sl[j] == []:
		ans = -1
		break
	else:
		w = ans % l
		ans = ans - w + sord[j][w]

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

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
sord = [[] for _ in range(26)] #使えるリスト
l = len(s)
for i in range(l):
	j = ord(s[i])-97
	sord[j].append(i)
ans = 0
cycle = 0 #cycle * l + sordの値が番目
for i in range(len(t)):
	j = ord(t[i])-97
	if sord[j] == []:
		ans = -1
		break
	else:
		for k in range(len(sord[j])):
			w = sord[j][k] + cycle * l
			if w > ans:
				ans = w
				break
			elif k == len(sord[j])-1:
				cycle += 1
				ans = sord[j][0] + cycle * l
if ans == -1:
	print(ans)
else:
	print(ans+1)

Submission status: Wrong Answer

Solution code:
s=input()
S=set()
for i in s:
    S.add(i)
t=input()
T=set()
for i in t:
    T.add(i)
if S & T!=T:
    ans=-1
else:
    ans=0
    X=[]
    for i in range(len(t)):
        X.append(s.index(t[i]))
    
    for i in range(len(t)-1):
        if X[i]>=X[i+1]:
            ans+=len(s)
    ans+=X[len(t)-1]+1
     
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
S=set()
for i in s:
    S.add(i)
t=input()
T=set()
for i in t:
    T.add(i)
if S & T!=T:
    ans=-1
else:
    ans=0
    X=[]
    for i in range(len(t)):
        X.append(s.index(t[i]))
    
    for i in range(len(t)-1):
        if X[i]>X[i+1]:
            ans+=len(s)
    ans+=X[len(t)-1]+1
     
print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
dic = {}
for i,s in enumerate(S):
  if s not in dic:
    dic[s] = [i]
  else:
    dic[s].append(i)
#print(dic)
ind = -1
loop = 0
for t in T:
  if t not in dic:
    ans = -1
    break
  if dic[t][-1]<ind:
    loop += 1
    ind = dic[t][0]
  else:
    for i in dic[t]:
      if i > ind:
        ind = i
        break
  #print(ind)
#print(loop,ind)
else:
  ans = len(S)*loop+ind+1
          
print(ans)   

#print(*ans[1:], sep='\n')

Submission status: Wrong Answer

Solution code:
import sys

import bisect

from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math


# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    sd = defaultdict(list)

    sl = len(s)

    for i in range(sl):
        c = s[i]
        sd[c].append(i)

    tl = len(t)
    prev = 0

    ans = 0

    for i in range(tl):
        c2 = t[i]
        appear = sd[c2]
        if len(appear) == 0:
            print(-1)
            sys.exit()

        appear_max = appear[-1]
        if appear_max <= prev:
            nxt = appear[0]
        else:
            nxt = appear[bisect.bisect_left(appear, prev)]
        forward = nxt - prev
        if forward <= 0:
            forward += sl
        ans += forward
        prev = nxt

    print(ans+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
s *= 2
t = input()
l = [[]for i in range(26)]

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


from bisect import *

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


print(shukai * n + now + 1)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
s *= 2
t = input()
l = [[]for i in range(26)]

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


from bisect import *

shukai = 0
now = 0
for c in t:
    x = ord(c) - ord('a')
    if len(l[x]) == 0:
        print(-1)
        exit()
    now = l[x][bisect(l[x], now)]
    if now >= n:
        now -= n
        shukai += 1


print(shukai * n + now + 1)

Submission status: Wrong Answer

Solution code:
import bisect
s = list(input())
t = list(input())
dic = {}
for i, j in enumerate(s):
    if j in dic:
        dic[j].append(i)
    else:
        dic[j] = [i]
loop = 0

for d in dic.items():
    print(d)

if set(t) <= set(s):
    for i in range(len(t)):
        if i==0:
            idx = dic[t[0]][0]
        else:
            lis = dic[t[i]]
            idx2 = bisect.bisect_right(lis, idx)
            if idx2 == len(lis):
                loop += 1
                idx = lis[0]
            else:
                idx = lis[idx2]
    print(loop*len(s) + idx + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
d = {}
if set(t) <= set(s):
    for c in set(s):
        d[c] = []
    for i,c in enumerate(s):
        d[c].append(i)
    loc = 0
    ret = 0
    for c in t:
        nx_idx = bisect.bisect_left(d[c], loc)
        if nx_idx >= len(d[c]):
            ret += 1
            nx_idx = 0
        nx_loc = d[c][nx_idx]
        loc = nx_loc
    print(ret*len(s) + loc + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase
import bisect

s = input()
t = input()

d = {}
for c in ascii_lowercase:
    d[c] = []

if set(t) <= set(s):
    for i,c in enumerate(s):
        d[c].append(i)
    loc = 0
    ret = 0
    for c in t:
        nx_idx = bisect.bisect_left(d[c], loc)
        if nx_idx >= len(d[c]):
            ret += 1
            nx_idx = 0
        nx_loc = d[c][nx_idx]
        loc = nx_loc
        
    print(ret*len(s) + loc + 1)
        
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase
import bisect

s = input()
t = input()

d = {}
for c in ascii_lowercase:
    d[c] = []

if set(t) <= set(s):
    for i,c in enumerate(s):
        d[c].append(i)
    loc = 0
    ret = 0
    for c in t:
        nx_idx = bisect.bisect_left(d[c], loc)
        if nx_idx >= len(d[c]):
            ret += 1
            nx_idx = 0
        nx_loc = d[c][nx_idx]
        loc = nx_loc
        print(loc, ret)
        
    print(ret*len(s) + loc + 1)
        
else:
    print(-1)

Submission status: Wrong Answer

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
T = sr()
S_set = set(S)
T_set = set(T)
if len(T_set - S_set) > 0:
    print(-1); exit()

#これ以降は必ず部分列が出来る
dict_S = defaultdict(list)
for i, s in enumerate(S):
    dict_S[s].append(i)

cur = 0
lenS = len(S)
answer = 1
for t in T:
    L = dict_S[t]
    i = bisect_right(L, cur)
    if i == len(L):
        answer += lenS - cur + L[0]
        cur = L[0]
    else:
        answer += L[i] - cur
        cur = L[i]

print(answer)
# 07

Submission status: Wrong Answer

Solution code:
#138_E
from bisect import bisect_left, bisect_right
#leftはある数未満,rightはある数以下を返す
s = input()
t = input()
if set(s) >= set(t):
    al_idx = [[] for _ in range(26)]
    ss = s * 2
    alp = 'abcdefghijklmnopqrstuvwxyz'
    for i in range(len(ss)):
        al_idx[alp.index(ss[i])].append(i)
    
    tmp = -1
    ans = 0
    for j in range(len(t)):
        idx = alp.index(t[j])
        cur = bisect_right(al_idx[idx], tmp)
        ans += al_idx[idx][cur] - tmp
        print(ans)
        tmp = al_idx[idx][cur] % len(s)
        
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#138_E
from bisect import bisect_left, bisect_right
#leftはある数未満,rightはある数以下を返す
s = input()
t = input()
if set(s) >= set(t):
    al_idx = [[] for _ in range(26)]
    alp = 'abcdefghijklmnopqrstuvwxyz'
    for i in range(len(s)):
        al_idx[alp.index(s[i])].append(i)
        al_idx[alp.index(s[i])].append(i+len(s))

    tmp = -1
    ans = 0
    for j in range(len(t)):
        idx = alp.index(t[j])
        cur = bisect_right(al_idx[idx], tmp)
        ans += al_idx[idx][cur] - tmp
        tmp = al_idx[idx][cur] % len(s)
        
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#138_E
from bisect import bisect_left, bisect_right
#leftはある数未満,rightはある数以下を返す
s = input()
t = input()
if set(s) >= set(t):
    al_idx = [[] for _ in range(26)]
    alp = 'abcdefghijklmnopqrstuvwxyz'
    for i in range(len(s)):
        al_idx[alp.index(s[i])].append(i)
        al_idx[alp.index(s[i])].append(i+len(s))

    tmp = 0
    ans = 1
    for j in range(len(t)):
        idx = alp.index(t[j])
        cur = bisect_right(al_idx[idx], tmp)
        ans += al_idx[idx][cur] - tmp
        tmp = al_idx[idx][cur] % len(s)
        
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

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

from collections import deque

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = deque([])


for i in range(n):
    dic[s[i]].append(i + 1)

cnt = 0
res = 0
from bisect import bisect_left

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = bisect_left(dic[i], cnt)
    if idx >= len(dic[i]):
        res += 1
        cnt = dic[i][0]
    else:
        cnt = dic[i][idx]

print(n * res + cnt)

Submission status: Wrong Answer

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

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

from collections import deque

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = deque([])

# print(dic)

for i in range(n):
    dic[s[i]].append(i + 1)

# print(dic)
ans = 0

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = dic[i].popleft()
    if ans >= idx:
        idx += ((ans - idx) // n) * n
        if idx <= ans:
            idx += n
        ans = idx
        dic[i].append(idx)
    else:
        ans = idx
        dic[i].append(idx)
    # print(ans)

print(ans)

Submission status: Wrong Answer

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

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

from collections import deque

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = deque([])

# print(dic)

for i in range(n):
    dic[s[i]].append(i + 1)

# print(dic)
ans = 0

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = dic[i].popleft()
    if ans >= idx:
        idx += ((ans - idx) // n) * n
        if idx <= ans:
            idx += n
        ans = idx
        if len(dic[i]) > 0:
            if dic[i][-1] >= idx:
                idx += ((dic[i][-1] - idx) // n) * n
                if idx <= dic[i][-1]:
                    idx += n
        dic[i].append(idx)
    else:
        ans = idx
        if len(dic[i]) > 0:
            if dic[i][-1] >= idx:
                idx += ((dic[i][-1] - idx) // n) * n
                if idx <= dic[i][-1]:
                    idx += n
        dic[i].append(idx)
    # print(ans)

print(ans)

Submission status: Wrong Answer

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

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

import heapq

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = []

# print(dic)

for i in range(n):
    heapq.heappush(dic[s[i]], i + 1)

# print(dic)
keys = set(dic.keys())
ans = 0

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = heapq.heappop(dic[i])
    if ans >= idx:
        idx += ((ans - idx) // n) * n
        if idx <= ans:
            idx += n
        ans = idx
        if len(dic[i]) > 0:
            if dic[i][-1] >= idx:
                idx += ((dic[i][-1] - idx) // n) * n
                if idx <= dic[i][-1]:
                    idx += n
        heapq.heappush(dic[i], idx)
    else:
        ans = idx
        if len(dic[i]) > 0:
            if dic[i][-1] >= idx:
                idx += ((dic[i][-1] - idx) // n) * n
                if idx <= dic[i][-1]:
                    idx += n
        heapq.heappush(dic[i], idx)
    # print(ans)

print(ans)

Submission status: Wrong Answer

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

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

import heapq

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = []

# print(dic)

for i in range(n):
    heapq.heappush(dic[s[i]], i + 1)

# print(dic)
keys = set(dic.keys())
ans = 0

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = heapq.heappop(dic[i])
    if ans >= idx:
        idx += ((ans - idx) // n) * n
        if idx <= ans:
            idx += n
        ans = idx
        heapq.heappush(dic[i], idx)
    else:
        ans = idx
        if len(dic[i]) > 0:
            if dic[i][-1] >= idx:
                idx += ((dic[i][-1] - idx) // n) * n
                if idx <= dic[i][-1]:
                    idx += n
        heapq.heappush(dic[i], idx)
    # print(ans)

print(ans)

Submission status: Wrong Answer

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

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

import heapq

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = []

# print(dic)

for i in range(n):
    heapq.heappush(dic[s[i]], i + 1)

# print(dic)
keys = set(dic.keys())
ans = 0

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = heapq.heappop(dic[i])
    if ans >= idx:
        idx += ((ans - idx) // n) * n
        if idx <= ans:
            idx += n
        ans = idx
        heapq.heappush(dic[i], idx)
    else:
        ans = idx
        if len(dic[i]) > 0:
            if dic[i][-1] >= idx:
                idx += ((dic[i][-1] - idx) // n) * n
                if idx <= dic[i][-1]:
                    idx += n
        heapq.heappush(dic[i], idx + n)
    # print(ans)

print(ans)

Submission status: Wrong Answer

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

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

import heapq

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = []

# print(dic)

for i in range(n):
    heapq.heappush(dic[s[i]], i + 1)

# print(dic)
keys = set(dic.keys())
ans = 0

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = heapq.heappop(dic[i])
    if ans >= idx:
        idx += ((ans - idx) // n) * n
        if idx <= ans:
            idx += n
        ans = idx
        heapq.heappush(dic[i], idx)
    else:
        ans = idx
        heapq.heappush(dic[i], idx + n)
    # print(ans)

print(ans)

Submission status: Wrong Answer

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

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

import heapq

dic = {}
for i in range(ord("a"), ord("z") + 1):
    dic[chr(i)] = []

# print(dic)

for i in range(n):
    heapq.heappush(dic[s[i]], i + 1)

# print(dic)
keys = set(dic.keys())
ans = 0

for i in t:
    if len(dic[i]) == 0:
        print(-1)
        sys.exit()
    idx = heapq.heappop(dic[i])
    if ans >= idx:
        while ans >= idx:
            idx += n
        ans = idx
        heapq.heappush(dic[i], idx)
    else:
        ans = idx
        heapq.heappush(dic[i], idx + n)
    # print(ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
sub = s+s
dp = []
for i in range(len(s)):
    d = [10**15]*26
    dp.append(d)
index = [[] for i in range(26)]
for i in range(len(sub)):
    index[ord(sub[i])-97].append(i)
for i in range(len(s)):
    cur = s[i]
    for j in range(26):
        if len(index[j]) != 0:
            k = bisect.bisect_left(index[j], i)
            dp[i][j] = index[j][k]-i
ans = dp[0][ord(t[0])-97]+1
next = dp[0][ord(t[0])-97]
flag = True
for i in range(1,len(t)):
    if ans >= 10**15:
        flag = False
        break
    else:
        cur = next
        ans += dp[cur][ord(t[i])-97]
        if cur + dp[cur][ord(t[i])-97] >= len(s):
            next = cur + dp[cur][ord(t[i])-97] - len(s)
        else:
            next = cur + dp[cur][ord(t[i])-97]
if ans < 10**15:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
sub = s+s
dp = []
for i in range(len(s)):
    d = [10**15]*26
    dp.append(d)
index = [[] for i in range(26)]
for i in range(len(sub)):
    index[ord(sub[i])-97].append(i)
for i in range(len(s)):
    cur = s[i]
    for j in range(26):
        if len(index[j]) != 0:
            k = bisect.bisect_left(index[j], i)
            dp[i][j] = index[j][k]-i
ans = dp[0][ord(t[0])-97]+1
next = dp[0][ord(t[0])-97]
flag = True
for i in range(1,len(t)):
    if ans >= 10**15:
        flag = False
        break
    else:
        cur = next
        ans += dp[cur][ord(t[i])-97]
        if cur + dp[cur][ord(t[i])-97] >= len(s):
            next = cur + dp[cur][ord(t[i])-97] - len(s)
        else:
            next = cur + dp[cur][ord(t[i])-97]
if ans < 10**15:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

import bisect
from collections import defaultdict
d = defaultdict(list)
for i in range(len(s)):
    d[s[i]].append(i)

#print(d)
now=0
cnt=0
for i in range(len(t)):
    if len(d[t[i]])==0:
        print(-1)
        exit()
    found=False

    ind = bisect.bisect_left(d[t[i]],now)
#    print(ind,now)
    if ind!=len(d[t[i]]):
        now=d[t[i]][ind]+1
    else:
        now=d[t[i]][0]
        cnt+=1

if cnt==0:
    cnt+=1

print(cnt*len(s) + d[t[-1]][0]+1)

#print(cnt,len(s), d[t[-1]])