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:
from string import ascii_lowercase
from bisect import bisect_right
s=input()
t=input()
p={c: [] for c in s}
for x,c in enumerate(s):
    p[c].append(x)
z=0
l=-1
for c in t:
    if c not in p:
        print(-1)
        break
    x=bisect_right(p[c],1)
    if x==len(p[c]):
        x=0
        z+=1
    l=p[c][x]
else:
    print(z*len(s)+l+1)

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase
from bisect import bisect_right
s=input()
t=input()
p={c: [] for c in s}
for x,c in enumerate(s):
    p[c].append(x)
z=0
l=-1
for c in t:
    if c not in p:
        print(-1)
        break
    x=bisect_right(p[c],1)
    if x==len(p[c]):
        x=0
        z+=1
    l=p[c][x]

print(z*len(s)+l+1)

Submission status: Wrong Answer

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

table = collections.defaultdict(list)
table2 = collections.defaultdict(int)
last = t[-1]
last_id = []
for i, x in enumerate(s):
    table[x].append(i)

for i, x in enumerate(t):
    if x not in table:
        print(-1)
        exit(0)

tmp = 0
id = 0
ans = 0
for x in t:
    l = len(table[x])
    i = bisect.bisect_left(table[x], id)
    if l == i:
        id = 0
        ans += len(s)
        i = bisect.bisect_left(table[x], id)
    id = table[x][i]

ans += id+1


print(ans)

Submission status: Wrong Answer

Solution code:
S = list(map(lambda x : ord(x)-ord('a'), input().strip()))
T = list(map(lambda x : ord(x)-ord('a'), input().strip()))

L = len(S)

occ = [[] for i in range(26)]
for i, c in enumerate(S):
    occ[c].append(i)

for c in T:
    if occ[c] == []:
        print(-1)
        quit()

total = 0
cur = -1

def getLowest(bound, lo, hi, lst):
    # Return index of lowest element in list greater than bound
    if lo >= hi:
        if lst[lo] > bound:
            return lo
        else:
            return 0
        
    mid = lo + (hi - lo) // 2
    if lst[mid] > bound:
        return getLowest(bound, lo, mid, lst)
    else:
        return getLowest(bound, mid+1, hi, lst)

for i, char in enumerate(T):
    newpos = occ[char][getLowest(cur, 0, len(occ[char])-1, occ[char])]
    if newpos < cur:
        total += L - cur + newpos
    else:
        total += newpos - cur
    cur = newpos
print(total)

Submission status: Wrong Answer

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

dic = {}
for i in range(len(s)):
    if s[i] in dic:
        dic[s[i]].append(i)
    else:
        dic[s[i]] = [i]
        
def f(L, u, l, x):
    if L[-1] < x:
        return -1
    if u-l < 2:
        if L[l] > x:
            return l
        else:
            return u
    m = (u+l)//2
    if L[m] > x:
        return f(L, m, l, x)
    else:
        return f(L, u, m, x)
    
ans = 0
c = 0
for i in range(len(t)):
    if t[i] not in dic:
        ans = -1
        break
    idx = f(dic[t[i]], len(dic[t[i]])-1, 0, c-1)
#    print("idx =", idx)
    if idx < 0:
        idx = dic[t[i]][0]
        ans += len(s)-c+idx+1
        c = idx+1
#        print(ans,c)
    else:
        idx = dic[t[i]][idx]
        ans += idx+1-c
        c = idx+1
#        print(ans,c)
        
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import bisect

def main():
    s=input()
    t=input()
    s = s*2
    n = len(s)
    cs = collections.Counter(s)
    ct = collections.Counter(t)
    for sct in ct.keys():
        if cs[sct] == 0:
            return -1
    dc = collections.defaultdict(list)
    for i in range(n):
        dc[s[i]].append(i+1)
    res = 0
    ptl = 0
    for i in range(len(t)):
        tl = dc[t[i]][bisect.bisect_left(dc[t[i]],ptl)]
        res += tl - ptl
        ptl = tl - n//2 if tl > n//2 else tl
    return res

print(main())

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bi_l
from collections import defaultdict


def main():
    s, t = sys.stdin.read().split()
    print(s, t)
    if set(t) - set(s):
        print(-1)
        sys.exit()

    n = len(s)
    s *= 2
    c = defaultdict(list)
    for i in range(n * 2):
        c[s[i]].append(i)

    i = 0
    l = 0 # left_most
    for ch in t:
        b = c[ch][bi_l(c[ch], l)]
        if b < n:
            l = b + 1
        else:
            l = b - n + 1
            i += n

    print(i+(l-1)+1) # 最初が0のため

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bi_l
from collections import defaultdict


