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:
import sys
from collections import defaultdict
dic = defaultdict(list)
s = input()
t = input()
n = len(s)
for i in range(n):
    dic[s[i]].append(i+1)

for i in t:
    if dic[i]==[]:
        print(-1)
        sys.exit()
        
ans = dic[t[0]][0]

if len(t)==1:
    print(ans)
    sys.exit()

count=0

for i in range(1, len(t)):
    if ans >= dic[t[i]][-1]:
        count += 1
        ans = dic[t[i]][-1]
    elif ans < dic[t[i]][0]:
        ans = dic[t[i]][0]
    else:
        sm = dic[t[i]][0]
        la = dic[t[i]][-1]
        while sm+1<la:
            mi = (sm + la)//2
            if ans >= mi:
                sm = mi
            else:
                la = mi
        ans = la

print(ans+count*n)

Submission status: Wrong Answer

Solution code:
import copy
key= list('abcdefghijklmnopqrstuvwxyz')
value=[[] for i in range(26)]
d=dict(zip(key,value))
s = input()
s = list(s)
n = len(s)
ans = 0
for i in range(len(s)):
    d[s[n-i-1]].append(n-i)
st = set(s)
t = input()
t = list(t)
p = copy.deepcopy(d)
b = 0
for i in range(len(t)):
    if t[i] in st:
        if len(p[t[i]]) != 0:
            a = p[t[i]].pop()
            if b > a:
                p = copy.deepcopy(d)
                ans += n
            else:
                pass
            b = a
        else:
            p = copy.deepcopy(d)
            b = 0
            ans += n
    else:
        ans = -1
        break
if ans != -1:
    ans += a
print(ans)

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase
from bisect import bisect_right, bisect_left


def main():
    s = input()
    t = input()
    len_s = len(s)
    s_all = {s: [] for s in ascii_lowercase}
    for i in range(len_s):
        s_all[s[i]].append(i)
    ans = 0
    for ss in ascii_lowercase:
        s_all[ss].sort()
    if any(s_all[tt] == [] for tt in t):
        ans = -1
    else:
        s_ind = 0
        duplicate = 0
        for i in range(len(t)):
            if s_ind <= s_all[t[i]][0]:
                next_ind = s_all[t[i]][0]
            elif s_all[t[i]][-1] <= s_ind:
                duplicate += 1
                next_ind = s_all[t[i]][0]
            else:
                next_ind = bisect_left(s_all[t[i]], s_ind)
            s_ind = next_ind + 1
        ans = duplicate * len_s + s_ind
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase
from bisect import bisect_right


def main():
    s = input()
    t = input()
    len_s = len(s)
    s_all = {s: [] for s in ascii_lowercase}
    for i in range(len_s):
        s_all[s[i]].append(i)
    ans = 0
    for s in ascii_lowercase:
        s_all[s].sort()
    if any(s_all[tt] == [] for tt in t):
        ans = -1
    else:
        s_ind = 0
        rest = 0
        for i in range(len(t)):
            if s_all[t[i]][-1] < s_ind:
                next_ind = 0
            else:
                next_ind = bisect_right(s_all[t[i]], s_ind)
            if len(s_all[t[i]]) <= next_ind:
                next_ind = len(s_all[t[i]]) - 1
            if s_all[t[i]][next_ind] < s_ind:
                ans += 1
            rest = s_all[t[i]][next_ind] + 1
            s_ind = s_all[t[i]][next_ind]
        ans *= len_s
        ans += rest
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import bisect
from collections import defaultdict

def main():
	s=RD()
	t=RD()
	d=defaultdict(list)

	for i,ss in enumerate(s):
		d[ss].append(i)
	#print(d)

	now=0
	cnt=0

	for tt in t:
		if d[tt]==[]:
			print(-1)
			exit()
		else:
			i=bisect.bisect_left(d[tt],now)
			if len(d[tt])<=i:
				cnt+=1
				now=d[tt][0]
			else:
				now=d[tt][i]
		#print(tt,now,cnt)
	print(len(s)*cnt+now+1)

























if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import bisect
from collections import defaultdict

def main():
	s=RD()
	t=RD()
	d=defaultdict(list)

	for i,ss in enumerate(s):
		d[ss].append(i)
	#print(d)

	now=0
	cnt=0

	for tt in t:
		if d[tt]==[]:
			print(-1)
			break
		else:
			i=bisect.bisect_left(d[tt],now)
			if len(d[tt])<=i:
				cnt+=1
				now=d[tt][0]
			else:
				now=d[tt][i]
		#print(tt,now,cnt)
	print(len(s)*cnt+now+1)

























