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:
#!/usr/bin/env python3
 
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
import math

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop, heappushpop, heapify, heapreplace
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
import math
# 以下を記述しないとTLEになる, 何故？
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappop, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
# from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
#from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
#from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from collections import defaultdict

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

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

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(1000000000)

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Python3 (3.4.3)
import sys

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input()
T = input()

chars1 = set()
for t in T:
    chars1.add(t)
chars2 = set()
for s in S:
    chars2.add(s)

for c in chars1:
    if c not in chars2:
        print(-1)
        sys.exit()

idx = S.index(T[0])
ans = idx+1
for i in range(1,len(T)):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()

alpha = 'abcdefghijklmnopqrstuvwxyz'
f = [False]*26
f2 = [False]*26
for i in range(len(S)):
    f[alpha.index(S[i])] = True
for i in range(len(T)):
    f2[alpha.index(T[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        sys.exit()


idx = S.index(T[0])
ans = idx+1
for i in range(1,len(T)):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()

chars1 = set()
for t in T:
    chars1.add(t)
chars2 = set()
for s in S:
    chars2.add(s)

for c in chars1:
    if c not in chars2:
        print(-1)
        sys.exit()

idx = S.index(T[0])
ans = idx+1
for i in range(1,len(T)):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()

chars = set()
for t in T:
    chars.add(t)

for c in chars:
    if S.find(c) == -1:
        print(-1)
        sys.exit()

idx = S.index(T[0])
ans = idx+1
for i in range(1,len(T)):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import deque
import math
import fractions
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

s=input()
n=len(s)
t=input()
lt=len(t)
i=0
k=0
check=[-1]*n
while True:
    if i==lt:
        print(k)
        exit()
    if t[i]==s[k%n]:
        i+=1
    if check[k%n]==i:
        print(-1)
        exit()
    else:
        check[k%n]=i
    k+=1

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
if not set(t) <= set(s):
    print(-1)
    exit()
t_index = 0
cnt = 0
last = 0
while t_index < len(t):
    cnt += 1
    for i in range(len(s)):
        if t[t_index] == s[i]:
            t_index += 1
        if t_index == len(t):
            last = i
            break
print((cnt-1)*len(s)+last+1)

Submission status: Time Limit Exceeded

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()

    d = [[] for _ in range(26)]
    p = [0] * 26
    for i,x in enumerate(s):
        d[ord(x)-ord('a')].append(i+1)

    rev = 0
    a = 0
    for x in t:
        x = ord(x) - ord('a')
        if len(d[x]) == 0:
            print(-1)
            return

        c = p[x]
        while d[x][c] <= a:
            c += 1
            if c >= len(d[x]):
                rev += 1
                p = [0] * 26
                a = 0
                c = 0
        a = d[x][c]

    print(rev*len(s) + a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()

    d = {chr(x):[] for x in range(ord('a'),ord('z')+1)}
    p = {chr(x):0 for x in range(ord('a'),ord('z')+1)}
    for i,x in enumerate(s):
        d[x].append(i+1)

    rev = 0
    a = 0
    for x in t:
        if len(d[x]) == 0:
            print(-1)
            return

        c = p[x]
        while d[x][c] <= a:
            c += 1
            if c >= len(d[x]):
                rev += 1
                p = {chr(x): 0 for x in range(ord('a'), ord('z') + 1)}
                a = 0
                c = 0
        a = d[x][c]

    print(rev*len(s) + a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)

from collections import defaultdict
d = defaultdict(list)

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        for jj in index:
            if prev < jj:
                ans+= jj-prev
                prev = jj
                break
        else:
            ans += (ls-prev)+index[0]
            prev = index[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)

from collections import defaultdict
d = defaultdict(list)

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        index.sort()
        for jj in index:
            if prev < jj:
                ans+= jj-prev
                prev = jj
                break
        else:
            ans += (ls-prev)+index[0]
            prev = index[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)
slist = [(ss,i) for i, ss in enumerate(s)]
tlist = [(tt,i) for i, tt in enumerate(t)]

from collections import defaultdict
d = defaultdict(list)

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        index.sort()
        for jj in index:
            if prev < jj:
                ans+= jj-prev
                prev = jj
                break
        else:
            ans += (ls-prev)+index[0]
            prev = index[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i,i+len(s)]
    else:
        ma[each_s].append(i)
        ma[each_s].append(i+len(s))
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    tmp_li.sort()
    #print(tmp_li,'tmp')

    lee = len(s_li)
    new_li = tmp_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min',lee)
    if min_index>= lee:
        repeat_count += 1
        min_index = new_li[0]
    elif min_index <= last_index:
        repeat_count += 1
        min_index = new_li[0]
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i]
    else:
        ma[each_s].append(i)
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li)

    lee = len(s_li)
    add_li = [ii+lee for ii in tmp_li]
    new_li = tmp_li + add_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min')
    if min_index>= lee:
        repeat_count += 1
        min_index -= lee
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    a=ord('a')
    d={chr(i+a): i for i in range(26)}
    s=list(map(lambda x:d[x],input()))
    t=list(map(lambda x:d[x],input()))
    l=[[-1]*26 for _ in range(len(s))]
    ap=[0]*26
    for i,a in enumerate(s*2):
        for j in range(ap[a],len(s)):
            l[j][a]=i-j
        ap[a]=i
    ans=0
    index=len(s)-1
    for a in t:
        n=l[index][a]
        if n==-1:
            print(-1)
            exit()
        ans+=n
        index+=n
        index%=len(s)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    a=ord('a')
    s=list(map(lambda x:ord(x)-a,list(input())))
    t=list(map(lambda x:ord(x)-a,list(input())))
    l=[[-1]*len(s) for _ in range(26)]
    ap=[0]*26
    for i,a in enumerate(s*2):
        for j in range(ap[a],len(s)):
            l[a][j]=i-j
        ap[a]=i
    ans=0
    index=len(s)-1
    for a in t:
        n=l[a][index]
        if n==-1:
            print(-1)
            exit()
        ans+=n
        index+=n
        index%=len(s)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    a=ord('a')
    s=list(map(lambda x:ord(x)-a,list(input())))
    t=list(map(lambda x:ord(x)-a,list(input())))
    l=[[-1]*26 for _ in range(len(s))]
    S=s*2
    ap=[0]*26
    for i,a in enumerate(S):
        for j in range(ap[a],len(s)):
            l[j][a]=i-j
        ap[a]=i
    ans=0
    index=len(s)-1
    for a in t:
        n=l[index][a]
        if n==-1:
            print(-1)
            exit()
        ans+=n
        index+=n
        index%=len(s)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())
lis = [[] for i in range(26)]
for i in range(len(s)):
    lis[ord(s[i])-ord("a")].append(i)
lislen = [len(lis[i]) for i in range(26)]
now = -1
ans = 0
  # print(lis)
for i in range(len(t)):
    if lislen[ord(t[i])-ord("a")] == 0:
        print(-1)
        exit()
    if lis[ord(t[i])-ord("a")][-1] <= now:
        now = lis[ord(t[i])-ord("a")][0]
        ans += len(s)
    elif now < lis[ord(t[i])-ord("a")][0]:
        now = lis[ord(t[i])-ord("a")][0]
    else:
        left = 0
        right = lislen[ord(t[i])-ord("a")]
        mid = 0
        while left < right:
            mid = (left+right)//2
            if now < lis[ord(t[i])-ord("a")][mid]:
                right = mid
            else:
                left = mid
        now = lis[ord(t[i])-ord("a")][mid]
print(ans+now+1)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
chk={}
sn=len(s)
ans=0
for i,a in enumerate(list(s)):#場所をビットで逆に保存する
    if a in chk:
        chk[a]+=2**i
    else:
        chk[a]=2**i
rep,pre=0,-1
for a in list(t):
    if a in chk:
        chk_num=chk[a]
        pre_next=0
        for i in range(pre+1,sn):
            if chk_num&1<<i:
                pre_next=i
                break
        if pre_next==0:
            for i in range(pre+1):
                if chk_num&1<<i:
                    pre_next=i
                    rep+=1
                    break
        pre=pre_next
    else:
        ans=-1
        break
if ans!=-1:
    ans=rep*sn+pre+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ans = -1
muri = False
for c in t:
    if c not in s:
        muri = True
if not muri:
    trimed_s = s
    trim = 'abcdefghijklmnopqrstuvwxyz'
    for c in t:
        index = trim.find(c)
        if index >= 0:
            trim = trim[:index] + trim[index+1:]
    
    for c in trim:
        while trimed_s.find(c) >= 0:
            index = trimed_s.find(c)
            trimed_s = trimed_s[:index] + trimed_s[index+1:]
    
    loop = 0
    while t:
        last = t
        for c in trimed_s:
            if t[0] == c:
                t = t[1:]
                if not t:
                    break
                # todo: trimed_sの更新
                if c not in t:
                    index = trimed_s.find(c)
                    trimed_s = trimed_s[:index] + trimed_s[index+1:]
        loop += 1
    last_index = 0
    for i in range(len(s)):
        c = s[i]
        if last[0] == c:
            last = last[1:]
            if not last:
                last_index = i
                break
    ans = len(s) * (loop-1) + last_index + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:


def submit():
    s = input()
    t = input()

    next_char = {}
    char_list = {}

    for i in reversed(range(len(s))):
        c = s[i]
        if c not in next_char.keys():
            next_char[c] = i
            char_list[(c, i)] = -1
        else:
            char_list[(c, i)] = next_char[c]
            next_char[c] = i

    
    init_next_char = next_char.copy()
    loop = 0
    curr = 0
    for c in t:
        # 実現不可能
        if c not in next_char.keys():
            print(-1)
            return

        while 0 <= next_char[c] < curr:
            next_char[c] = char_list[(c, next_char[c])]
        
        if next_char[c] < 0:
            loop += 1
            curr = 0
            next_char = init_next_char.copy()
        
        curr = next_char[c]
        next_char[c] = char_list[(c, next_char[c])]
    print(loop * len(s) + curr + 1)
        

submit()