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:
from collections import defaultdict
c = defaultdict(list)
d = defaultdict(list)
s = input()
t = input()
n = len(s)
for i in range(n):
    c[s[i]].append(i + 1)
cnt1 = 0
cnt2 = 0
judge = True
for i in range(len(t)):
    if not c[t[i]]:
        judge = False
        break
    if cnt2 >= c[t[i]][-1]:
        cnt2 = c[t[i]][0]
        cnt1 += 1
        continue
    l = 0
    r = len(c[t[i]])
    for j in range(len(c[t[i]])):
        ce = (l + r) // 2
        if cnt2 >= c[t[i]][ce]:
            l = ce + 1
        else:
            r = ce
        if l == r:
            cnt2 = c[t[i]][l]
if judge:
    print(n * cnt1 + cnt2)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
c = defaultdict(list)
s = input()
n = len(s)
for i, ch in enumerate(s):
    c[ch].append(i + 1)
cnt1 = 0
cnt2 = 0
judge = True
for ch in input():
    if not c[ch]:
        judge = False
        break
    if cnt2 >= c[ch][-1]:
        cnt2 = c[ch][0]
        cnt1 += 1
        continue
    l = 0
    r = len(c[ch])
    for i in range(len(c[ch])):
        ce = (l + r) // 2
        if cnt2 >= c[ch][ce]:
            l = ce + 1
        else:
            r = ce
        if l == r:
            cnt2 = c[ch][l]
if judge:
    print(n * cnt1 + cnt2)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
c = defaultdict(list)
s = input()
n = len(s)
for i, ch in enumerate(s):
    c[ch].append(i + 1)
cnt1 = 0
cnt2 = 0
judge = True
for ch in input():
    if not c[ch]:
        judge = False
        break
    for i in range(len(c[ch])):
        if cnt2 < c[ch][i]:
            cnt2 = c[ch][i]
            break
        if i == len(c[ch]) - 1:
            cnt1 += 1
            cnt2 = c[ch][0]
if judge:
    print(n * cnt1 + cnt2)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
len_s = len(s)
a = ord('a')
dictionary = {chr(a + i): [] for i in range(26)}
for i in range(len_s):
  dictionary[s[i]].append(i)
repeat = 0
cur_index = -1
for c in t:
  indices = dictionary[c]
  if not indices:
    repeat = 0
    cur_index = -2
    break
  next_index = indices[0]
  for index in indices:
    if index > cur_index:
      next_index = index
      break
  else:
    repeat += 1
  cur_index = next_index
print(len_s * repeat + cur_index + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s = list(input())
s += s
t = list(input())
ls = len(s)
check = [[] for i in range(26)]
for i in range(len(s)):
    o = ord(s[i])-ord("a")

    check[o].append(i+1)
ans = 0
c1 = 0
for i in t:
    o =ord(i)-ord("a")
    if check[o]:
        com = False
        lo = len(check[o])
        for j in range(lo):
            if ans < c1*len(s)+check[o][j]:
                ans = c1*len(s)+check[o][j]
                com = True
                break   
        if not com:
            c1 += 1
            for j in range(lo):
                if ans < c1*len(s)+check[o][j]:
                    ans = c1*len(s)+check[o][j]
                    
                    com = True
                    break   

    else:
        print(-1)
        exit()
    
print(ans)

Submission status: Time Limit Exceeded

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

def list_check2(list1, list2):
    return set(list1).issubset(list2)

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


if list_check2(t_list, s_list):
  i = 0
  j = 0
  while j < len(t):
    if s[i % len(s)] == t[j]:
      j += 1
    else:
      pass
    i += 1
  print(i)
      
else:
  print("-1")

Submission status: Time Limit Exceeded

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

def list_check2(list1, list2):
    return set(list1).issubset(list2)

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

s_list_check = sorted(list(set(s_list)))
t_list_check = sorted(list(set(t_list)))


if list_check2(t_list, s_list):
  i = 0
  j = 0
  while j < len(t):
    if s[i % len(s)] == t[j]:
      j += 1
    else:
      pass
    i += 1
  print(i)
      
else:
  print("-1")

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
dic = {}
for i,s in enumerate(S):
  if s not in dic:
    dic[s] = [i]
  else:
    dic[s].append(i)
#print(dic)
ind = -1
loop = 0
for t in T:
  if t not in dic:
    ans = -1
    break
  if dic[t][-1]<=ind:
    loop += 1
    ind = dic[t][0]
  else:
    for i in dic[t]:
      if i > ind:
        ind = i
        break
  #print(ind)
#print(loop,ind)
else:
  ans = len(S)*loop+ind+1
          
print(ans)   

#print(*ans[1:], sep='\n')

Submission status: Time Limit Exceeded

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

a = ord('a')
alph = [[] for _ in range(ord('z')-a+1)]
for i, c in enumerate(s):
  alph[ord(c)-a].append(i)

tmp = alph[ord(t[0])-a]
if tmp:
  idx = min(tmp)
  for c in t[1:]:
    tmp = alph[ord(c)-a]
    if tmp:
      idx += min(map(lambda x: (x - idx - 1) % len_s + 1, tmp))
    else:
      idx = -2
      break
  print(idx + 1)
else:
  print(-1)

Submission status: Time Limit Exceeded

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

a = ord('a')
alph = [[] for _ in range(ord('z')-a+1)]
for i, c in enumerate(s):
  alph[ord(c)-a].append(i)

tmp = alph[ord(t[0])-a]
if tmp:
  idx = min(tmp)
  for c in t[1:]:
    tmp = alph[ord(c)-a]
    if tmp:
      position = idx % len_s
      delta = len_s
      for i in tmp:
        delta = min(delta, (i - idx - 1) % len_s + 1)
      idx += delta
    else:
      idx = -2
      break
  print(idx + 1)
else:
  print(-1)

Submission status: Time Limit Exceeded

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

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i + 1)