if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


S = input()
T = input()
if not set(T).issubset(set(S)):
    print(-1)
    exit()

pos = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
for i, c in enumerate(S):
    pos[c].append(i)
ans = 0
cur_pos = 0
for t in T:
    nxt_idx = bisect_left(pos[t], cur_pos)
    if nxt_idx == len(pos[t]):
        ans += len(S)
        cur_pos = 0
        nxt_idx = bisect_left(pos[t], cur_pos)
        cur_pos = pos[t][nxt_idx]
    else:
        cur_pos = pos[t][nxt_idx]

print(ans + cur_pos + 1)

Submission status: Wrong Answer

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

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

n = len(s)
q = 0
r = 0
import bisect
for c in t:
    j = ord(c)-ord('a')
    if len(X[j]) == 0:
        print(-1)
        exit()
    idx = bisect.bisect_right(X[j], r)
    #print(X[j], idx)
    if idx == len(X[j]):
        q += 1
        r = X[j][0]
    else:
        r = X[j][idx]
    #print(q, r)
ans = q*n + r+1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
p = [[] for k in range(26)]
for k in range(len(s)):
    p[ord(s[k])-97].append(k)
for e in p:
    e.append(10**6)
ans = 0
now = -1
for e in t:
#    print(p[ord(e)-97][bisect.bisect_left(p[ord(e)-97],now)])
    if len(p[ord(e)-97]) == 1:
        print(-1)
        exit(0)
    q = p[ord(e)-97][bisect.bisect_left(p[ord(e)-97],now)]
    if q == 10**6:
        ans += len(s)-now+p[ord(e)-97][0]
        now = p[ord(e)-97][0]
    else:
        ans += q-now
        now = q
print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

from collections import defaultdict

nx = [defaultdict(lambda: -1) for i in range(len(S)+1)]
lastpos = defaultdict(lambda: 0)

SS = S+S
for i,c in enumerate(SS[::-1]):
    i = len(SS)-1-i
    if i < len(S):
        for k,v in lastpos.items():
            nx[i+1][k] = v-i
    lastpos[c] = i
for k,v in lastpos.items():
    nx[0][k] = v

ans = 0
for c in T:
    if nx[ans%len(S)][c] == -1:
        print(-1)
        exit()
    ans += nx[ans%len(S)][c]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()

n = len(s)

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

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

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

ans = 0
now = 0
for i in range(len(t)):
    c = ord(t[i]) - ord('a')
    j = bisect.bisect_right(pos[c], now)

    if j == len(pos[c]):
        print(-1)
        exit()
    now = pos[c][j]

    if now >= n:
        now -= n
        ans += n
print(ans + now + 1)

Submission status: Wrong Answer

Solution code:
import bisect

s = input()
t = input()

n = len(s)

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

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

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

ans = 0
now = 0
for i in range(len(t)):
    c = ord(t[i]) - ord('a')
    j = bisect.bisect_right(pos[c], now)

    if j == len(pos[c]):
        print(-1)
        exit()
    now = pos[c][j]

    if now > n:
        now -= n
        ans += n