def main():
    s, t = sys.stdin.read().split()
    if set(t) - set(s):
        print(-1)
        sys.exit()

    n = len(s)
    s *= 2
    c = defaultdict(list)
    for i in range(n * 2):
        c[s[i]].append(i)

    i = 0
    l = 0 # left_most
    for ch in t:
        b = c[ch][bi_l(c[ch], l)]
        if b < n:
            l = b + 1
        else:
            l = b - n + 1
            i += n
    i += b
    print(i+1) # 最初が0のため

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bi_l
from collections import defaultdict


def main():
    s, t = sys.stdin.read().split()
    if set(t) - set(s):
        print(-1)
        sys.exit()

    n = len(s)

    c = defaultdict(list)
    for i in range(n * 2):
        c[(s+s)[i]].append(i)

    count = 0
    l = 0 # left_most
    for ch in t:
        b = c[ch][bi_l(c[ch], l)]
        if b < n:
            l = b + 1
        else:
            l = b - n + 1
            count += n
    count += b
    print(count+1) # 最初が0のため

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bi_l
from collections import defaultdict


def main():
    s, t = sys.stdin.read().split()
    if set(t) - set(s):
        print(-1)
        sys.exit()

    n = len(s)

    c = defaultdict(list)
    for i in range(n*2):
        c[(s*2)[i]].append(i)

    i = 0
    l = 0 # left_most
    for ch in t:
        b = c[ch][bi_l(c[ch], l)]
        if b < n:
            l = b + 1
        else:
            l = b - n + 1
            i += n
    i += b
    print(i+1) # 最初が0のため

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import bisect
bi_l = bisect.bisect_left
import collections

s, t = sys.stdin.read().split()
if set(t) - set(s):
    print(-1)
    sys.exit()

n = len(s)

c = collections.defaultdict(list)
for i in range(n*2):
    c[(s*2)[i]].append(i)

i = 0
l = 0 # left_most
for ch in t:
    b = c[ch][bi_l(c[ch], l)]
    if b < n:
        l = b + 1
    else:
        l = b - n + 1
        i += n
i += b
print(i+1) # 最初が0のため

Submission status: Wrong Answer

Solution code:
import sys
import bisect
bi_l = bisect.bisect_left
import collections


s, t = sys.stdin.read().split()
if set(t) - set(s):
    print(-1)
    sys.exit()

n = len(s)

c = collections.defaultdict(list)
for i in range(n):
    c[s[i]].append(i)

i = 0
for ch in t:
    p = c[ch][bi_l(c[ch], (i+1) % n) % len(c[ch])]
    if p <= i % n:
        i += n - i % n + p
    else:
        i += p - i % n
print(i+1) # indexの関係で0から始まっているため

Submission status: Wrong Answer

Solution code:
import sys
import bisect
bi_l = bisect.bisect_left
import collections


s, t = sys.stdin.read().split()
if set(t) - set(s):
    print(-1)
    sys.exit()

n = len(s)

c = collections.defaultdict(list)
for i in range(n):
    c[s[i]].append(i)


i = 0
for ch in t:
    b = bi_l(c[ch], (i+1) % n)
    if b >= len(c[ch]):
        b = 0
    p = c[ch][b]
    if p <= i % n:
        i += n - i % n + p
    else:
        i += p - i % n
print(i+1) # indexの関係で0から始まっているため

Submission status: Wrong Answer

Solution code:
import sys
import bisect
bi_l = bisect.bisect_left
import collections


s, t = sys.stdin.read().split()
if set(t) - set(s):
    print(-1)
    sys.exit()

n = len(s)

c = collections.defaultdict(list)
for i in range(n):
    c[s[i]].append(i)


i = 0
for ch in t:
    b = bi_l(c[ch], i % n)
    if b >= len(c[ch]):
        b = 0
    p = c[ch][b]
    if p <= i % n:
        i += n - i % n + p
    else:
        i += p - i % n
print(i+1) # indexの関係で0から始まっているため

Submission status: Wrong Answer

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

if len(set(t)-set(s))>0:
  print(-1)