out = 0
cnt = -1
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] <= V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * (cnt + 1))
    else:
        print(len(S) * cnt + V[-1])
a = 0

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
N, M = len(s), len(t)

if t in s:
    print(s.find(t) + len(t))

else:
    schr, indchr = dict(), dict()
    for i in range(N):
        if s[i] in schr:
            schr[s[i]].append(i+1) 
        else:
            schr[s[i]] = [i+1]
            indchr[s[i]] = 0

    schrset = set(schr)
    ans, pos, back = 0, 0, True
    for i in range(M):
        if t[i] in schrset:
            c = schr[t[i]]
            if c[-1] <= pos:
                ans += N - pos + c[0]
                pos = c[0]
                if not back:
                    for x in indchr.keys():
                        indchr[x] = 0
                    back = True
            else:
                while c[indchr[t[i]]] <= pos:
                    indchr[t[i]] += 1
                ans += c[indchr[t[i]]] - pos
                pos, back = c[indchr[t[i]]], False
        else:
            print(-1)
            exit()
    print(ans)

Submission status: Time Limit Exceeded

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

if t in s:
    print(s.find(t) + len(t))
else:
    schr = dict()
    for i in range(N):
        if s[i] in schr:
            schr[s[i]].append(i+1) 
        else:
            schr[s[i]] = [i+1]

    schrset = set(schr)
    ans, pos, pre, back = 0, 0, "#", False
    for i in range(len(t)):
        if t[i] in schrset:
            c = schr[t[i]]
            if c[-1] <= pos:
                ans += N - pos + c[0]
                pos, back = c[0], True
            else:
                if pre != t[i] or back:
                    j = 0
                while c[j] <= pos:
                    j += 1
                ans += c[j] - pos
                pos, pre, back = c[j], t[i], False
        else:
            print(-1)
            exit()
    print(ans)

Submission status: Time Limit Exceeded

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

if t in s:
    print(s.find(t) + len(t))
else:
    schr = dict()
    for i in range(N):
        if s[i] in schr:
            schr[s[i]].append(i+1) 
        else:
            schr[s[i]] = [i+1]

    schrset = set(schr)
    ans, pos, pre = 0, 0, "#"
    for i in range(len(t)):
        if t[i] in schrset:
            c = schr[t[i]]
            if c[-1] <= pos:
                ans += N - pos + c[0]
                pos = c[0]
            else:
                if pre != t[i]:
                    j = 0
                while c[j] <= pos:
                    j += 1
                ans += c[j] - pos
                pos = c[j]
        else:
            print(-1)
            exit()
    print(ans)

Submission status: Time Limit Exceeded

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

schr = dict()
for i in range(N):
    if s[i] in schr:
        schr[s[i]].append(i+1) 
    else:
        schr[s[i]] = [i+1]

ans, pos = 0, 0
for i in range(len(t)):
    if t[i] in schr:
        c = schr[t[i]]
        if c[-1] <= pos:
            ans += N - pos + c[0]
            pos = c[0]
        else:
            j = 0
            while c[j] <= pos:
                j += 1
            ans += c[j] - pos
            pos = c[j]
    else:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        for j in range(len(obj[char])):
            if obj[char][j] > temp_num:
                temp_num = obj[char][j]
                break
            elif j == len(obj[char]) - 1:
                loop_num += 1
                temp_num = obj[char][0]

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        next_num = next(itertools.filterfalse(lambda x: x <= temp_num, obj[char]), None)
        if next_num == None:
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = next_num

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        filtered = [x for x in obj[char] if x > temp_num]
        if len(filtered) == 0:
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = filtered[0]

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり整数
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

