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: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,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 LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  ln=len(s)

  a=set(s)
  b=set(t)

  for x in b:
    if x not in a:
      return -1

  cnt=-1
  ans=0
  for x in t:
    while True:
      cnt+=1
      ans+=1
      if s[cnt%ln]==x:
        break

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
l=len(s)
lt=len(t)
ctr=0
a=[0]*26
for i in t:
  a[ord(i)-ord('a')]=1
for i in s:
  if a[ord(i)-ord('a')]==1:a[ord(i)-ord('a')]=0
if sum(a)>0:print(-1)
else:
  j=0
  for i in range(10**100):
    if t[j]==s[i%l]:
      j+=1
      if j==lt:break
    ctr+=1
  print(ctr+1)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
from collections import defaultdict
d = defaultdict(list)
for i, e in enumerate(s):
  d[e].append(i)

for e in t:
  if e not in d:
    print(-1)
    exit()
cur = -1
loop = 0
for e in t:
  found = False
  for idx in d[e]:
    if (loop*len(s))+idx>cur:
      cur = (loop*len(s))+idx
      found = True
      break
  if not found:
    loop += 1
    for idx in d[e]:
      if (loop*len(s))+idx>cur:
        cur = (loop*len(s))+idx
        found = True
        break
print(cur+1)

Submission status: Time Limit Exceeded

Solution code:
s = input() # これを繰り返しまくる
t = input() # これを探す

# 判定
s_set = set(s)
s_len = len(s)

if all((t_ in s_set) for t_ in t):
    ans = 0

    # loop
    ss = s

    for t_ in t:
        find_plus_one = ss.find(t_) + 1
        ss = ss[find_plus_one:]
        if len(ss) < s_len:
            ss += s
        ans += find_plus_one
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def first_check(s, t):
    result = True
    for i in range(len(t)):
        if not t[i] in s:
            result = False
            break
    return result

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

result = 0
len_t = len(t)

flag = True

if first_check(s, t):
    while flag:
        for i in range(len(s)):
            if t[0] == s[i]:
                del t[0]
                len_t -= 1
            if len_t == 0:
                flag = False
                break
        result += i + 1
else:
    result = -1

print(result)

Submission status: Time Limit Exceeded

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

res = 0

N = 100000
for i in range(N):
    _s = s
    while len(_s) > 0 and len(t) > 0:
        if t[0] in _s:
            _index = _s.index(t[0])
            res += _index + 1
            _s = _s[_index + 1:]
            t = t[1:]
        else:
            res += len(_s)
            break
    if len(t) == 0:
        print(res)
        exit(0)

print(-1)

Submission status: Time Limit Exceeded

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

for i in range(len(t)):
  if t[i] in s:
    continue
  else:
    print(-1)
    sys.exit()

cnt=0
i=0
while i<len(t):
  
  if t[i]==s[cnt%len(s)]:
    i+=1
  
  cnt+=1
  
print(cnt)

Submission status: Time Limit Exceeded

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

ps, pt = 0, 0
cnt = 0

flg = False
for x in t:
  if not x in s:
    flg = True
  
if flg:
  print(-1)