else:
  s2=s*2
  s2pos={}
  for i in range(len(s2)):
    if s2[i] in s2pos:
      s2pos[s2[i]].append(i)
    else:
      s2pos[s2[i]]=[i]

  cur=-1
  import bisect
  rev=0
  for c in t:
    cur+=1
    pos=s2pos[c]
    p=bisect.bisect_left(pos,cur)
    cur=pos[p]
    if cur>=len(s):
      cur-=len(s)
      rev+=1
    if rev>=100:
      print(-1)
      break
  else:
    print(rev*len(s)+cur+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s, t = [ord(c)-ord('a') for c in input()], [ord(c)-ord('a') for c in input()]
cnt = [[] for i in range(26)]
for i in range(len(s)):
    cnt[s[i]].append(i)
    cnt[s[i]].append(i+len(s))
for i in range(26):
    cnt[i] = sorted(cnt[i])
ans = 0
p = 0
for i in range(len(t)):
    c = t[i]
    if (len(cnt[c]) == 0):
        print('-1')
        exit()
    next = bisect_left(cnt[c], p)
    p = cnt[c][next] + 1
    print(c, cnt[c], p)
    if (p >= len(s)):
        p -= len(s)
        ans += len(s)
ans += p
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s, t = [ord(c)-ord('a') for c in input()], [ord(c)-ord('a') for c in input()]
cnt = [[] for i in range(26)]
for i in range(len(s)):
    cnt[s[i]].append(i)
    cnt[s[i]].append(i+len(s))
ans = 0
p = 0
for i in range(len(t)):
    c = t[i]
    if (len(cnt[c]) == 0):
        # print('-1')
        exit()
    next = bisect_left(cnt[c], p)
    p = cnt[c][next] + 1
    if (p >= len(s)):
        p -= len(s)
        ans += len(s)
ans += p
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s, t = [ord(c)-ord('a') for c in input()], [ord(c)-ord('a') for c in input()]
cnt = [[] for i in range(26)]
for i in range(len(s)):
    cnt[s[i]].append(i)
    cnt[s[i]].append(i+len(s))
ans = 0
p = 0
for i in range(len(t)):
    c = t[i]
    if (len(cnt[c]) == 0):
        print('-1')
        exit()
    next = bisect_left(cnt[c], p)
    p = cnt[c][next] + 1
    if (p >= len(s)):
        p -= len(s)
        ans += len(s)
ans += p
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s, t = [ord(c)-ord('a') for c in input()], [ord(c)-ord('a') for c in input()]
cnt = [[] for i in range(26)]
for i in range(len(s)):
    cnt[s[i]].append(i)
    cnt[s[i]].append(i+len(s))
ans = 0
p = 0
for i in range(len(t)):
    c = t[i]
    if (len(cnt[c]) == 0):
        print('-1')
        exit()
    next = bisect_left(cnt[c], p)
    p = cnt[c][next] 
    if (p >= len(s)):
        p -= len(s)
        ans += len(s)
ans += p + 1
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
else:
  import bisect
  dic={}
  for i in range(len(s)):
    if s[i] in dic:
      dic[s[i]].append(i)
    else:
      dic[s[i]]=[i]
  po=-1
  rep=0
  for i in range(len(t)):
    po+=1
    target=t[i]
    posis=dic[target]
    place=bisect.bisect_left(posis,po)
    if place==len(posis):
      rep+=1
      po=0
      place=bisect.bisect_left(posis,po)
    po=posis[place]
    if rep>=100:
      break
  if rep>=100:
    print(-1)
  else:
    print(rep*len(s)+po+1)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
else:
  import bisect
  dic={}
  for i in range(len(s)):
    if s[i] in dic:
      dic[s[i]].append(i)
    else:
      dic[s[i]]=[i]
  po=-1
  rep=0
  for i in range(len(t)):
    po+=1
    target=t[i]
    posis=dic[target]
    place=bisect.bisect_left(posis,po)
    if place==len(posis):
      rep+=1
      po=0
      place=bisect.bisect_left(posis,po)
    po=posis[place]
    if rep>100:
      break
  if rep>=100:
    print(-1)
  else:
    print(rep*len(s)+po+1)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
else:
  import bisect
  dic={}
  for i in range(len(s)):
    if s[i] in dic:
      dic[s[i]].append(i)
    else:
      dic[s[i]]=[i]
  po=-1
  rep=0
  for i in range(len(t)):
    po+=1
    target=t[i]
    posis=dic[target]
    place=bisect.bisect_left(posis,po)
    if place==len(posis):
      rep+=1
      po=0
      place=bisect.bisect_left(posis,po)
    po=posis[place]
    if rep>100:
      break
  if rep>100:
    print(-1)
  else:
    print(rep*len(s)+po+1)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
else:
  import bisect
  dic={}
  for i in range(len(s)):
    if s[i] in dic:
      dic[s[i]].append(i)
    else:
      dic[s[i]]=[i]
  po=0
  rep=0
  for i in range(len(t)):
    target=t[i]
    posis=dic[target]
    place=bisect.bisect_left(posis,po)
    if place==len(posis):
      rep+=1
      po=0
      place=bisect.bisect_left(posis,po)
    po=posis[place]
    if rep>100:
      break
  if rep>100:
    print(-1)
  else:
    print(rep*len(s)+po+1)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
ans = 0
bef = -1
Slen = len(S)
for t in T:
    while S[ans%Slen]!=t:
        ans+=1
        if ans-bef>Slen:break
    if ans-bef>Slen:
        ans=-1
        break
    else:bef=ans
print(ans if ans==-1 else ans+1)

Submission status: Wrong Answer

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

check = [False]*30
for c in s:
    i = ord(c) - ord("a")
    check[i] = True

for c in t:
    i = ord(c) - ord("a")
    if not check[i]:
        print(-1)
        sys.exit()

dp = [[-1 for i in range(26)] for j in range(len(s))]

s = s + s

#
def ser(string :str,target :str,s :int):
    for i in range(s,len(string)):
        if string[i] == target:
            return i % (len(string)//2),i-1

# 指定した範囲に数字を埋める
def dig(ls,c,v,s,t):
    for i in range(s,t+1):
        ls[i][c] = v

for c in range(len(dp[0])):
    if not check[c]:continue
    i = 0
    while i < len(dp):
        start = i
        v,i = ser(s,chr(c+ord("a")),i+1)
        dig(dp,c,v,start,min(i,len(dp)-1))
        i += 1

# 最初にうまいことやるために
import copy
ls = copy.deepcopy(dp[0])
dp.append(ls)

ans = 0
i = -1
for char in t:
    ikari = dp[i][ord(char) - ord("a")]
    if i >= ikari:
        ans += 1
    i = ikari
print(ans * (len(dp)-1) + 1 + i)

Submission status: Wrong Answer

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

check = [False]*30
for c in s:
    i = ord(c) - ord("a")
    check[i] = True

for c in t:
    i = ord(c) - ord("a")
    if not check[i]:
        print(-1)
        sys.exit()

dp = [[-1 for i in range(26)] for j in range(len(s))]

s = s + s

#
def ser(string :str,target :str,s :int):
    for i in range(s,len(string)):
        if string[i] == target:
            return i % (len(string)//2),i-1

# 指定した範囲に数字を埋める
def dig(ls,c,v,s,t):
    for i in range(s,t+1):
        ls[i][c] = v

for c in range(len(dp[0])):
    if not check[c]:continue
    i = 0
    while i < len(dp):
        start = i
        v,i = ser(s,chr(c+ord("a")),i+1)
        dig(dp,c,v,start,min(i,len(dp)-1))
        i += 1

ans = 0
i = 0
for char in t:
    ikari = dp[i][ord(char) - ord("a")]
    if i >= ikari:
        ans += 1
    i = ikari
print(ans * len(dp) + 1 + i)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import bisect

def solve(s: str, t: str):
    LENS = len(s)
    dict_s = {} ##{'c': [0], 'o': [1], 'n': [2], 't': [3, 6], 'e': [4], 's': [5]}
    index = [] ##[[5], [4], [2], [3, 6], [4], [2], [0], [4]]

    ## create dict
    for i in range(LENS):
        if dict_s.get(s[i]) != None:
            dict_s[s[i]].append(i)
        else:
            dict_s[s[i]]= [i]
    
    ## そもそもtが作れるかの判定
    for tt in t:
        if dict_s.get(tt) == None:
            print(-1)
            return
        else:
            index.append(dict_s[tt])
    
    answer = 0
    for i in range(len(index)):
        cur = index[i]

        if i == 0:
            answer += cur[0]
            index[i]=[cur[0]]
            continue

        prev = index[i-1]

        if len(cur)==1:
            if cur[0]>prev[0]:
                answer += cur[0]-prev[0]
            else:
                answer += cur[0]+LENS-prev[0] ##一周追加
        else: ##複数
            next_index = bisect.bisect_left(cur,prev[0])

            if next_index<len(cur)-1: ## prevより大きいindexがある時
                next_index += 1 if cur[next_index] == prev[0] else 0
                
                answer += cur[next_index]-prev[0]
                index[i]= [cur[next_index]]
            else:
                answer += cur[0]+LENS-prev[0]
                index[i] = [cur[0]]
       

    print(answer+1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import bisect

def solve(s: str, t: str):
    LENS = len(s)
    dict_s = {} ##{'c': [0], 'o': [1], 'n': [2], 't': [3, 6], 'e': [4], 's': [5]}
    index = [] ##[[5], [4], [2], [3, 6], [4], [2], [0], [4]]

    ## create dict
    for i in range(LENS):
        if dict_s.get(s[i]) != None:
            dict_s[s[i]].append(i)
        else:
            dict_s[s[i]]= [i]
    
    ## そもそもtが作れるかの判定
    for tt in t:
        if dict_s.get(tt) == None:
            print(-1)
            return
        else:
            index.append(dict_s[tt])
    
    answer = 0
    for i in range(len(index)):
        cur = index[i]

        if i == 0:
            answer += cur[0]
            index[i]=[cur[0]]
            continue

        prev = index[i-1]

        if len(cur)==1:
            if cur[0]>prev[0]:
                answer += cur[0]-prev[0]
            else:
                answer += cur[0]+LENS-prev[0] ##一周追加
        else: ##複数
            next_index = bisect.bisect_left(cur,prev[0])

            if next_index<len(cur): ## prevより大きいindexがある時
                answer += cur[next_index]-prev[0]
                index[i]= [cur[next_index]]
            else:
                answer += cur[0]+LENS-prev[0]
                index[i]= [cur[0]]

    print(answer+1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: [])
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].append(i+1)
    min_D[s] = min(i+1, min_D[s])

for s in D.keys():
    D[s] = sorted(D[s])

cur_pos = 0
repeat = 0
for t in T:
    ind = bisect.bisect_left(D[t], cur_pos)
    if ind >= len(D[t]):
        repeat += 1
        cur_pos = min_D[t]
    else:
        cur_pos = D[t][ind]

print(len(S)*repeat+cur_pos)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: [])
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].append(i)
    min_D[s] = min(i, min_D[s])

for s in D.keys():
    D[s] = sorted(D[s])

cur_pos = 0
repeat = 0
for t in T:
    ind = bisect.bisect_left(D[t], cur_pos)
    if ind >= len(D[t]):
        repeat += 1
        cur_pos = min_D[t]
    else:
        cur_pos = D[t][ind]

print(len(S)*repeat+cur_pos+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: set())
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].add(i)
    min_D[s] = min(i, min_D[s])

