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:
abc = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
s = input()
x = [[float("inf") for i in range(26)] for j in range(len(s))]
for k in range(2):
    for i in range(len(s)-1,-1,-1):
        if i == 0:
            ib = len(s)-1
        else:
            ib = i-1
        for j in range(26):
            if j == ord(s[i])-97:
                x[ib][j] = i
            else:
                x[ib][j] = x[i][j]
t = input()
i = len(s)-1
count = 0
for j in range(len(t)):
    nxt = x[i][ord(t[j])-97]
    if nxt == float("inf"):
        print(-1)
        exit()
    elif nxt <= i:
        count += 1
        i = nxt
    else:
        i = nxt
print(len(s)*(count-1)+i+1)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = input()
t = input()
if not set(t).issubset(set(s)):
    print(-1)
    sys.exit(0)
count = 0
temp_s = s
for i,t_ in enumerate(t):
    temp_s += s if len(temp_s)<len(s) else ''
    next_idx = temp_s.index(t_)+1
    temp_s = temp_s[next_idx:]
    count += next_idx
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = input()
t = input()
if not set(t).issubset(set(s)):
    print(-1)
    sys.exit(0)
count = 0
temp_s = s
for i,t_ in enumerate(t):
    temp_s += s
    next_idx = temp_s.index(t_)+1
    temp_s = temp_s[next_idx:]
    count += next_idx
print(count)

Submission status: Time Limit Exceeded

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

s_list=list(s)
t_list=list(t)

last_index=0
add_index=0

if not set(t).issubset(set(s)):
    print(-1)
else:
    while(len(t_list)>0):
        if s_list[last_index:].count(t_list[0])>0:
            last_index=s_list[last_index:].index(t_list[0])+1+len(s_list[:last_index])
            t_list.pop(0)
        else:
            s_list+=list(s)
            add_index+=len(s)
    print(last_index)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls_s = list(s)
ls_t = list(t)
set_s = set(ls_s)
set_t = set(list(t))
if not set_t <= set_s:
    print(-1)
    exit()
tag_t = [-1]*len(t)
cnt_t = 0 #index of t
cnt = 0 #count i
tag = 0 #index of s
n = len(s)-1
nt = len(t)-1
for i in range(nt+1):
    while True:
        if ls_t[i] == ls_s[tag]:
            tag_t[i] = tag +1
            tag += 1
            if tag > n:
                tag = 0
            break
        tag += 1
        if tag > n:
            tag = 0
now = tag_t[0]
cnt+= now
for i in range(1,nt+1):
    pre = now
    now = tag_t[i]
    if now > pre:
        cnt +=  now - pre
    else:
        cnt += n+1 - pre + now
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
i = -1
r = 0
c = 0
n = len(s)

s = np.array(list(s))

d = dict()
for x in t:
    if x not in d:
        d[x] = np.where(s == x)[0]
        if len(d[x]) == 0:
            r = -1
            break
    
    y = d[x]>i
    if not any(y):
        i = d[x][0]
        c += 1
    else:
        y = np.where(y)[0][0]
        i = d[x][y]
        
if r != -1:
    r = c * n + i + 1
print(r)

Submission status: Time Limit Exceeded

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

len_s = len(s)
dp = [[-1 for _ in range(len_s)] for _ in range(26)]
# dp[i][j] = いまsのj文字目にいる。次に探しているのはアルファベットのi文字目であるとき、次までの必要文字数。
# print(len(dp))
# print(len(dp[0]))

for idx in range(len_s):

	ch = s[idx]
	i = ord(ch)-ord("a")
#	for j in range(len_s):
	if dp[i][0] == -1:
		dp[i] = [idx] * len_s
	else:
		temp = dp[i][idx]
		dp[i][temp+1:idx] = [idx] * (idx - temp + 1)

ans = 0
j = 0
first = True
for ch in t:

	i = ord(ch)-ord("a")

	if dp[i][j] < 0:
		print(-1)
		exit()

	distance = dp[i][j] - j
	if (not first )and distance <= 0 :
		distance += len_s
	ans += distance
	j = dp[i][j]

	first = False

