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 sys
import math
sys.setrecursionlimit(200000)
input = sys.stdin.readline

S = input().strip()
T = input().strip()
l = len(S)

m = {}
for i in range(l):
    c = S[i]
    if m.get(c) == None:
        m[c] = []
    m[c].append(i)

a = [None] * len(T)
for i in range(len(T)):
    if m.get(T[i]) == None:
        print(-1)
        exit()
    a[i] = m[T[i]]

bl = 0
before = min(a[0])
for i in range(1, len(T)):
    m = a[i]
    f = True
    while f:
        for j in range(len(m)):
            c = (bl * l) + m[j]
            if before < c:
                before = c
                f = False
                break
        if f:
            bl += 1

print(before + 1)

Submission status: Time Limit Exceeded

Solution code:
def counter(list_1,list_2,length):
    w = list_1.pop()
    count = 0
    while True:
        for x,y in list_2:
            if x == w:
                if not list_1:
                    return count * length + y
                w = list_1.pop()
        count += 1
s = input()
le_s = len(s)
t = input()
l_t = [x for x in t]
l_t.reverse()
s_t = set(l_t)
l_s = []
s_s =set()
i = 1
for y in s:
    if y in s_t:
        l_s.append((y,i))
        s_s.add(y)
    i += 1
if s_t != s_s:
    print(-1)
    exit()
print(counter(l_t,l_s,le_s))

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = input()
     
count = 0
ind = -1
if set(l).issubset(set(s)):
    for i in range(len(l)):
        ind = s.find(l[i], ind+1)
        if ind == -1:
            count += 1
            ind = s.find(l[i], ind+1)
    print(count*len(s) + ind+1)
 
else:
    print(-1)

Submission status: Time Limit Exceeded

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

wi = {}  
for n, _ in enumerate(s):
  wi[n] = {}
  for k, ws in enumerate(s):
    if not wi[n].get(ws):
      wi[n][ws] = [k-n if k-n > 0 else k-n+s_l]
    else:
      wi[n][ws].append(k-n if k-n > 0 else k-n+s_l)

ans = 0
x = 0
for b, wt in enumerate(t):
  if b == 0:
    x = s.find(wt)
    if x == -1:
      print(x)
      exit()
    else:
      ans = x + 1
  else:
    if not wi[x].get(wt):
      print(-1)
      exit()
    else:
      ans += wi[x][wt][0]
      x = (x + wi[x][wt][0]) % s_l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

s = input()
t = input()
n = len(s)
cnt = {}
s = s*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

suffix = 0
idx = 0
ten = 0
for z in t:
    if z not in s:
        print(-1)
        sys.exit()

    idx = ([m for m in cnt[z][::-1] if m>=idx]).pop(-1) + 1

    if idx>=n:
        idx -= n
        ten += 1

suffix = idx + ten * n
print(suffix)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

s = input()
t = input()
n = len(s)
cnt = {}
s = s*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

for y in t:
    if y not in s:
        print(-1)
        sys.exit()

suffix = 0
idx = 0
ten = 0
for z in t:
    idx = ([m for m in cnt[z][::-1] if m>=idx]).pop(-1) + 1

    if idx>=n:
        idx -= n
        ten += 1

suffix = idx + ten * n
print(suffix)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = input()
t = input()
n = len(s)
cnt = {}
s = s*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

for y in t:
    if y not in s:
        print(-1)
        sys.exit()

suffix = 0
idx = 0
ten = 0
for z in t:
    idx = min([m for m in cnt[z] if m>=idx]) + 1

    if idx>=n:
        idx -= n
        ten += 1

suffix = idx + ten * n
print(suffix)

Submission status: Time Limit Exceeded

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

wi = {}
for n, ws in enumerate(s):
  wi[n] = {}
  
for n, _ in enumerate(s):
  for k, ws in enumerate(s):
    if not wi[n].get(ws):
      wi[n][ws] = [k-n if k-n > 0 else k-n+s_l]
    else:
      wi[n][ws].append(k-n if k-n > 0 else k-n+s_l)