cur_pos = 0
repeat = 0
for t in T:
    for next_cand in D[t]:
        if next_cand >= cur_pos:
            cur_pos = next_cand+1
            break
    else:
        repeat += 1
        cur_pos = min_D[t]
print(len(S)*repeat+cur_pos)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: set())
for i, s in enumerate(S):
    D[s].add(i)

cur_pos = 0
repeat = 0
for t in T:
    for next_cand in D[t]:
        if next_cand >= cur_pos:
            cur_pos = next_cand+1
            break
    else:
        repeat += 1
        cur_pos = min(D[t])
print(len(S)*repeat+cur_pos)

Submission status: Wrong Answer

Solution code:
import bisect

S = input()
T = input()


n = len(S)
m = len(T)
c = [[] for _ in range(26)]
for i in range(n):
    idx = ord(S[i]) - ord('a')
    c[idx].append(i)
for i in range(n):
    idx = ord(S[i]) - ord('a')
    c[idx].append(i+n)
# print(c)
ans = 0
now = 0
for i in range(m):
    id = ord(T[i]) - ord('a')
    if len(c[id]) == 0:
        print("-1")
        exit()
    now = c[id][bisect.bisect_left(c[id], now)]
    if now >= n:
        now -= n
        ans += n
ans += now
print(ans+1)