print(ans + 1)

Submission status: Time Limit Exceeded

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

s=s+s

ss=list(s)
tt=list(t)
l=len(ss)    
count=0
y=-1
ind={}
flag1=0
for x in tt:
    ind[x]=[i for i, xx in enumerate(ss) if xx == x]
    if ind[x]==[]:
        flag1=1

if flag1==0:    
    for x in tt:
        for z in ind[x]:
            if z>y:
                y=z
                flag=0
                break
            flag=1
        if flag==1:
            count+=1
            y=ind[x][0]
    #         print(count,z,y)
    ans=count*l+z+1
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def SI(): return sys.stdin.readline().strip()

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

    import collections
    didx = collections.defaultdict(int)
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)


    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def SI(): return sys.stdin.readline().strip()

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

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

    import collections
    didx = collections.defaultdict(int)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

Submission status: Time Limit Exceeded

Solution code:
import copy

S = input()
revS = copy.copy(S)
T = input()
cnt = 0
add_cnt = 0
num = 0

for i,t in enumerate(T):
  if t in revS:
    revS = revS[revS.index(t)+1:]
    T = T[1:]
    cnt = (len(S)-len(revS))
  else:
    if t in S:
      add_cnt += 1
      revS = S[S.index(t)+1:]
      T = T[1:]
      cnt = (len(S)-len(revS))
    else:
      num = -1
      break
if num==-1:
  print(-1)