ans = 0
x = 0
for b, wt in enumerate(t):
  if b == 0:
    x = s.find(wt)
    if x == -1:
      print(x)
      exit()
    else:
      ans = x + 1
  else:
    if not wi[x].get(wt):
      print(-1)
      exit()
    else:
      ans += wi[x][wt][0]
      x = (x + wi[x][wt][0]) % s_l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
 
flg = False
for x in t:
  if not x in s:
    flg = True
  
if flg:
  print(-1)
else:
  dic = {}
  for i in range(len(s)):
    dic[s[i]] = dic.get(s[i], []) + [i]
  for i in range(len(s)):
    dic[s[i]] = dic.get(s[i], []) + [i+len(s)]

  ans = 0
  p = 0
  for i in range(len(t)):
    if not t[i] in dic:
      print(-1)
      break
    else:
      idx = [-1]+dic[t[i]]
      l, r = 0, len(idx)
      while l<=r:
        m = (l+r)//2
        if p>idx[m-1] and p<=idx[m]:
          p = idx[m]+1
          break
        elif p<idx[m-1]:
          r = m-1
        else:
          l = m+1
      if p>=len(s):
        p -= len(s)
        ans += len(s)
  ans += p
  print(ans)

Submission status: Time Limit Exceeded

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

c=0
j=-1
k=1

a=len(s)

for i in range(0,len(t)):
  while True:
    j=j+1
    c=c+1

    if j>=a:
      j=0

    if t[i:i+1]==s[j:j+1]:
      k=1
      break
    else:
      k=k+1
      if k>a+1:
        print("-1")
        exit()
print(c)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
before = -1
len_s = len(s)
ans = 0
cnt = 0
moji = [[] for _ in range(26)]
for i,S in enumerate(s):
        moji[ord(S) - 97].append(i)

for T in t:
        found = False
        if not moji[ord(T) - 97]:
                print(-1)
                exit()
        for num in moji[ord(T) - 97]:
                if num > before:
                        before = num
                        found = True
                        break
        if not found:
                cnt += 1
                before = moji[ord(T) - 97][0]
ans = cnt * len_s + before + 1
print(ans)

Submission status: Time Limit Exceeded

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

c=0
j=-1
k=1

#print(len(s))

#t
for i in range(0,len(t)):
  while True:
    j=j+1
    c=c+1

    if j>=len(s):
#      print("折り返し")
#      print(j)
      #jがお尻まで行ったら先頭に戻る
      j=0

#    print(j)
#    print(c)
    
    if t[i:i+1]==s[j:j+1]:
#      print("hit")
      #kはもう一度一文字めからカウントし直し
      k=1
      break
    else:
      #hitしなかった場合、index　カウントアップ
      k=k+1
      #一周回ってもヒットしなかったらエラー
      if k>len(s)+1:
        print("-1")
        exit()
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

count = 0
for j in range(10000000000):
    for k in range(len(s)):
        if count == len(t):
            print(k +  (j * len(s)))
            sys.exit()
            
        #print(a[k +  (j * len(s))], t[count],a, count)
        if s[k] == t[count]:
            count += 1

Submission status: Time Limit Exceeded

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

c=0
j=0
k=0

#t
for i in range(0,len(t)):
  while True:
    if t[i:i+1]==s[j:j+1]:
      j=j+1
      c=c+1
      k=c
      break
    else:
      if j==len(s):
        j=0
      else:
        if c-k==len(s):
          print("-1")
          exit()
        else:
          j=j+1
          c=c+1
print(c)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
s_l = len(s)
ss = s + s

wi = {}
for w in range(s_l):
  for n, ws in enumerate(ss[w+1:w+s_l+1]):
    if not wi.get(w):
      wi[w] = {ws:[n+1]}
    else:
      if not wi[w].get(ws):
        wi[w][ws] = [n+1]
      else:
        wi[w][ws].append(n+1)