print(ans + now + 1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

s = input()
t = input()

alp_d = {chr(ord('a') + i): [] for i in range(26)}
for i,si in enumerate(s):
    alp_d[si].append(i)

curr_i = 0
loop = 0
for ti in t:
    if not alp_d[ti]:
        print(-1)
        exit()
    # bより大きい最小要素のindex/value
    ind = bisect_right(alp_d[ti], curr_i)
    ind = ind if 0 <= ind < len(alp_d[ti]) else None
    detected_i = alp_d[ti][ind] if ind is not None else None
    if detected_i is not None:
        curr_i = detected_i
    else:
        loop += 1
        curr_i = min(alp_d[ti])

ans = loop*(len(s)) + curr_i+1
print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

from collections import defaultdict

nx = [defaultdict(lambda: -1) for i in range(len(S))]
lastpos = defaultdict(lambda: 0)

SS = S+S
for i,c in enumerate(SS[::-1]):
    i = len(SS)-1-i
    if i < len(S):
        for k,v in lastpos.items():
            nx[i][k] = v-i
    lastpos[c] = i

ans = 0
for c in T:
    if nx[ans%len(S)][c] == -1:
        print(-1)
        exit()
    ans += nx[ans%len(S)][c]
print(ans + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    s = input()
    N = len(s)
    # sの出現位置を保持
    si = [[] for _ in range(26)]
    for i in range(N):
        si[ord(s[i])-ord('a')].append(i)

    # s'の何文字目までで十分かtの各文字に関して調べる
    ans = -1
    t = input()
    M = len(t)
    for j in range(M):
        ti = si[ord(t[j])-ord('a')]
        if len(ti)==0:
            print(-1)
            exit()
        d = bisect_right(ti,ans%N)
        if d == len(ti):
            ans += (ti[0]-ans%N)%N
        else:
            ans += ti[d]-ans%N
    print(ans+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

alpha2num = lambda c: ord(c) - ord('a')

S2 = [[] for i in range(26)]
for i in range(len(s)):
  S2[alpha2num(s[i])].append(i)
  
#print(S2)
time = 0
place = 0
for i in range(len(t)):
  now = alpha2num(t[i])
  if S2[now] == []:
    print(-1)
    quit()
  else:
    index = bisect.bisect_left(S2[now], place)
    if index == len(S2[now]):
      place = S2[now][0]
      time += 1
    else:  
      place = S2[now][index]
  #print(place, time)  
    
    
ans = len(s) * time + place + 1
print(ans)

Submission status: Wrong Answer

Solution code:
s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	if nx.get(('.',c)) is None:
		nx[('.',c)],k = i+1,0
		for j in range(i+1,len(x)):
			if nx.get((c,x[j])) is None:
				nx[(c,x[j])] = j-i-k
			if j<len(s) and c==x[j]:
				k = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

Submission status: Wrong Answer

Solution code:
s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	if nx.get(('.',c)) is None:
		nx[('.',c)],k = i+1,0
		for j in range(i+1,i+len(s)):
			if nx.get((c,x[j])) is None:
				nx[(c,x[j])] = j-i-k
			if j<len(s) and c==x[j]:
				k = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

Submission status: Wrong Answer

Solution code:
s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	if nx.get(('.',c)) is None:
		nx[('.',c)] = i+1
		for j in range(i+1,i+len(s)):
			if nx.get((c,x[j])) is None:
				nx[(c,x[j])] = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

Submission status: Wrong Answer

Solution code:
s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	if nx.get(('.',c)) is None:
		nx[('.',c)] = i+1
	else:
		continue
	for j in range(i+1,len(x)):
		if nx.get((c,x[j])) is None:
			nx[(c,x[j])] = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  t=S()
  lens=len(s)

  d={}
  for i,x in enumerate(s):
    if x in d:
      d[x].append(i)
    else:
      d[x]=[i]
  # print(d)

  ans=0
  ind=0
  for x in t:
    if x not in d:
      return -1

    v=d[x]
    l=0
    r=len(v)-1
    if ind==v[l] or ind==v[r]:
      ind+=1
      ans+=1
      continue
    if ind<v[l]:
      zoubun=v[l]-ind+1
      ans+=zoubun
      ind=v[l]+1
      continue
    if v[r]<ind:
      zoubun=lens-ind-1
      zoubun+=v[l]+2
      ans+=zoubun
      ind=v[l]+1
      continue

    while r-l>1:
      m=(r-l)//2
      if v[m]<ind:
        l=m
      else:
        r=m
    zoubun=v[l]-ind
    ans+=zoubun
    ind=v[l]

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  t=S()
  lens=len(s)

  d={}
  for i,x in enumerate(s):
    if x in d:
      d[x].append(i)
    else:
      d[x]=[i]
  # print(d)

  ans=0
  for x in t:
    if x not in d:
      return -1

    v=d[x]
    ind=ans%lens
    l=0
    r=len(v)-1
    if ind==v[l] or ind==v[r]:
      ind+=1
      ans+=1
      continue
    if ind<v[l]:
      zoubun=v[l]-ind+1
      ans+=zoubun
      ind=v[l]+1
      continue
    if v[r]<ind:
      zoubun=lens-ind-1
      zoubun+=v[l]+2
      ans+=zoubun
      ind=v[l]+1
      continue

    while r-l>1:
      m=(r-l)//2
      if v[m]<ind:
        l=m
      else:
        r=m
    zoubun=v[l]-ind
    ans+=zoubun
    ind=v[l]

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

f = defaultdict(list)
d = {}


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

len_s = len(s)

for i in range(len_s):
    f[s[i]].append(i)

next_char = [[0] * len_s for _ in range(len(f))]

j = 0
for k, v in f.items():
    d[k] = j
    l = 0
    for i in range(len_s):
        if v[l] == i:
            l += 1
            if l == len(v):
                l = 0
        next_char[j][i] = v[l]
    j += 1

m = 0

for x in t:
    if d.get(x) == None:
        m = -2
        break
    else:
        j = d[x]
        r = m % len_s
        n = next_char[j][r]
        if r >= n:
            m += len_s - (r-n)
        else:
            m += n - r

print(m+1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)

check = set(list(t))
t_s = ""
for ss in s:
    if ss in check:
        t_s += ss

if len(set(list(t_s)))<len(check):
    print(-1)
    exit(0)

c = [[0]*(max(m,n)+1) for _ in range(26)]
for i, ss in enumerate(s):
    c[ord(ss)-ord("a")][c[ord(ss)-ord("a")][-1]] = i
    c[ord(ss)-ord("a")][-1] += 1

# for i,cc in enumerate(c):
#     print(chr(97+i),":",*cc)

tmp_counter = [0]*26
t_idx = [0]*m
for i,tt in enumerate(t):
    t_idx[i] = c[ord(tt)-ord("a")][tmp_counter[ord(tt)-ord("a")]]
    if tmp_counter[ord(tt)-ord("a")] < c[ord(tt)-ord("a")][-1]-1:
        tmp_counter[ord(tt)-ord("a")] += 1

# print(t_idx)

count = 0
ans = 0
for i,ti in enumerate(t_idx):
    if i == len(t_idx)-1:
        ans = t_idx[i]+1
        break
    if t_idx[i+1]<t_idx[i]:
        count += 1
ans += count*n
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
alp = []

for i in range(26):
  array = []
  now = chr(ord('a') + i)
  for j in range(lenS):
    if s[j] == now:
      array.append(j)
  alp.append(array)

count,now = 0,0

for i in range(lenT):
  j = ord(t[i])-ord('a')
  if alp[j]:
    next = bisect(alp[j],now)
    if next == len(alp[j]):
      count += 1
      now = alp[j][0]
    else:
      now = alp[j][next]
  else:
    print(-1)
    exit()

ans = count*lenS+now+1

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
alp = []

for i in range(26):
    array = []
    now = chr(ord('a') + i)
    for j in range(lenS):
        if s[j] == now:
            array.append(j)
    alp.append(array)

count,now = 0,-1

for i in range(lenT):
  j = ord(t[i])-ord('a')
  if alp[j]:
    next = bisect_left(alp[j],now)
    if next == len(alp[j]):
      count += 1
      now = alp[j][0]
    else:
      now = alp[j][next]
  else:
    print(-1)
    exit()

ans = count*lenS+now+1

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
alp = []

for i in range(26):
    array = []
    now = chr(ord('a') + i)
    for j in range(lenS):
        if s[j] == now:
            array.append(j)
    alp.append(array)

count,now = 0,0

for i in range(lenT):
  j = ord(t[i])-ord('a')
  if alp[j]:
    next = bisect_left(alp[j],now)
    if next == len(alp[j]):
      count += 1
      now = alp[j][0]
    else:
      now = alp[j][next]
  else:
    print(-1)
    exit()

ans = count*lenS+now+1

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
l = [0]*26
alp = list("abcdefghijklmnopqrstuvwxyz")
for i in range(26):
  for j in range(lenS):
    if alp[i] == s[j] and l[i] == 0:
      l[i] = j+1
      break
count,now = 0,0
for i in range(lenT):
  b = bisect_left(alp,t[i])
  if l[b] == 0:
    print(-1)
    exit()
  if now > l[b]:
    count += 1
  now = l[b]

ans = count*lenS+now
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s = list(input())
t = list(input())
lenT = len(t)
lenS = len(s)
l = [0]*26
alp = list("abcdefghijklmnopqrstuvwxyz")
for i in range(26):
  for j in range(lenS):
    if alp[i] == s[j] and l[i] == 0:
      l[i] = j+1
      break
count,now = 0,0
for i in range(lenT):
  b = bisect_left(alp,t[i])
  if l[b] == 0:
    print(-1)
    exit()
  if now > l[b]:
    count += 1
  now = l[b]

ans = count*lenS+now
if ans > max(l):
  print(ans)
else:
  print(max(l))

Submission status: Wrong Answer

Solution code:
def find(base, indexes):
    n = len(indexes)
    ng = -1
    ok = n

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if indexes[mid] > base:
            ok = mid
        else:
            ng = mid

    return indexes[0] if ok == n else indexes[ok]


s = input()
t = input()

s_set = set(s)
t_set = set(t)

if t_set.issubset(s_set) is False:
    print(-1)
    exit(0)

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

for i in range(len(s)):
    c = s[i]
    idx = ord(c) - ord("a")
    s_indxes[idx].append(i)

base = -1
loop = 0
for i in range(len(t)):
    c = t[i]
    idx = ord(c) - ord("a")
    n_base = find(base, s_indxes[idx])

    if n_base < base:
        loop += 1

    base = n_base

print(loop * len(s) + base + 1)

Submission status: Wrong Answer

Solution code:
def find(base, indexes):
    ng = -1
    ok = len(indexes)

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if indexes[mid] >= base:
            ok = mid
        else:
            ng = mid

    return indexes[0] if ok == len(indexes) else indexes[ok]


s = input()
t = input()

s_set = set(s)
t_set = set(t)
sub_set = s_set - t_set

if t_set.issubset(s_set) is False:
    print(-1)
    exit(0)

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

for i in range(len(s)):
    c = s[i]
    idx = ord(c) - ord("a")
    s_idx[idx].append(i)


base = -1
loop = 0

for i in range(len(t)):
    c = t[i]
    n_base = find(base, s_idx[ord(c) - ord("a")])
    if n_base <= base:
        loop += 1
    base = n_base

print(base + loop * len(s) + 1)

Submission status: Wrong Answer

Solution code:
def find(base, indexes):
    ng = -1
    ok = len(indexes)

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if indexes[mid] >= base:
            ok = mid
        else:
            ng = mid

    return indexes[0] if ok == len(indexes) else indexes[ok]


s = input()
t = input()

s_set = set(s)
t_set = set(t)
sub_set = s_set - t_set

if t_set.issubset(s_set) is False:
    print(-1)
    exit(0)

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

for i in range(len(s)):
    c = s[i]
    idx = ord(c) - ord("a")
    s_idx[idx].append(i)


base = -1
loop = 0

for i in range(len(t)):
    c = t[i]
    n_base = find(base, s_idx[ord(c) - ord("a")])
    if n_base < base:
        loop += 1
    base = n_base

print(base + loop * len(s) + 1)

Submission status: Wrong Answer

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

N = len(s)

s_i = 0
a = 0
for t_j in t:
    if t_j in s[s_i:N-1]:
        s_i = s.index(t_j)
    elif t_j in s:
        a += 1
        s_i = s.index(t_j)
    else:
        print(-1)
        exit()

print(N*a+s_i+1)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

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

n = len(S)
i = -1
cnt = 0
for t in T:
    if t not in ctr:
        i = -2
        break

    j = bisect_right(ctr[t], i)
    if j == len(ctr[t]):
        idx = ctr[t][0]
    else:
        idx = ctr[t][j]

    if i >= idx:
        cnt += 1
    i = idx

print(cnt * n + i + 1)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

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

n = len(S)
i = 0
cnt = 0
for t in T:
    if t not in ctr:
        i = -2
        break

    j = bisect_right(ctr[t], i)
    if j == len(ctr[t]):
        idx = ctr[t][0]
    else:
        idx = ctr[t][j]
        
    if i >= idx:
        cnt += 1
    i = idx

print(cnt * n + i + 1)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
from bisect import bisect_right

S = input()
T = input()

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

n = len(S)
i = 0
cnt = 0
for t in T:
    if t not in ctr:
        i = -2
        break

    j = bisect_right(ctr[t], i)
    if j == len(ctr[t]):
        cnt += 1
        j -= 1
    i = ctr[t][j]

print(cnt * n + i + 1)

Submission status: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    s = input()
    ls = len(s)
    t = input()
    idx = 0
    for i in t:
        nt = s.find(i,idx%ls+1)
        ntl = s.find(i)
        if ntl == -1:
            print(-1)
            exit()
        elif nt == -1:
            idx = (idx//ls)*ls+ls+ntl
        else:
            idx = (idx//ls)*ls+nt
    print(idx+1)
    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    s = input()
    ls = len(s)
    t = input()
    s *= 2
    idx = 0
    for i in t:
        nt = s.find(i,idx%ls+1)
        if nt == -1:
            print(-1)
            exit()
        else:
            idx = (idx//ls)*ls+nt
    print(idx+1)
    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
"""
Tの文字にたいして、Sのインデックスをリストで持たせる
Tの頭から順繰りにたし上げていく（Loop数を数えること）
自分よりも大きい要素があれば、それを使うし、
なければ最も小さい要素を使いつつ、Loop数をCountUp
bisect_left()かな？

0123456
contest

01234567
sentence

s=[5]   -> 5  (6moji)
e=[4]   -> 7*1+4 (12moji)
n=[2]   -> 7*2+2 = 16
t=[3,6] -> 7*2+3 = 17
e=[4]   -> 7*2+4 = 18
n=[2]   -> 7*3+2 = 23
c=[0]   -> 7*4+0 = 28
e=[4]   -> 7*4+4 = 32 ( 33moji)
"""

from bisect import bisect_right, bisect_left
S = input()
T = input()

def calc(ch):
  return ord(ch) - ord('a')

## Tに含まれる文字に対し、Sのインデックスをふる
LST = [[] for _ in range(26)]
for t in T:
  nt = calc(t)
  if len(LST[nt]) > 0:
    continue
  for i in range(len(S)):
    if t == S[i]:
      LST[nt].append(i)
  if len(LST[nt]) == 0:
    print(-1)
    exit(0)
    
NS = len(S)
## Tの文字に対して順繰りにたしあげる
NofLoop = 0
now = 0
for t in T:
  nt = calc(t)
  rel_now = now - NofLoop * NS
  if rel_now < LST[nt][0] :
    now = NofLoop * NS + LST[nt][0]
  elif LST[nt][-1] <= rel_now:
    NofLoop += 1
    now = NofLoop * NS + LST[nt][0]
  else:
    idx = bisect_right(LST[nt], rel_now)
    now = NofLoop * NS + LST[nt][idx]
    
print(now+1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    import copy
    from bisect import bisect_left
    from collections import defaultdict
    input = sys.stdin.readline
    s, t = input().strip(), input().strip()
    lens = len(s)
    index_list = defaultdict(list)
    leng = defaultdict(int)
    for i, ss in enumerate(s):
        index_list[ss].append(i)

    for s, i in index_list.items():
        if i:
            leng[s] = len(index_list[s])

    prev = -1
    ans = 0
    for tt in t:
        if tt not in leng:
            print(-1)
            return False
        p = bisect_left(index_list[tt], prev)
        # print('tt={}, prev={}, p={}, ans={}'.format(tt, prev, p, ans))
        if p < leng[tt]:
            prev = index_list[tt][p]
        else:
            prev = index_list[tt][0]
            ans += lens

    print(ans+prev+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

s = input()
t = input()

if not set(s) >= set(t):
	print(-1)
	exit()

dic = defaultdict(list)
for i, char in enumerate(s, 1):
	dic[char].append(i)

loop = 0
index = -1
for i in range(len(t)):
	idx = bisect_left(dic[t[i]], index)
	if idx < len(t[i]):
		index = dic[t[i]][idx]
	else:
		idx = dic[t[i]][0]
		index = idx
		loop += 1

print(len(s)*loop+index)

Submission status: Wrong Answer

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

dict_s = {}
for i, c in enumerate(s * 2):
    dict_s[c] = dict_s.get(c, []) + [i]


dict_next_i = {
    c: [min(j for j in dict_s[c] if j > i) for i in range(n)]
    for c in dict_s.keys()
}


def next_i(i, c):
    if c not in dict_s.keys():
        return -1
    else:
        return n * (i // n) + dict_next_i[c][i % n]


def answer():
    i = 0
    for c in t:
        i = next_i(i, c)
        if i == -1:
            return -1
    return i + 1  # 1-origin


print(answer())

Submission status: Wrong Answer

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

dict_s = {}
for i, c in enumerate(s):
    dict_s[c] = dict_s.get(c, []) + [i]


def answer():
    i = 0
    for c in t:
        if c not in dict_s.keys():
            return -1
        d, r = i // n, i % n
        list_i = [n * d + index if index > r else n * (d + 1) + index for index in dict_s[c]]
        i = min(list_i)
    return i + 1  # 1-origin


print(answer())