S = input()
T = input()

next = [[INF] * 30 for i in range(len(S))]
S *=2

# i文字目から次の文字cまでの距離
for i in range(len(S)//2):
    for c in range(26):
           
        for j in range(i+1, len(S)):
            if S[j] == chr(c+ord("a")):
                next[i][c] = j-i
                break

ans = 0
now = 0
for check in range(len(T)):
    if T[check] == S[0] and check == 0:
        check+=1
        continue

    stride = next[now][ord(T[check])-ord("a")]

    if stride == INF:
        print(-1)
        sys.exit()

    ans += stride
    now += stride
    now %= len(S)//2

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり整数
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

S = input()
T = input()

next = [[INF] * 30 for i in range(len(S))]
S *=2

# i文字目から次の文字cまでの距離
for i in range(len(S)//2):
    for c in range(26):
           
        for j in range(i+1, len(S)):
            if S[j] == chr(c+ord("a")):
                next[i][c] = j-i
                break

ans = 0
now = 0
for check in range(len(T)):
    if T[check] == S[0] and check == 0:
        check+=1
        continue

    if next[now][ord(T[check])-ord("a")] == INF:
        print(-1)
        sys.exit()

    ans += next[now][ord(T[check])-ord("a")]
    now += next[now][ord(T[check])-ord("a")]
    now %= len(S)//2

print(ans+1)

Submission status: Time Limit Exceeded

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
len_S = len(S)
T = sr()
dict_S = defaultdict(list)
for i, s in enumerate(S):
    dict_S[s].append(i)

answer = 0
cur = -1
for t in T:
    turn = 0 # 1周した時 len_S - cur
    if not dict_S[t]:
        print(-1)
        exit()
    indexes = dict_S[t] + [len_S]
    i = bisect.bisect_right(indexes, cur)
    next = indexes[i]
    if next == len_S:
        turn = len_S - cur - 1
        cur = -1
        answer += indexes[0] - cur + turn
        cur = indexes[0]
    else:
        answer += next - cur
        cur = next

print(answer)

Submission status: Time Limit Exceeded

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
len_S = len(S)
T = sr()
dict_S = defaultdict(list)
dict_T = defaultdict(list)
for i, s in enumerate(S):
    dict_S[s].append(i)

for i, t in enumerate(T):
    dict_T[t].append(i)

answer = 0
cur = -1
for t in T:
    if not dict_S[t]:
        print(-1)
        exit()
    indexes = dict_S[t] + [len_S]
    i = bisect.bisect_right(indexes, cur)
    next = indexes[i]
    if next == len_S:
        answer = (-(-answer//len_S)) * len_S
        cur = -1
        answer += indexes[0] - cur
        cur = indexes[0]
    else:
        answer += next - cur
        cur = next

print(answer)
# 32

Submission status: Time Limit Exceeded

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

s_dict = {c:[] for c in s}
for i, c in enumerate(s):
  s_dict[c].append(i)

len_s = len(s)

ans = 0
prev_i = -1
for c in t:
  if c not in s_dict:
    ans = -1
    prev_i = -1
    break;
  else:
    if s_dict[c][-1] <= prev_i:
      ans += len_s 
      prev_i = min(i for i in s_dict[c])
    else:
      prev_i = min(i for i in s_dict[c] if i > prev_i)


print(ans + prev_i + 1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    m = 0
    st = s
    for i in t:
        if i in st:
            j = st.index(i)
            m += j + 1
            st = st[j+1:]
        else:
            m += len(st)
            st = s
            j = st.index(i)
            st = st[j+1:]
            m += j + 1
    return m
print(main())

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
for i in t:
    if i not in s:
        print(-1)
        exit()
i, j = 0, 0
while j < len(t):
    if s[i%len(s)] == t[j]:
       j += 1
    i += 1
print(i)

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/abc138/submissions/8926003

S = input()
T = input()
if not set(T) <= set(S):
    print(-1)
    exit()
now = -1
rep = 0
for t in T:
    now = S.find(t,now+1)
    if now == -1:
        rep += 1
        now = S.find(t)
print(rep*len(S)+now+1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
s = s+s
for i in range(2*N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
nex = [[0]*N for _ in range(26)]
for now in range(N):
    for alp in range(26):
        if not lis[alp]:
            continue
        i = bisect_left(lis[alp],now+1)
        #print(lis[alp],now+1,i)
        nex[alp][now] = lis[alp][i] - now
ans = 0
now = 0
tN = len(t)
for i in range(tN):
    alp = ord(t[i])-97
    ne = nex[alp][now]
    ans += ne
    if now+ne >= N:
        now += ne-N
    else:
        now += ne
    #print(now,ans)
print(ans)

Submission status: Time Limit Exceeded

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

for c in t:
    if c not in s:
        print(-1)
        exit()

i = 0
mod = len(s)
for c in t:
    while True:
        if s[i % mod] == c:
            i += 1
            break
        else:
            i += 1
    
print(i)

Submission status: Time Limit Exceeded

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

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

    s_indexes = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i, s_c in enumerate(s):
        s_indexes[s_c].append(i)
    s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
    s_length = {c: len(s_indexes[c]) for c in "abcdefghijklmnopqrstuvwxyz"}

    power = 0
    last_index = -1
    for i, t_c in enumerate(t):
        if s_length[t_c] <= s_pointer[t_c]:
            # reset
            s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
            power += 1
        elif s_indexes[t_c][s_pointer[t_c]] <= last_index:
            for i, index in enumerate(s_indexes[t_c]):
                if last_index < index:
                    s_pointer[t_c] = i
                    break
            else:
                # reset
                s_pointer = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
                power += 1

        last_index = s_indexes[t_c][s_pointer[t_c]]
        s_pointer[t_c] += 1

    print(len(s) * power + last_index + 1)


main()

Submission status: Time Limit Exceeded

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

NX=[[-1]*26 for _ in range(len(S))]

for i in range(len(S)*2-1)[::-1]:
    idx = i%lenS
    idx2 = (i+1)%lenS
    for j in range(26):
        if NX[idx2][j] != -1:
            NX[idx][j] = NX[idx2][j] + 1
    NX[idx][ord(S[idx2])%26] = 1

# for lis in NX:
#     print(lis)
# for c in S:
#     print(ord(c)%26, end=" ")
# print("")

res = 0
prev=lenS-1
for c in T:
    v = NX[prev][ord(c)%26]
    if v == -1:
        print(-1)
        exit()
    else:
        res += v
        prev = (prev + v)%lenS

print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq
MAX_VALUE = 10**100
S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  heapq.heappush(Si[s],i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    if ans<=max(Si[t]):
      while idx<ans:
        idx = heapq.heappop(Si[t])
        heapq.heappush(Si[t],idx+lenS)
    else:
      factor = (ans-min(Si[t]))//lenS
      idx = heapq.heappop(Si[t])
      heapq.heappush(Si[t],idx+lenS*factor)
      while idx<ans:
        idx = heapq.heappop(Si[t])
        heapq.heappush(Si[t],idx+lenS)
    ans = idx
    if MAX_VALUE<ans:
      print(-1)
      exit()
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  heapq.heappush(Si[s],i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    while idx<ans:
      idx = heapq.heappop(Si[t])
      heapq.heappush(Si[t],idx+lenS)
    ans = idx
print(ans+1)

Submission status: Time Limit Exceeded

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

j = 0
ans = 0

while j < len(t):
  ok=0
  for i in range(len(s)):
    ans += 1
    if t[j]==s[i]:
      ok=1
      j+=1
    if j >= len(t):
      break
  if not ok:
    print('-1')
    break
    
if ok:print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
  exit()

ss=s*2
ind=-1
ans=0
for c in t:
  nex=ss[ind+1:].find(c)
  ind=(ind+1)+nex
  if ind>=len(s):
    ind-=len(s)
    ans+=len(s)

print(ans+ind+1)

Submission status: Time Limit Exceeded

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

dp = [-1]*(len(t)+1)
dp[0] = 0

for p in range(len(t)):
    d = s[dp[p] % len(s):].find(t[p])
    if d >= 0:
        dp[p+1] = dp[p]+d+1
    else:
        d = s[:dp[p] % len(s)].find(t[p])
        if d >= 0:
            dp[p+1] = dp[p]+d+1+len(s[dp[p] % len(s):])
        else:
            print(-1)
            exit()

print(dp[len(t)])

Submission status: Time Limit Exceeded

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

dp = [-1]*(len(t)+1)
dp[0] = 0

for p in range(len(t)):
    sd = s[dp[p] % len(s):]+s[:dp[p] % len(s)]
    d = sd.find(t[p])+1
    if d >= 1:
        dp[p+1] = dp[p]+d
    else:
        print(-1)
        exit()

print(dp[len(t)])

Submission status: Time Limit Exceeded

Solution code:
# Library
alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = 0
next_char = [[-1 for j in range(len(s))] for i in range(26)]
# nc[i, j]: j文字目以降(1-indexed)で'a'+i がいつ出てくるか

for i in range(26):
    ind = chr(ord('a') + i)
    for j in range(len(s)):
        next_char[i][j] = ss.find(ind, j) - (j - 1)
        # print("next " + alp[i] + " is " + str(next_char[i][j]))

for i in range(len(t)):
    tmp = next_char[ord(t[i]) - ord('a')][index % len(s)]
    if tmp <= 0:
        index = -1
        break
    else:
        index += tmp
        # print(index)

print(index)

Submission status: Time Limit Exceeded

Solution code:
# Library
alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = 0
next_char = [[-1 for j in range(len(s))] for i in range(26)]
# nc[i, j]: j文字目以降(1-indexed)で'a'+i がいつ出てくるか

for i in range(26):
    for j in range(len(s)):
        next_char[i][j] = ss.find(alp[i], j) - (j - 1)
        # print("next " + alp[i] + " is " + str(next_char[i][j]))


for i in range(len(t)):
    tmp = next_char[ord(t[i]) - ord('a')][index % len(s)]
    if tmp <= 0:
        index = -1
        break
    else:
        index += tmp
        # print(index)


print(index)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
schr = [0]*26
tchr = [0]*26
for i in range(len(s)):
    schr[ord(s[i])-97] = 1
for i in range(len(t)):
    tchr[ord(t[i])-97] = 1
for i in range(26):
    if tchr[i] and not schr[i]:
        print(-1)
        break
else:
    i = 0
    j = 0
    while True:
        if s[i%len(s)] == t[j]:
            if j==len(t)-1:
                break
            j += 1
        i += 1
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S, T):

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

    for k in si:
        si[k].append(-1)

    wsi = si
    used = defaultdict(deque)
    ans = 0
    i = -1
    # from pprint import pprint
    # pprint(si)
    for t in T:
        if t not in wsi:
            return -1

        while wsi[t][0] != -1:
            j = wsi[t].popleft()
            used[t].append(j)
            if j > i:
                i = j
                break
        else:
            ans += len(S)
            for k, q in used.items():
                while q:
                    wsi[k].appendleft(q.pop())
            i = wsi[t].popleft()
            used = defaultdict(deque)
            used[t].append(i)
    return ans + i + 1

def f(S, T):
    ans = -1
    ss = S * 1000
    for t in T:
        if t not in S:
            return -1
        for i in range(ans+1, len(ss)):
            if t == ss[i]:
                ans = i
                break
    return ans + 1





def main():
    S = read_str()
    T = read_str()
    print(slv(S, T))

    # S = ''.join(random.choices('ab', k=3))
    # T = ''.join(random.choices('ab', k=10))
    # print(S)
    # print(T)
    # print(slv(S, T))
    # print(f(S, T))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S, T):

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

    for k in si:
        si[k].append(-1)

    wsi = copy.deepcopy(si)
    ans = 0
    i = -1
    for t in T:
        if t not in wsi:
            return -1
        j = wsi[t].popleft()
        if j > i:
            i = j
        else:
            ans += len(S)
            wsi = copy.deepcopy(si)
            i = wsi[t].popleft()


    return ans + i + 1

def main():
    S = read_str()
    T = read_str()
    print(slv(S, T))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


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

    charset = set()
    for c in t:
        charset.add(c)
    for c in charset:
        if c not in s:
            print(-1)
            exit(0)

    d = defaultdict(list)  # d[c] := cはsの何番目に出現するか
    for i, c in enumerate(s):
        d[c].append(i + 1)

    ans = 0
    S = s
    at = 0
    for c in t:
        found = False
        while not found:
            for i in d[c]:
                if i > at:
                    ans += i - at
                    at = i
                    found = True
                    break
            if not found:
                ans += len(S) - at
                at = 0
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

s = input()
t = input()

charset = set()
for c in t:
    charset.add(c)
for c in charset:
    if c not in s:
        print(-1)
        exit(0)

d = defaultdict(list)  # d[c] := cはsの何番目に出現するか
for i, c in enumerate(s):
    d[c].append(i + 1)

ans = 0
S = s
at = 0
for c in t:
    found = False
    while not found:
        for i in d[c]:
            if i > at:
                ans += i - at
                at = i
                found = True
                break
        if not found:
            ans += len(S) - at
            at = 0
print(ans)