else:
  tmp = 0
  while pt<len(t):
    while ps<len(s):
      if pt<len(t) and t[pt]==s[ps]:
        pt += 1
        tmp = ps
        ps += 1
      else:
        ps += 1
    cnt += 1
    ps = 0
  print((cnt-1)*len(s)+tmp+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  originalStr = input()
  target = input()

  blContain = False
  for char in list(target):
    if char not in list(originalStr):
      blContain = False
      break
    blContain = True
  
  if not blContain:
    print("-1")
    return

  count = 0
  bl_list = []

  j=0
  target_char = list(target)[j]

  while True:
    for char in list(originalStr):
      count += 1
      if char == target_char:
        bl_list.append(True)
      
        if len(bl_list) == len(target):
          print(count)
          return

        j += 1
        target_char = list(target)[j]


  return


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

s = list(input())
t = input()
tmp=0
ans=0
flag=True
for ch in t:
    if ch in s:
        while ch != s[tmp]:
            ans += 1
            tmp = (tmp+1)%len(s)
        ans += 1
        tmp = (tmp+1)%len(s)
    else:
        flag = False
        break

if flag:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import collections
s = input()
t = input()
if not set(t).issubset(set(s)): print(-1)
else:
    d = collections.defaultdict(list)
    for i, letter in enumerate(s):
        d[letter].append(i+1)
    prev = 0
    cnt = 0
    for target in t:
        for num in d[target]:
            if num > prev:
                prev = num
                break
        else:
            cnt += 1
            prev = d[target][0]
    print(cnt * len(s) + prev)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    print([i-N-1 for i in range(len(conc)) if Z[i] == N])


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return m, n


def solve(s: str, t: str):

    T = len(t)
    S = len(s)
    counter = 0
    curr = 0
    head = 0
    updated = True
    while updated:
        updated = False
        for i, c in enumerate(s):
            if c == t[curr]:
                curr += 1
                updated = True
                if curr == T:
                    counter += i
                    break
        if curr == T:
            break
        else:
            counter += S
    if updated == False:
        print(-1)
    else:
        print(counter+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: Time Limit Exceeded

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

if sum(moji in set(s) for moji in t)!=len(t):print(-1)
n_itr=0
while len(t)!=0:
    n_itr+=1
    for i,moji in enumerate(s):
        if len(t)!=0 and t[0] == moji:
            t=t[1:]
            j=i
    if len(t)==0:
        print((n_itr-1)*len(s)+j+1)

Submission status: Time Limit Exceeded

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

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

hoge = 0
nyoro = ls-1
count_t = 0
count_s = 0

while count_t < lt:
    while count_s < ls:
        if t[count_t] == s[count_s]:
            nyoro = count_s
            count_t += 1
            if count_t == lt:
                break
        elif nyoro == count_s:
            print(-1)
            count_t = lt+1
            break
            
        count_s += 1
    else:
        count_s = 0
        hoge += 1
if count_t == lt:
    print(hoge*ls+nyoro+1)

Submission status: Time Limit Exceeded

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

s_lis = set(s)
t_lis = set(t)

if t_lis <= s_lis:
  k = t[0]
  c = 0
  i = 0
  j = -1
  while i != len(t):
    while True:
      c += 1
      j = (j + 1)%len(s)

      if t[i] == s[j]:
        #print(c,t[i])
        i += 1
        break
        
   
  print(c)
  
  
  
else:
  print(-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def gg(cc, c, l, d):
    if d[c][-1] <= cc:
        return d[c][1], l+1
    ll = d[c]
    mx, mn = len(ll)-1, 0
    x = (mx - mn)//2
    while True:
        if ll[x] <= cc and cc < ll[x+1]:
            return ll[x+1], l
        if cc < ll[x]:
            mx = x
            x = (mx-mn)//2
        else:
            mn = x
            x = (mx-mn)//2

def main():
    ss=set(s)
    tt=set(t)
    if len(tt - ss) != 0: 
        return -1
    d = dict()
    for i, c in enumerate(s):
        if c not in d:
            d[c] = [0]
        d[c].append(i+1)
    cc, l = 0, 0
    for c in t:
        cc, l = gg(cc, c, l, d)
    return l*len(s) + cc

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

for i in range(len(t)):
    if(list(s).count(t[i])==0):
        print("-1")
        exit()

p=0
i = 0
while True:
    for j in range(len(s)):
        if(t[p]==s[j]):
            p+=1
        if(len(t)==p):break
    if(len(t)==p):break
    i+=1
print(i*len(s)+j+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

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

q = deque([])

for x in t:
  q.append(x)

cnt = 0
for i in range(len(t)):
  for x in s:
    cnt+=1
    if x == q[0]:
      q.popleft()
      if len(q)<1:
        print(cnt)
        sys.exit()

print('-1')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

import sys

s1 = input()
s2 = input()

n1 = 0
t1 = 0

for i1 in range(len(s2) ):
    t1 =  s1.find(s2[i1])
    if t1 == -1:
        print(t1)
        sys.exit()
    n1 += t1 + 1
    s1 = s1[t1 + 1:] + s1[0:t1 + 1]

print(n1)

Submission status: Time Limit Exceeded

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

ti = 0
si = 0
tl = len(t)
sl = len(s)
count = 0
found = False
while ti < tl:
	if s[si] == t[ti]:
#		print(s[si])
		si += 1
		ti += 1
		found = True
	else:
		si += 1
	if si == sl:
		if not found:
			count = -1
			break
		si = 0
		found = False
	count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
s=input()
t=input()
for i in t:
    if i not in s:
        print("-1")
        sys.exit()
l=len(s)
ans=0
p=0
for i in t:
    j=p
    while True:
        #print("{} ".format(s[j]),end="")
        if i==s[j]:
            ans+=1
            if j!=l-1:
                p=j+1
            else:
                p=0
            break
        elif j==l-1:
            ans+=1
            j=-1
        else:
            ans+=1
        j+=1
    #print()

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())



def run():
    S, T = input(), input()
    dic = defaultdict(lambda : [])
    for i, s in enumerate(S):
        dic[s].append(i)

    k = -1
    ans = 1
    for t in T:
        if t in dic.keys():
            i = bisect.bisect_right(dic[t], k)
            if i >= len(dic[t]):
                k = dic[t][0]
                ans += 1
            else:
                k = dic[t][i]

        else:
            print(-1)
            return

    print((ans-1) * len(S) + k +1)


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
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()
  n=len(s)
  t=S()
  n2=len(t)

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

  # print(d)
  i=0
  j=0
  ans=1
  while j<n2:
    check=t[j]
    if check not in d:
      return -1
    l=d[check]
    if i<l[0]:
      ans+=l[0]-i+1
      i=l[0]+1
      j+=1
    elif l[-1]<i:
      ans+=n-(i+1)+l[0]+2
      i=l[0]+1
      j+=1
    else:
      if i==l[0]:
        ans+=1
        i+=1
        j+=1
      elif i==l[-1]:
        ans+=1
        i+=1
        j+=1
      else:
        left=0
        right=len(l)
        while right-left>1:
          m=(right+left)//2
          if l[m]>=i:
            right=m
          else:
            left=m
          # print(right,left,m,i)
        ans+=l[right]-i+1
        i=l[right]+1
        j+=1

    # print(i,ans)

    i%=n

  return ans-1

# main()
print(main())

Submission status: Accepted

Solution code:
from bisect import bisect_left


S = input()
T = input()
if any(c not in S for c in T):
    print(-1)
    exit()

N = len(S)
pos = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
for i in range(N):
    pos[S[i]].append(i)

loop = 0
cur = 0
for c in T:
    nxt = bisect_left(pos[c], cur)
    if nxt == len(pos[c]):
        loop += 1
        cur = pos[c][0] + 1
    else:
        cur = pos[c][nxt] + 1
print(loop * N + cur)

Submission status: Accepted

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

def s2n(s):
    return ord(s)-97

ALF=[[] for _ in [0]*26]
for i in range(len(S)):
    ALF[s2n(S[i])].append(i)

ALF_T=[0]*26
seqT=[]
res=0
for t in T:
    i=s2n(t)
    if ALF[i]:
        if seqT:
            a=seqT[-1]
        else:
            a=-1
        j=br(ALF[i],a)
        seqT.append(ALF[i][j%len(ALF[i])])
    else:
        res=-1
if res>=0:
    tmp=[]
    m=-1
    for n in seqT:
        if m<n:
            tmp.append(n)
        else:
            res+=1
            tmp=[n]
        m=n
    res=res*len(S)+tmp[-1]+1
print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left

S = list(input())
T = list(input())
dict_s = {}
for i,val in enumerate(S):
    if val in dict_s:
        dict_s[val].append(i)
    else:
        dict_s[val] = [i]

l_cunt = 0
now_point = -1
for i,val in enumerate(T):
    if val in dict_s:
        tmp_point = bisect_left(dict_s[val],now_point)
        if tmp_point == len(dict_s[val]):
            l_cunt += 1
            tmp_point = 0
        now_point = dict_s[val][tmp_point]+1
    else:
        print(-1)
        exit()

print(l_cunt*len(S)+now_point)

Submission status: Accepted

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

n = len(s)
m = len(t)
s += s
next = [[-1] * 26 for _ in range(len(s) + 1)]

# 場所iから、次の文字jへの場所、みたいなテーブル
# 後ろから更新してくと最短距離になる
# next[i]は場所iを含む
for i in range(len(s) - 1, -1, -1):
    c = ord(s[i]) - ord('a')
    for j in range(26):
        if j == c:
            next[i][j] = i
        else:
            next[i][j] = next[i + 1][j]
now = 0
ans = 0
for i in range(m):
    c = ord(t[i]) - ord('a')
    if next[now][c] == -1:
        print(-1)
        exit()
    ans += next[now][c] - now + 1
    now = next[now][c] + 1
    if now >= n:
        now -= n
print(ans)

Submission status: Accepted

Solution code:
def main():
    from functools import lru_cache
    import bisect
    S = input()
    T = input()
    if set(S) & set(T) != set(T):
        print(-1)
    else:
        lt = len(T)
        ls = len(S)
        st = set(T)
        D = dict()
        for t in st:
            D[t] = list()
            for i, s in enumerate(S):
                if t == s:
                    D[t].append(i)
        pre = -1
        cnt = 0

        @lru_cache(maxsize=None)
        def judge(pre, t):
            X = D[t]
            index = bisect.bisect(X, pre)
            if len(X) == index:
                return (X[0], True)
            else:
                return (X[index], False)

        for t in T:
            J = judge(pre, t)
            pre = J[0]
            if J[1]:
                cnt += 1

        print(cnt * len(S) + pre + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

s = input()
t = input()

n = len(s)

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

ans = 0
now = -1
for i in range(len(t)):
    a = ord(t[i]) - ord('a')
    nxt = bisect_right(mp[a], now)
    if len(mp[a]) == nxt:
        print(-1)
        exit()

    ans += mp[a][nxt] - now
    now = mp[a][nxt]
    if now >= n:
        now -= n

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()

n = len(s)

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

ans = 0
now = -1
for i in range(len(t)):
    a = ord(t[i]) - ord('a')
    nxt = bisect_right(mp[a], now)
    if len(mp[a]) == nxt:
        print(-1)
        exit()

    now = mp[a][nxt]
    if now >= n:
        ans += n
        now -= n

print(ans + now + 1)

Submission status: Accepted

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)

ans = 0
import bisect
cur = -1
for c in t:
    j = ord(c)-ord('a')
    if len(X[j]) == 0:
        print(-1)
        exit()
    k = bisect.bisect_right(X[j], cur)
    if k != len(X[j]):
        cur = X[j][k]
    else:
        cur = X[j][0]
        ans += len(s)
ans += cur+1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import *

s,t = input(),input()
before,count = len(s),0
idx = defaultdict(list)

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

for i,l in enumerate(s):
  idx[l] += [i]
  
for c in t:
  N = idx[c]
  index = bisect_left(N, before)
  if index > len(N) - 1:
    before = N[0] + 1
    count += 1
  else:
    before = N[index] + 1
    
print((count - 1) * len(s) + before)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left
s = input()
t = input()
ids = defaultdict(list)
for i, c in enumerate(s):
    ids[c].append(i)
i = 0
ans = 0
for c in t:
    if c not in ids:
        print(-1)
        exit()
    ls = ids[c]
    j = bisect_left(ls, i)
    if j == len(ls):
        ans += len(s)
        i = ls[0]+1
    else:
        i = ls[j]+1
print(ans+i)

Submission status: Accepted

Solution code:
import sys
import bisect

# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    S = list(input())
    T =list(input())

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

    orda =ord("a")

    for i in range(len(S)):
        G[ord(S[i])-orda].append(i)

    count =0
    p=-1
    for j in range(len(T)):
        tord = ord(T[j]) -orda
        if G[tord]!=[]:
            if G[tord][-1]<p+1:
                p=-1
                count+=1

            gp =bisect.bisect_left(G[tord],p+1)
            p =G[tord][gp]

        else:
            print(-1)
            exit()


    print(count * len(S)+p+1)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()
if set(list(s + t)) != set(list(s)):
    print(-1)
    exit()
check = set(list(t))
dic = {}
for Str in check:
    dic[Str] = []
for i in range(len(s)):
    if s[i] in check:
        dic[s[i]] += [i]
times = 0
now = -1
for p in t:
    if now >= dic[p][-1]:
        now = dic[p][0]
        times += 1
    else:
        now = dic[p][bisect.bisect(dic[p], now)]
print(len(s) * times + now + 1)

Submission status: Accepted

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

n = len(s)
s = s * 2


r = {}
for i, v in enumerate(s):
    if v in r.keys():
        r[v].append(i+1)
    else:
        r[v] = [i+1]

now = 0

lt = len(t)
for v in t:
    if v in r.keys():
        index = bisect_left(r[v], now % n + 1)
        tmp = r[v][index]
        now += tmp - now % n
    else:
        print(-1)
        exit()

print(now)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict as dd

def main():

  s=input()
  t=input()
  n=len(s)

  dic=dd(list)
  for idx,i in enumerate(s*2):
    dic[i].append(idx)

  ans,p=0,-1
  for i in t:
    if i not in dic.keys():
      print(-1)
      exit()
    p=dic[i][bisect_left(dic[i], p+1)]
    if p>=n:
      p-=n
      ans+=n

  print(ans+p+1)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import bisect

s=input()
t=input()
n=len(s)

dic={}
for idx,i in enumerate(s*2):
  if i in dic.keys():
    dic[i].append(idx)
  else:
    dic[i]=[idx]

ans,p=0,-1
for i in t:
  if i not in dic.keys():
    print(-1)
    exit()
  p=dic[i][bisect.bisect_left(dic[i], p+1)]
  if p>=n:
    p-=n
    ans+=n
  
print(ans+p+1)

Submission status: Accepted

Solution code:
import bisect

s=input()
t=input()
n=len(s)*2

dic={}
for idx,i in enumerate(s*2):
  if i in dic.keys():
    dic[i].append(idx)
  else:
    dic[i]=[idx]

#print(dic)
    
ans=k=0
before='-1'
for i in t:
  if i not in dic.keys():
    print(-1)
    exit()
  t=bisect.bisect_left(dic[i], ans%n)
  if before==i:
    t+=1
  if len(dic[i])==t:
    t=0
    k+=n
  ans=dic[i][t]+k
  before=i
  
print(ans+1)

Submission status: Accepted

Solution code:
s = input()
t = input()
next_alpha = [[-1] * len(s) for _ in range(30)] # (文字種a, 今いるsのインデックス)=>(次のaが出るsのインデックス)
for i, s_ in enumerate(s):
    j = ord(s_) - 97
    for k in range(i, -1, -1):
        if next_alpha[j][k] != -1:
            break
        next_alpha[j][k] = i

ans = 0
for t_ in t:
    i = ans % len(s)
    tmp = next_alpha[ord(t_) - 97][i]
    if tmp == -1:
        ans += (-1 * ans) % len(s)
        i = ans % len(s)
        tmp = next_alpha[ord(t_) - 97][i]
    if tmp == -1:
        ans = -1
        break
    else:
        ans += tmp - (i - 1)
print(ans)

Submission status: Accepted

Solution code:
import string
import bisect
s=input()
t=input()
S=[[] for _ in range(26)]
a=string.ascii_lowercase
now=-1
ans=-1
count=0
for i in range(len(s)):
    for j in range(26):
        if s[i]==a[j]:
            S[j].append(i)
            break
for i in range(len(t)):
    for j in range(26):
        if t[i]==a[j]:
            break
    if len(S[j])==0:
        break
    nex=bisect.bisect_right(S[j],now)
    if nex==len(S[j]) or now>=S[j][nex]:
        count+=1
        now=S[j][0]
    else:
        now=S[j][nex]
    if i==len(t)-1:
        ans=count*(len(s))+now+1
print(ans)

Submission status: Accepted

Solution code:
import bisect

s = input()
t = input()
n = len(s)
s0 = {}
for i in range(n):
    s0.setdefault(s[i], [])
    s0[s[i]].append(i)
num1 = 0
num2 = -1
flag = True
for i in t:
    if i not in s:
        flag = False
        break
    num = bisect.bisect_right(s0[i], num2)
    if num == len(s0[i]):
        num1 += 1
        num2 = s0[i][0]
    else:
        num2 = s0[i][num]
if flag == True:
    print(num1 * n + num2 + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
"""
tの先頭から、できるだけ長い文字列を一回のsで消費するゲーム
できるだけ短い時間で、残っているtの先頭からどこまでを一回で消費できるかを判断したい。
部分文字列DPのときにやったみたいに、ns[i][j] => i番目より後ろで、つぎに文字jが出てくるインデックス
という表を作っておけばよい。
"""

S = input()
T = input()
N = len(S)
dp = [[-1]*26 for _ in range(N+1)]
for i in range(N):
    s = S[i]
    dp[i][ord(s)-ord("a")] = i+1

for i in range(N-2,-1,-1):
    for j in range(26):
        if dp[i][j] == -1:
            dp[i][j] = dp[i+1][j]

cycleCnt = 0
sInd = 0
for i in range(len(T)):
    if dp[sInd][ord(T[i])-ord("a")] == -1:
        cycleCnt += 1
        sInd = 0
        if dp[sInd][ord(T[i])-ord("a")] == -1:
            print(-1)
            exit()
    sInd = dp[sInd][ord(T[i])-ord("a")]
else:
    print(cycleCnt*N+sInd)

Submission status: Accepted

Solution code:
from bisect import bisect

def ctoi(c):
    return ord(c) - ord('a')

def solve():
    S = input()
    T = input()
    N = len(S)
    idx = [[] for i in range(26)]
    for i in range(2 * N):
        idx[ctoi(S[i % N])].append(i)
    ans = -1
    for c in T:
        if not idx[ctoi(c)]:
            return -1
        ans += idx[ctoi(c)][bisect(idx[ctoi(c)], ans % N)] - ans % N
    return ans + 1
print(solve())

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
s = input()
t = input()
n_s = len(s)
n_t = len(t)


idx = [[] for _ in range(26)]
#print(ord("a"))
#print(ord("z"))

def a_idx(a):
    idx = ord(a)
    idx -= 97
    return idx


for i in range(n_s):
    idx[a_idx(s[i])].append(i)

t_syutugenkasyo = []
for i in range(n_t):
    t_syutugenkasyo.append(idx[a_idx(t[i])])
#print(t_syutugenkasyo)

now = -1
ans = 0
for i in range(n_t):
    if len(t_syutugenkasyo[i]) == 0:
        print(-1)
        exit()
    ni = bisect_right(t_syutugenkasyo[i], now)
    if ni >= len(t_syutugenkasyo[i]):
        ans += n_s
        now = t_syutugenkasyo[i][0]
    else:
        now = t_syutugenkasyo[i][ni]
ans += now+1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
s = input()
t = input()
n_s = len(s)
n_t = len(t)


idx = [[] for _ in range(26)]
#print(ord("a"))
#print(ord("z"))

def a_idx(a):
    idx = ord(a)
    idx -= 97
    return idx


for i in range(n_s):
    idx[a_idx(s[i])].append(i)

t_syutugenkasyo = []
for i in range(n_t):
    t_syutugenkasyo.append(idx[a_idx(t[i])])
#print(t_syutugenkasyo)

now = -1
ans = 0
for i in range(n_t):
    if len(t_syutugenkasyo[i]) == 0:
        print(-1)
        exit()
    ni = bisect_right(t_syutugenkasyo[i], now)
    if ni >= len(t_syutugenkasyo[i]):
        ans += n_s
        now = -1
        ni = bisect_right(t_syutugenkasyo[i], now)
        now = t_syutugenkasyo[i][ni]
    else:
        now = t_syutugenkasyo[i][ni]
ans += now+1
print(ans)

Submission status: Accepted

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

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

len_s=len(s)
len_t=len(t)


for i in range(len_s):
    idx=ord(s[i])-97
    pos[idx].append(i)

ans=[]
tmp=-1
cnt=0
for i in range(len_t):
    idx=ord(t[i])-97
    if len(pos[idx])==0:
        print(-1)
        exit()

    if tmp<pos[idx][-1]:
        l=-1
        r = len(pos[idx]) - 1
        while l + 1 < r:
            mid = (l + r) // 2
            if pos[idx][mid] <= tmp:
                l = mid
            else:
                r=mid
        ans.append(pos[idx][r])
        tmp=pos[idx][r]
    else:
        cnt+=1
        ans.append(pos[idx][0])
        tmp=pos[idx][0]


print(cnt*len_s+ans[-1]+1)

Submission status: Accepted

Solution code:
def next(str):
    N = len(str)
    nxt = [[N] * 26 for i in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(str[i]) - ord('a')] = i
    return nxt

def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = next(S)
    ans = -1
    for c in T:
        i = ans % N
        pos = ord(c) - ord('a')
        if nxt[i + 1][pos] == M:
            return -1
        ans += nxt[i + 1][pos] - i
    return ans + 1

print(solve())

Submission status: Accepted

Solution code:
def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = [[M] * 26 for i in range(M + 1)]
    for i in range(M - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(S[i]) - ord('a')] = i
    ans = -1
    for c in T:
        i = ans % N
        pos = ord(c) - ord('a')
        if nxt[i + 1][pos] == M:
            return -1
        ans += nxt[i + 1][pos] - i
    return ans + 1

print(solve())

Submission status: Accepted

Solution code:
def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = [[M] * 26 for i in range(M + 1)]
    for i in range(M - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(S[i]) - ord('a')] = i
    ans = 0
    i = 0
    for c in T:
        pos = ord(c) - ord('a')
        if nxt[i][pos] == M:
            return -1
        ans += nxt[i][pos] - i + 1
        i = (nxt[i][pos] + 1) % N
    return ans

print(solve())