Submission status: Wrong Answer

Solution code:
import bisect

S = input()
T = input()


n = len(S)
m = len(T)
c = [[] for _ in range(26)]
for i in range(n):
    idx = ord(S[i]) - ord('a')
    c[idx].append(i)
for i in range(n):
    idx = ord(S[i]) - ord('a')
    c[idx].append(i+n)

ans = 0
now = 0
for i in range(m):
    id = ord(T[i]) - ord('a')
    if len(c[id]) == 0:
        print("-1")
        exit()
    now = c[id][bisect.bisect(c[id], now)]
    if now >= n:
        now -= n
        ans += n
ans += now
print(ans+1)

Submission status: Wrong Answer

Solution code:
#$from collections 
import bisect,sys

s_ = input()
t = input()

char_s = set(s_)
char_t = set(t)


if not char_s >= char_t:
    print(-1)
    sys.exit()

s = s_+s_

chr_s = {}

l = len(s_)

for i in range(2*l):
    if s[i] in chr_s:
        chr_s[s[i]].append(i)
    else:
        chr_s[s[i]] = [i]
#print(chr_s)
loops = 0
tmp = 0##-1から変更してみる

for i in range(len(t)):
    j = bisect.bisect_right(chr_s[t[i]],tmp)###leftと違うの？
    tmp = chr_s[t[i]][j]
    #print(tmp)
    if tmp>=l:
        loops+=l
        tmp-=l