else:
  print(add_cnt*len(S)+cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
i = -1
r = 0
n = len(s)

s = np.array(list(s))

d = dict()
for x in t:
    if x not in d:
        d[x] = np.where(s == x)[0]
        if len(d[x]) == 0:
            r = -1
            break
    
    y = d[x]>i
    if not any(y):
        r += n - i
        i = d[x][0]
        r += i
    else:
        y = np.where(y)[0][0]
        j = d[x][y]
        r += j - i
        i = j

print(r)

Submission status: Time Limit Exceeded

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

text = list(set(List_t) - set(List_s))
if len(text)!=0:
    print(-1)
    exit()

ans=0
j=0
for i in List_t:
    for _ in range(len(List_s)):
        if j>=len(List_s):
            j=0
        ans+=1
        if i==List_s[j]:
            j+=1
            break
        j+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
i = -1
r = 0
n = len(s)

d = dict()
for x in t:
    if x not in d:
        d[x] = np.where(np.array(list(s)) == x)[0]
        if len(d[x]) == 0:
            r = -1
            break
    
    y = d[x]>i
    if not any(y):
        r += n - i
        i = d[x][0]
        r += i
    else:
        y = np.where(y)[0][0]
        j = d[x][y]
        r += j - i
        i = j

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = input().rstrip("\n")
t = input().rstrip("\n")
dic = {"a":[],"b":[],"c":[],"d":[],"e":[],"f":[],"g":[],"h":[],"i":[],"j":[],"k":[],"l":[],"m":[],"n":[],"o":[],"p":[],"q":[],"r":[],"s":[],"t":[],"u":[],"v":[],"w":[],"x":[],"y":[],"z":[]}
for i,c in enumerate(s):
    dic[c] += [i]
else:
    l = i+1
#print(dic)
cnt = 0
ind = -1
ans = 0
for c in t:
    d = dic[c]
    if d:
        if d[-1] > ind:
    #    print("c=",c,"d=",d)
            for i in d: #iは各文字のindex 昇順
        #        print("i=",i)
                if ind < i: #もし現在位置<iなら
                    ind = i
        #            print("found, ind=",i)
                    break
        else:
    #        print("not found")
            cnt += 1
            ind = d[0]
    else:
        ans = -1
        break

print(cnt*l+ind+1 if ans > -1 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
s=list(input())
t=list(input())
a=[[] for _ in range(len(t))]
d=[]

for i in range(len(t)):
  for k in range(len(d)):
    if t[i]==d[k][1]:
      a[i]=d[k][0]
      break

  if a[i]==[]:
    for j in range(len(s)):
      if t[i]==s[j]:
        a[i].append(j)
        if (a[i],t[i]) not in d:
          d.append((a[i],t[i]))
      if j==len(s)-1 and a[i]==[]:
        print('-1')
        sys.exit()

ans=0
cur=0
for i in range(len(t)-1):
  for j in range(len(a[i+1])):
    if a[i][cur]<a[i+1][j]:
      cur=j
      break
    if j==len(a[i+1])-1:
      ans+=len(s)
      cur=0
print(ans+1+a[-1][cur])

Submission status: Time Limit Exceeded

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


s = input().splitlines()[0]
t = input()


Slen = len(s)
Index = -1
Loop = 0
LUT = [[] for i in range(26)]
for i, c in enumerate(s):
    v = ord(c) - ord('a')
    LUT[v].append(i)

NotFound = False
for c in t:
    v = ord(c) - ord('a')
    if len(LUT[v]) == 0:
        NotFound = True
        break
    m = -1
    for l in LUT[v]:
        if l > Index:
            m = l
            break
    if m < 0:
        Index = LUT[v][0]
        Loop += 1
    else:
        Index = m

if NotFound:
    print(-1)
else:
    print(Loop*Slen+Index+1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

s = input()
t = input()

s_dict = {}
for i, si in enumerate(s):
    s_dict[si] = [i] if si not in s_dict else s_dict[si] + [i]

# print(s_dict)

s_len = len(s)
counter = 0
fail = False
memo = {}
for ti in t:
    if ti not in s_dict:
        fail = True
        break
    # counter in s
    c_in_s = counter % s_len
    c = 0
    if (ti, c_in_s) not in memo:
        c = bisect.bisect_left(s_dict[ti], c_in_s)
        memo[(ti, c_in_s)] = c
    else:
        c = memo[(ti, c_in_s)]
    if c == len(s_dict[ti]):
        counter += s_len - c_in_s
        counter += s_dict[ti][0]
        counter += 1
    else:
        counter += s_dict[ti][c] - c_in_s
        counter += 1

print(counter if not fail else '-1')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
i = -1
r = 0
n = len(s)

d = dict()
for x in t:
    if x not in d:
        d[x] = np.where(np.array(list(s)) == x)[0]
        if len(d[x]) == 0:
            r = -1
            break
    
    y = d[x]>i
    if not any(y):
        r += n - i
        i = d[x][0]
        r += i
    else:
        y = np.where(y)[0][0]
        j = d[x][y]
        r += j - i
        i = j

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
def SI(): return sys.stdin.readline().strip()

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

    d = {}
    for i, c in enumerate(s):
        if c not in d.keys():
            d[c] = [i]
        else:
            d[c].append(i)

    import collections
    didx = collections.defaultdict(int)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    s = input()
    t = input()
    ans = 0
    for c in t:
        index = s.find(c)
        if index == -1:
            print(-1)
            return
        ans += index+1
        s = s[index+1:] + s[:index+1]
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = [0] * (len(t)+1)
for i in range(1,len(t)+1):
    if t[i-1] in s:
        dp[i] = dp[i-1] + (s.index(t[i-1]) + 1)
        s = s[s.index(t[i-1])+1:] + s[:s.index(t[i-1])+1]
    else:
        print(-1)
        exit()
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    s = input()[:-1]
    t = input()[:-1]
#    S = "abcdefghijklmnopqrstuvwxyz"
    A = [[] for k in range(26)]
    for k in range(len(s)):
        A[ord(s[k])-97] += [k+1]
    ans = 0
    now = 0
    for k in range(len(t)):
        a = ord(t[k]) - 97
        if len(A[a]) == 0:
            print(-1)
            exit(0)
        if A[a][-1] <= now:
            ans += len(s)
            now = A[a][0]
        else:
            for l in range(len(A[a])):
    #            print(A[S.index(t[k])][l]>now)
                if A[a][l] > now:
                    now = A[a][l]
                    break
    print(ans+now)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)
a = [-100]
ans = 0
ng_count = 0
s_raw = s
d = []
for i in range(len_t):
    b = s.find(t[i])
    # print(b)
    if b == -1:
        e = s_raw.find(t[i])
        if e!=-1:
            d.append(e)
        else:
            print(-1)
            exit()
    else:
        if b!=len_t:
            s = s[:b] + "?" + s[b+1:]
        else:
            s = s[:b] + "?"
        # print(t)
        d.append(b)
        # print(d)

# print(d)

if len(d) == 1:
    print(d[0]+1)
    exit()
else:
    for i in range(1,len_t):
        if d[i-1] < d[i]:
            ans = ng_count*len_s + d[i]
        else:
            ng_count += 1
            ans = ng_count*len_s + d[i]

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def SI(): return sys.stdin.readline().strip()

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

    d = {}
    for i, c in enumerate(s):
        if c not in d.keys():
            d[c] = [i]
        else:
            d[c].append(i)

    import collections
    didx = collections.defaultdict(int)

    for c in t:
        if c not in d.keys():
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
s_length = len(s)
t_length = len(t)

def char2int(char):
    return ord(char) - 97

def search_index(t_atom, last_index, d):
    if d[char2int(t_atom)] == []:
        return -1

    for i in d[char2int(t_atom)]:
        if last_index < i:
            return i

    return d[char2int(t_atom)][0]

def solve():
    last_index = -1
    t_index = []
    loop_cost = 1

    d = [[] for _ in range(26)]
    for i in range(s_length):
        char = s[i]
        d[char2int(char)].append(i)

    for i in range(t_length):
        t_atom = t[i]
        t_atom_index = search_index(t_atom, last_index, d)
        if t_atom_index == -1:
            return -1
        else:
            t_index.append(t_atom_index)
            last_index = t_atom_index

    remainder_cost = t_index[-1] + 1

    for i in range(1, t_length):
        if t_index[i - 1] >= t_index[i]:
            loop_cost += 1

    return s_length * (loop_cost - 1) + remainder_cost

print(solve())

Submission status: Time Limit Exceeded

Solution code:
def b_search(a,tgt):
    left = 0
    right = len(a) - 1

    while abs(right - left):
        mid = (left + right) // 2
        if a[mid] > tgt:
            right = mid
        else:
            left = mid
    return a[right]

def main():
    s = input()
    t = input()
    s_set = set(list(s))
    s_dict = {}
    s_len = len(s)
    t_list = list(t)
    t_set = set(t_list)
    c = 0
    ans = []
    ans_append = ans.append
    for i in s_set:
        s_dict[i] = []
    for i in range(s_len):
        s_dict[s[i]].append(i)
    if len(t_set) == len(t_set & s_set):
        for i in t_list:
            idxs = s_dict[i]
            if idxs[-1] <= c:
                c = idxs[0]
                ans_append(c)
            else:
                c = b_search(idxs,c)
                ans_append(c)
        count = 0
        for i in range(len(ans)-1):
            if ans[i] >= ans[i+1]:
                count += 1
        print(s_len*count + ans[-1] + 1)
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    T = str(input().strip())

    if not set(T) <= set(S):
        return -1

    n = len(S)
    d = defaultdict(list)
    for i, s in enumerate(S, start=1):
        d[s].append(i)

    cnt = 0
    pos = 0
    for t in T:
        if pos >= max(d[t]):
            cnt += 1
            pos = d[t][0]
        else:
            left = 0
            right = len(d[t])
            while left < right:
                mid = (left + right) // 2
                np = d[t][mid]
                if np <= pos:
                    left = mid + 1
                else:
                    right = mid
            pos = d[t][left]

    return n * cnt + pos


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

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

    d = {}
    for i, c in enumerate(s):
        if c not in d.keys():
            d[c] = [i]
        else:
            d[c].append(i)

    import collections
    didx = collections.defaultdict(int)

    for c in t:
        if c not in d.keys():
            print(-1)
            return

    dprint(d)
    dprint(didx)

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

        dprint(c, i_loop, pos, currentidx)
        dprint(didx)

    print(len(s)*i_loop + currentidx + 1)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
i = -1
r = 0
n = len(s)

d = dict()
for x in t:
    if x not in d:
        d[x] = np.where(np.array(list(s)) == x)[0]
        if len(d[x]) == 0:
            r = -1
            break
    
    y = np.where(d[x]>i)[0]
    if len(y) == 0:
        r += n - i
        i = d[x][0]
        r += i
    else:
        j = d[x][y[0]]
        r += j - i
        i = j

print(r)

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
t=list(input())
ls=len(s)
cnt=10**100
cnt1=ls
flg=0
ss=s
for ti in t:
  if cnt<0:
    print(-1)
    flg=1
    break
  if ti in set(ss):
    if len(ss[ss.index(ti)+1:])<ls:
      ss = ss[ss.index(ti)+1:]+s
      cnt-=1
      cnt1+=ls
    else:
      ss = ss[ss.index(ti)+1:]
  else:
    print(-1)
    flg=1
    break
if flg == 0:
  print(cnt1-len(ss))

Submission status: Time Limit Exceeded

Solution code:
import sys

S = input()
T = input()

limit = len(S) * pow(10, 100)

count = 0

t_indexs = []

is_contain = True
for t in T:
    current_index = [i + 1 for i, x in enumerate(S) if x == t]
    if len(current_index) == 0:
        is_contain = False
        break

    t_indexs.append(current_index)

if not is_contain:
    print(-1)
    sys.exit()

is_limit = False


ans = 0
previous_count = 0
for t_index in t_indexs:
    # preよりうえで最小
    is_in_current = False
    add_index = -1
    for t in t_index:
        if previous_count < t:
            add_index = t
            is_in_current = True
            break
    if is_in_current:
        ans += (add_index - previous_count) 
        previous_count = add_index
    else:
        ans += t_index[0] + len(S) - previous_count
        previous_count = t_index[0]

    if ans > limit:
        is_limit = True
        break

if is_limit:
    print(-1)
    sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
s = input()
t = input()
for c in set(t):
  if s.find(c) == -1:
    print(-1)
    sys.exit()
p = 0
slen = len(s)
for i in range(1, 10 ** 5 + 1):
  for j in range(slen):
    if s[j] == t[p]:
      p += 1
      if p == len(t):
        print((i - 1) * slen + j + 1)
        sys.exit()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict
    import sys
    
    s = input()
    t = input()
    ds = defaultdict(int)
    di = {}

    for i in range(len(s)):
        di[i] = defaultdict(int)
    
    for a in s:
        ds[a] = 1
        
    flag = 0
    for b in t:
        if ds[b] == 0:
            flag = 1
    if flag == 1:
        print(-1)
        sys.exit()

    s2 = s[::-1]
    for i in range(2*len(s)):
        for j in di[len(s) - (i-1)%len(s)-1]:
            di[len(s) - i%len(s)-1][j] = di[len(s) - (i-1)%len(s)-1][j] + 1
        di[len(s) - i%len(s) - 1][s2[(i-1)%len(s)]] = 1
    tmp = t[0]

    for k in range(len(s)):
        if tmp == s[k]:
            answer = k+1
            break
    for k in range(len(t)-1):
        l = k+1
        answer += di[(answer-1)%len(s)][t[l]]
        tmp = t[l]
    print(answer)
      

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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:
  ta=[deque([]) for i in range(26)]
  sa=[deque([]) for i in range(26)]
  for i in range(l):
    sa[ord(s[i])-ord('a')].append(i+1) 
  last=0
  for i in t:
    for j in sa[ord(i)-ord('a')]:
      if j > last:
        ctr+=j-last
        last=j
        break
    else:
      ctr+=l-last+sa[ord(i)-ord('a')][0]
      last=sa[ord(i)-ord('a')][0]
  print(ctr)

Submission status: Time Limit Exceeded

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

len_s = len(s)
dp = [[-1 for _ in range(len_s)] for _ in range(26)]
# dp[i][j] = いまsのj文字目にいる。次に探しているのはアルファベットのi文字目であるとき、次までの必要文字数。
# print(len(dp))
# print(len(dp[0]))

for idx in range(len_s):

	ch = s[idx]
	i = ord(ch)-ord("a")
	for j in range(len_s):
		if dp[i][j] == -1 or (dp[i][j] < j < idx):
			dp[i][j] = idx

ans = 0
j = 0
first = True
for ch in t:

	i = ord(ch)-ord("a")

	if dp[i][j] < 0:
		print(-1)
		exit()

	distance = dp[i][j] - j
	if (not first )and distance <= 0 :
		distance += len_s
	ans += distance
	j = dp[i][j]

	first = False

print(ans + 1)

Submission status: Time Limit Exceeded

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

ls = len(s)
lt = len(t)
st = set(t)
flg = 0

for i in st:
  if s.count(i)==0:
    flg = -1
    print(flg)
    exit()

i = 0
j = 0

while i<lt:
  if j==len(s):
    s+=s
  if t[i]==s[j]:
    i+=1
  j+=1
  
print(j)

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
lt=len(t)
ls=len(s)
while i<lt:
  
  if t[i]==s[cnt%ls]:
    i+=1
  
  cnt+=1
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
#s="contest"
#t="sentence"
#解の存在確認
s_set = set(s)
t_set = set(t)
i = 0
if not t_set <= s_set:
    print(-1)
else:
    search_str = s
    #for c in t:
    num_s = len(search_str)
    num = len(t)
    j = 0
    idx = 0
    while j < num:
        c = t[j]
        prev = -1
        while True:
            idx = search_str.find(c, prev + 1)
            if idx == -1:#見つからない
                i += num_s - prev - 1
                break
            else:
                #idx += 1
                i += idx - prev
                j += 1
                if j >= num:
                    break
                c = t[j]
            #idx = prev + idx
            prev = idx
    # num = len(t)
    # j = 0
    # while j < num:
    #     c = t[j]
    #     for d in s:
    #         i += 1
    #         if c == d:
    #             j += 1
    #             if j >= num:
    #                 break
    #             c = t[j]
    print(i)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
#print(s,t)
s_prime = s
count = 0
l_t = len(t)
l_s = len(s)
s_set = set(s)
t_set = set(t)
intersection = s_set & t_set 

for i in range(l_t):
    if intersection != t_set:
        count = -1
        #print(count)
        break
    while True:
        #print("s_prime",s_prime)
        if t[i] in s_prime:
            #print(s_prime.index(t[i])+1)
            count += s_prime.index(t[i])+1
            s_prime = s_prime[s_prime.index(t[i])+1:]
            break
        else:
            s_prime += s
if  1<= count <= 10**100 * l_s:
    print(count)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def b_search(a,tgt):
    left = 0
    right = len(a) - 1

    while abs(right - left):
        mid = (left + right) // 2
        if a[mid] > tgt:
            right = mid
        else:
            left = mid
    return a[right]

def main():
    import sys
    sys.setrecursionlimit(4100000)
    input = sys.stdin.readline
    s = input().strip()
    t = input().strip()
    s_set = set(list(s))
    s_dict = {}
    s_len = len(s)
    t_list = list(t)
    t_set = set(t_list)
    c = 0
    ans = []
    ans_append = ans.append
    for i in s_set:
        s_dict[i] = []
    for i in range(s_len):
        s_dict[s[i]].append(i)
    if len(t_set) == len(t_set & s_set):
        for i in t_list:
            idxs = s_dict[i]
            if idxs[-1] <= c:
                c = idxs[0]
                ans_append(c)
            else:
                c = b_search(idxs,c)
                ans_append(c)
        count = 0
        for i in range(len(ans)-1):
            if ans[i] >= ans[i+1]:
                count += 1
        print(s_len*count + ans[-1] + 1)
    else:
        print(-1)
    
if __name__ == '__main__':
    main()