ans = 0
x = 0
for b, wt in enumerate(t):
  if b == 0:
    x = s.find(wt)
    if x == -1:
      print(x)
      exit()
    else:
      ans = x + 1
  else:
    if not wi[x].get(wt):
      print(-1)
      exit()
    else:
      ans += wi[x][wt][0]
      x = (x + wi[x][wt][0]) % s_l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    if judge(s, t):
        makeCount(s, t)
    else:
        print("-1")

def judge(s, t):
    ans = True
    while(t != ""):
        c_t = t[0]
        t = t.replace(c_t, "")
        if c_t in s:
            s = s.replace(c_t, "")
        else:
            ans = False
            break
    return ans

def makeCount(s, t):
    count = 0
    p_t = 0
    flag = True
    s_l = len(s)
    t_l = len(t)
    while(flag):
        for i in range(s_l):
            if(p_t == t_l):
                flag = False
                break
            elif(s[i] == t[p_t]):
                p_t += 1
            count += 1
    print(count)

main()

Submission status: Time Limit Exceeded

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

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

    if not all(s.find(c) >= 0 for c in t):
        print(-1)
        exit()
    
    sa = [[] for _ in string.ascii_lowercase]
    for i,c in enumerate(s):
        sa[ord(c)-ord('a')].append(i+1)
#    print(sa)

    ls = len(s)
    ans = 1 # 条件を満たす整数
    i = 1 # s の何番目の文字から探し始めるか
    for c in t:
        a = sa[ord(c)-ord('a')]
        if len(a) == 0 or i > a[-1]:
            ans += ls-i+1
            i = 1
        for j in a:
            if j >= i:
                ans += j-i+1
                i = j+1
                break
#        print("c,a,ans,i=", c, a, ans, i)
    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    if judge(s, t):
        makeCount(s, t)
    else:
        print("-1")

def judge(s, t):
    ans = True
    t_l = len(t)
    for i in range(t_l):
        t.replace(t[i], "")
        if t[i] in s:
            s.replace(t[i], "")
        else:
            ans = False
            break
    return ans

def makeCount(s, t):
    count = 0
    p_t = 0
    flag = True
    s_l = len(s)
    t_l = len(t)
    while(flag):
        for i in range(s_l):
            if(p_t == t_l):
                flag = False
                break
            elif(s[i] == t[p_t]):
                p_t += 1
            count += 1
    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

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

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
ind_prev_each_letter = [0 for _ in range(26)]
hoge = [0 for _ in range(26)]
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = copy.deepcopy(hoge)
        loop += 1

    for i in range(ind_prev_each_letter[ord(x) - 97], len(letter)):
        y = letter[i]
        if y > ind_prev:
            ind_prev = y
            ind_prev_each_letter[ord(x) - 97] += 1
            break