#print(chr_s)
print(loops+tmp+1)#0-indexで+1

Submission status: Wrong Answer

Solution code:
#$from collections 
import bisect,sys

s_ = input()
t = input()

char_s = set(s_)
char_t = set(t)


if not char_s >= char_t:
    print(-1)
    sys.exit()

s = s_+s_

chr_s = {}

l = len(s_)

for i in range(2*l):
    if s[i] in chr_s:
        chr_s[s[i]].append(i)
    else:
        chr_s[s[i]] = [i]
#print(chr_s)
loops = 0
tmp = -1##?

for i in range(len(t)):
    j = bisect.bisect_left(chr_s[t[i]],tmp)###rightから変更してみる
    tmp = chr_s[t[i]][j]
    #print(tmp)
    if tmp>=l:
        loops+=l
        tmp-=l
#print(chr_s)
print(loops+tmp+1)#0-indexで+1

Submission status: Wrong Answer

Solution code:
#$from collections 
import bisect,sys

s_ = input()
t = input()

char_s = set(s_)
char_t = set(t)


if not char_s >= char_t:
    print(-1)
    sys.exit()

s = s_+s_

chr_s = {}

l = len(s_)

for i in range(2*l):
    if s[i] in chr_s:
        chr_s[s[i]].append(i)
    else:
        chr_s[s[i]] = [i]
loops = 0
tmp = 0

for i in range(len(t)):
    j = bisect.bisect_left(chr_s[t[i]],tmp)
    tmp = chr_s[t[i]][j]
    #print(tmp)
    if tmp>=l:
        loops+=l
        tmp-=l
#print(chr_s)
print(loops+tmp+1)#0-indexで+1

Submission status: Wrong Answer

Solution code:
import bisect

s=input()
t=input()

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

r="abcdefghijklmnopqrstuvwxyz"
p=[[] for i in range(26)]

for i in range(sl):
  p[r.find(s[i])].append(i)

for i in range(26):
  if len(p[i])>0:
    p[i].append(p[i][0]+sl)

s=set()
for i in range(tl):
  s.add(t[i])
for c in s:
  if len(p[r.find(c)]) == 0:
     print(-1)
     exit()

ti,si = 0,0
while ti < tl:
  si +=  p[r.find(t[ti])][bisect.bisect_right(p[r.find(t[ti])], si%sl)] - si%sl
  ti += 1

print(si+1)

Submission status: Wrong Answer

Solution code:
from bisect import*
s=input()
t=input()
if set(t)<=set(s):
    d={}
    for k,j in enumerate(s*2):
        if j in d:
            d[j].append(k)
        else:
            d[j]=[k]
    print(d)
    now=-1
    ans=0
    for _,i in enumerate(t):
        nex=d[i][bisect_right(d[i],now)]
        ans+=nex-now

        #print(i,_,now,nex,ans)
        
        if nex>=len(s):
            now=nex-len(s)
        else:
            now=nex
    print(ans)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import*
s=input()
t=input()
if set(t)<=set(s):
    d={}
    for k,j in enumerate(s*3):
        if j in d:
            d[j].append(k)
        else:
            d[j]=[k]
    #print(d)
    now=0
    ans=0
    for i in t:
        nex=d[i][bisect_left(d[i],now)]
        ans+=nex-now
        if nex>=len(s):
            nex-=len(s)
            now=nex
        else:
            now=nex
    print(ans+1)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import*