if flag:
    print(loop * len(s) + ind_prev + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
ind_prev_each_letter = [0 for _ in range(26)]
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = [0 for _ in range(26)]
        loop += 1

    for i in range(ind_prev_each_letter[ord(x) - 97], len(letter)):
        y = letter[i]
        if y > ind_prev:
            ind_prev = y
            ind_prev_each_letter[ord(x) - 97] += 1
            break

if flag:
    print(loop * len(s) + ind_prev + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        loop += 1

    for y in letter:
        if y > ind_prev:
            ind_prev = y
            break

if flag:
    print(loop * len(s) + ind_prev + 1)

Submission status: Time Limit Exceeded

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

s = list(s+s)
ans=0
start = 0
for ch in t:
    if ch in s:
        tmp = s[start:start+n]
        ans += tmp.index(ch)+1
        start = (start+tmp.index(ch)+1)%n
    else:
        print(-1)
        exit(0)

print(ans)

Submission status: Time Limit Exceeded

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

s = str(input())
t = str(input())
s_modified = ""


for _ in range(10):
	s_modified += s[:-1]

# print(s_modified)	

T = len(t)
p = 0 


for  i in range(T-1):
	if not t[i] in s :
		print(-1)
		break
	else:
		if p > len(s_modified) - len(s):
			# for _ in range(100):
			s_modified += s[:-1]
		
		p += s_modified[p:].index(t[i]) + 1
		
		if i == T-2:
			print(p)

# print("答えは{}".format(p))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect

S = list(input())
T = list(input())

pos_S = {}
for i, s in enumerate(S):
  if s in pos_S:
    pos_S[s].append(i)
  else:
    pos_S[s] = deque([i])
x = 0
start = 0
for t in T:
  if t in pos_S:
    poss = pos_S[t]
    pos = bisect.bisect_left(poss, start)
    if pos >= len(poss):
      x += 1
      start = poss[0]+1
    else:
      start = poss[pos]+1
  else:
    x = -1
    break
if x == -1:
  print(-1)
else:
  print(x*len(S)+start)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
LS = len(S)
LT = len(T)

dp = [0] * (LT+1)
dp[0] = -1
valid = True

for i in range(1,LT+1):
    t = T[i-1]
    p = (dp[i-1] + 1) % LS
    f = False  # find or not
    for j in range(p, LS):
        if S[j] == t:
            dp[i] = dp[i-1] + j - p + 1
            f = True
            break
    if f:
        continue
    for j in range(p):
        if S[j] == t:
            dp[i] = dp[i-1] + (LS - p) + j + 1
            f = True
            break
    if f:
        continue
    valid = False
    break
    
print(dp[-1] + 1 if valid else -1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        countMakeTbyS(s, t)
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    for i in range(len(t)):
        t.replace(t[i], "")
        if t[i] in s:
            s.replace(t[i], "")
        else:
            ans = False
            break
    return ans

def countMakeTbyS(s, t):
    count = 0
    p_t = 0
    flag = True
    loop = [0]
    for i in loop:
        if flag: loop.append(i+1)
        for i in range(len(s)):
            if(p_t == len(t)):
                flag = False
                break
            elif(s[i] == t[p_t]):
                p_t += 1
            count += 1
    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        countMakeTbyS(s, t)
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    for i in range(len(t)):
        t.replace(t[i], "")
        if t[i] in s:
            s.replace(t[i], "")
        else:
            ans = False
            break
    return ans

def countMakeTbyS(s, t):
    count = 0
    p_t = 0
    flag = True
    """
    while(flag):
        for i in range(len(s)):
            if(p_t == len(t)):
                flag = False
                break
            elif(s[i] == t[p_t]):
                p_t += 1
            count += 1
    """
    loop = [0]
    for i in loop:
        if flag: loop.append(i+1)
        for i in range(len(s)):
            if(p_t == len(t)):
                flag = False
                break
            elif(s[i] == t[p_t]):
                p_t += 1
            count += 1
    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        countMakeTbyS(s, t)
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    for i in range(len(t)):
        t.replace(t[i], "")
        if t[i] in s:
            s.replace(t[i], "")
        else:
            ans = False
            break
    return ans

def countMakeTbyS(s, t):
    count = 0
    p_t = 0
    flag = True
    while(flag):
        for i in range(len(s)):
            if(p_t == len(t)):
                flag = False
                break
            elif(s[i] == t[p_t]):
                p_t += 1
            count += 1
    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        print(countMakeTbyS(s, t))
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    #mem = set()
    for i in range(len(t)):
        #mem.add(t[i])
        t.replace(t[i], "")
        if t[i] in s:
            s.replace(t[i], "")
        else:
            ans = False
            break
    return ans

def countMakeTbyS(s, t):
    count = 0
    p_t = 0
    try:
        while(True):
            for i in range(len(s)):
                x = t[p_t]
                y = s[i]
                if x == y:
                    p_t += 1
                count += 1
    except:
        return count


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        print(countMakeTbyS(s, t))
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    mem = set()
    for i in range(len(t)):
        mem.add(t[i])
        t.replace(t[i], "")
        if t[i] in s:
            s.replace(t[i], "")
        else:
            ans = False
            break
    return ans

def countMakeTbyS(s, t):
    count = 0
    p_t = 0
    try:
        while(True):
            for i in range(len(s)):
                x = t[p_t]
                y = s[i]
                if x == y:
                    p_t += 1
                count += 1
    except:
        return count


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def main():
    s = input()
    t = input()
    if judgeMate(s, t):
        print(countMakeTbyS(s, t))
    else:
        print("-1")

def judgeMate(s, t):
    ans = True
    mem = set()
    for i in range(len(t)):
        """
        if t[i] in s:
            continue
        else:
            ans = False
            break
        """
        if t[i] not in mem:
            mem.add(t[i])
            t.replace(t[i], "")
            if t[i] in s:
                s.replace(t[i], "")
            else:
                ans = False
                break
    return ans

def countMakeTbyS(s, t):
    count = 0
    p_t = 0
    try:
        while(True):
            for i in range(len(s)):
                x = t[p_t]
                y = s[i]
                if x == y:
                    p_t += 1
                count += 1
    except:
        return count


main()

Submission status: Time Limit Exceeded

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

Submission status: Time Limit Exceeded

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_):
    if  len(list_) == 1:
            return list_[0]
    else:
            mid = len(list_)//2
            if list_[mid-1]>mark_:
                return search(list_[:mid],mark_)
            else:
                return search(list_[mid:],mark_)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

Submission status: Time Limit Exceeded

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

Submission status: Time Limit Exceeded

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_):
    if  len(list_) == 1:
            return list_[0]
    else:
            mid = len(list_)//2
            if list_[mid-1]>mark_:
                return search(list_[:mid],mark_)
            else:
                return search(list_[mid:],mark_)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

Submission status: Time Limit Exceeded

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

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        for j in range(len(sdict[target])):
            if sdict[target][j]>mark:
                mark = sdict[target][j]
                break
            if j == len(sdict[target])-1:
                mark = sdict[target][0]
                ans += len(s)
                break
        
if ans != -1:
    ans += mark
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline()[:-1]
from collections import defaultdict
s =input()
lenth=len(s)
ss=s*2
t =input()
place=defaultdict(list)

for k,l in enumerate(s):
	place[l].append(k+1)
	place[l].append(k+1+lenth)

now=0
ans=0
for i in t:
	if not place[i]:
		print(-1)
		exit()
	mt=min((j for j in place[i] if j>now))
	if mt>lenth:
		mt-=lenth
		ans+=lenth
	now=mt
print(ans+now)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline()[:-1]
from collections import defaultdict
s =input()
lenth=len(s)
ss=s*2
t =input()
place=defaultdict(list)

for k,l in enumerate(s):
	for word in range(97, 97+26):
		word=chr(word)
		if word==l:
			place[word].append(k+1)
			place[word].append(k+1+lenth)

now=0
ans=0
for i in t:
	if not place[i]:
		print(-1)
		exit()
	mt=min((j for j in place[i] if j>now))
	if mt>lenth:
		mt-=lenth
		ans+=lenth
	now=mt
print(ans+now)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
t = list(input())
work = s[:]
cnt = 0
ans = 0
flag = False
while cnt < len(t):
    #print("t[count] ",t[cnt])
    #print("work ",work)
    try:
        index = work.index(t[cnt])
        #print("index" , index)
        ans += index + 1
        cnt += 1
        work = work[index + 1:]
        #print("work",work)
        flag = False
    except ValueError:
        if flag:
            print(-1)
            exit(0)
        #print("len(work)",len(work))
        #print("not find")
        ans += len(work)
        work = s[:]
        #print("work",work)
        flag = True
    #print("ans ",ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s,t = [input() for i in range(2)]

cflg = 1
if len(set(t))>len(set(s)):
    cflg = 0
cnt = 0
stop =len(s)*len(t)
while cflg == 1 and cnt<=stop:
    cflg = 0
    for i in range(len(s)):
        cnt+=1
        if s[i] == t[0]:
            cflg = 1
            t = t[1:]
            if len(t) == 0:
                cflg = 0
                break

if len(t) !=0:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s,t = [input() for i in range(2)]

cflg = 1
if len(set(t))>len(set(s)):
    cflg = 0
cnt = 0
while cflg == 1:
    cflg = 0
    for i in range(len(s)):
        cnt+=1
        if s[i] == t[0]:
            cflg = 1
            t = t[1:]
            if len(t) == 0:
                cflg = 0
                break

if len(t) !=0:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s,t = [input() for i in range(2)]

cflg = 1
cnt = 0
while cflg == 1:
    cflg = 0
    for i in range(len(s)):
        cnt+=1
        if s[i] == t[0]:
            cflg = 1
            t = t[1:]
            if len(t) == 0:
                cflg = 0
                break

if len(t) !=0:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
ss = [[] for i in range(0,26)]
s = input()
sx = len(s)
t = input()
ff = True
for i in t:
    if i not in s:
        ff = False
        break
if ff:
    for i in range(0,len(s)):
        ss[ord(s[i])-97].append(i)
    curr_len = ss[ord(t[0])-97][0]
    curr_ind = ss[ord(t[0])-97][0]
    for i in range(1,len(t)):
        x = t[i]
        f = False
        for i in range(0,len(ss[ord(x)-97])):
            if ss[ord(x)-97][i] > curr_ind:
                f = True
                curr_len += ss[ord(x)-97][i]-curr_ind
                curr_ind = ss[ord(x)-97][i]
                break
        if not f:
            curr_len += (sx - curr_ind)+ss[ord(x)-97][0]
            curr_ind = ss[ord(x)-97][0]
    print(curr_len+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

# 辞書を作る
dictionary = {}

tt = t[:]
ss = dict(zip(list(range(len(s * 2))), s * 2))

while len(tt):
    _t = tt.pop(0)
    if _t in dictionary:
        continue
    indexes = [k for k, v in ss.items() if v == _t]
    if not len(indexes) > 0:
        print(-1)
        exit(0)
    for i in indexes:
        del ss[i]
    dictionary[_t] = indexes

result = 0
before = 0
sLen = len(s)
while len(t) > 0:
    _t = t.pop(0)
    next = dictionary[_t][bisect.bisect_left(dictionary[_t], before)] + 1
    result += next - before
    before = next
    if next >= sLen:
        before -= sLen

print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

# 辞書を作る
dictionary = {}

tt = t[:]
ss = s * 2

i = 0
while len(ss):
    _s = ss.pop(0)
    if _s not in dictionary:
        dictionary[_s] = [i]
    else:
        dictionary[_s].append(i)
    i += 1

result = 0
before = 0
sLen = len(s)
while len(t) > 0:
    _t = t.pop(0)
    if _t not in dictionary:
        print(-1)
        exit(0)
    _next = dictionary[_t][bisect.bisect_left(dictionary[_t], before)] + 1
    result += _next - before
    before = _next
    if _next >= sLen:
        before -= sLen

print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

# 辞書を作る
dictionary = {}

tt = t[:]
ss = s * 2

while len(tt):
    _t = tt.pop(0)
    if _t not in ss:
        print(-1)
        exit(0)
    indexes = [i for i, x in enumerate(ss) if x == _t]
    if _t not in dictionary:
        dictionary[_t] = indexes
    else:
        dictionary[_t].extend(indexes)

result = 0
before = 0
sLen = len(s)
while len(t) > 0:
    _t = t.pop(0)
    next = dictionary[_t][bisect.bisect_left(dictionary[_t], before)] + 1
    result += next - before
    before = next
    if next >= sLen:
        before -= sLen

print(result)