s=input()
t=input()
if set(t)<=set(s):
    d={}
    for k,j in enumerate(s*2):
        if j in d:
            d[j].append(k)
        else:
            d[j]=[k]
    #print(d)
    now=0
    ans=0
    for i in t:
        nex=d[i][bisect_left(d[i],now)]
        ans+=nex-now
        if nex>=len(s):
            nex-=len(s)
            now=nex
        else:
            now=nex
    print(ans+1)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
n = len(s)
s = s + s
t = input()
if set(t) - set(s):
	print(-1)
	exit()
d = defaultdict(list)
for i in range(2 * n):
	d[s[i]] += [i]
cur = tot = 0
for c in t:
	x = d[c][bisect_left(d[c], cur + 1)]
	if x < n:
		cur = x
	else:
		cur = x - n
		tot += n
if cur == n - 1:
	cur = 0
tot += cur
print(tot)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
n = len(s)
s = s + s
t = input()
if set(t) - set(s):
	print(-1)
	exit()
d = defaultdict(list)
for i in range(2 * n):
	d[s[i]] += [i]
cur = tot = 0
for c in t:
	x = d[c][bisect_left(d[c], cur)]
	if x < n:
		cur = x
	else:
		cur = x - n
		tot += n
tot += cur + 1
print(tot)

Submission status: Wrong Answer

Solution code:
import bisect
s=list(input())
t=list(input())
s=s+s
u=[[] for i in range(26)]
x=0
count=0

for i in range(ord('a'),ord('z')):
    for j in range(len(s)):
        if i==ord(s[j]):
            u[i-97].append(j+1)

for i in range(len(t)):
    if len(u[ord(t[i])-97])==0:
        print(-1)
        exit()
    b=bisect.bisect_left(u[ord(t[i])-97],x+1)
    
    if u[ord(t[i])-97][b]>=len(s)//2:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]-len(s)//2
        
    else:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]
        
        
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
s=list(input())
t=list(input())
s=s+s
u=[[] for i in range(26)]
x=0
count=0

for i in range(ord('a'),ord('z')):
    for j in range(len(s)):
        if i==ord(s[j]):
            u[i-97].append(j+1)

for i in range(len(t)):
    if len(u[ord(t[i])-97])==0:
        print(-1)
        exit()
    b=bisect.bisect_left(u[ord(t[i])-97],x+1)
    
    if u[ord(t[i])-97][b]>len(s)//2:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]-len(s)//2
        
    else:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]
        
        
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
s=list(input())
t=list(input())
s=s+s
u=[[] for i in range(26)]
x=0
count=0

for i in range(ord('a'),ord('z')):
    for j in range(len(s)):
        if i==ord(s[j]):
            u[i-97].append(j+1)

for i in range(len(t)):
    if len(u[ord(t[i])-97])==0:
        print(-1)
        exit()
    b=bisect.bisect_left(u[ord(t[i])-97],x)
    
    if u[ord(t[i])-97][b]>len(s)//2:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]-len(s)//2
        
    else:
        count+=u[ord(t[i])-97][b]-x
        x=u[ord(t[i])-97][b]
        
        
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
s=list(input())
t=list(input())
s=s+s
u=[[] for i in range(26)]
x=0
count=0
for i in range(ord('a'),ord('z')):
    for j in range(len(s)):
        if i==ord(s[j]):
            u[i-97].append(j+1)

for i in range(len(t)):
    if len(u[ord(t[i])-97])==0:
        print(-1)
        exit()
    for j in (u[ord(t[i])-97]):
        if j>x:
            if j>len(s)//2:
                count+=j-x
                x=j-len(s)//2
                break
            else:
                count+=j-x
                x=j
                break
        
print(count)

Submission status: Wrong Answer

Solution code:

s=list(input())
t=list(input())
k=0
for i in range(10**5):
    if i==1 and k==0:
        print(-1)
        exit()
    
    for j in range(len(s)):
        if s[j]==t[k]:
            k+=1
            if k==len(t):
                print((i)*len(s)+(j+1))
                exit()

Submission status: Wrong Answer

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

f = True
for i in t:
    if(not i in s):
        f = False
i = 0
if(not f):
    print(-1)
else:
    for x in t:
        while(s[i % len(s)] != x):
            i+=1
    print(i+1)