Problem:


Score : 500 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.

Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').

Notes

A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

Constraints

1 \leq |s| \leq 10^5

1 \leq |t| \leq 10^5

s and t consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If there exists an integer i satisfying the following condition, print the minimum such i; otherwise, print -1.

Sample Input 1

contest
son

Sample Output 1

10

t = son is a subsequence of the string contestcon (the first 10 characters in s' = contestcontestcontest...), so i = 10 satisfies the condition.

On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s'), so i = 9 does not satisfy the condition.

Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10.

Sample Input 2

contest
programming

Sample Output 2

-1

t = programming is not a substring of s' = contestcontestcontest.... Thus, there is no integer i satisfying the condition.

Sample Input 3

contest
sentence

Sample Output 3

33

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.



Sample input:
contest
son


Sample output:
10

Submission status: Time Limit Exceeded

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

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])
f = [[] for _ in range(26)]

for i in range(len(s)):
    f[ord(s[i])-97].append(i)

g = [-1 for _ in range(len(t))]
if len(f[ord(t[0])-97]) == 0:
    print(-1)
    sys.exit()
g[0] = f[ord(t[0])-97][0]
cnt = 0
for i in range(1,len(t)):
    if len(f[ord(t[i])-97]) == 0:
        print(-1)
        sys.exit()

    if f[ord(t[i])-97][-1] > g[i-1]:
        for j in f[ord(t[i])-97]:
            if j > g[i-1]:
                g[i] = j
                break
    else:
        g[i] = f[ord(t[i])-97][0]
    if g[i] <= g[i-1]:
        cnt += 1

print(cnt*len(s)+g[-1]+1)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
moji = {}
for i in range(len(s)):
    if s[i] in moji.keys():
        moji[s[i]].append(i)
    else:
        moji[s[i]] = [i]

now = -1
kaisu = 0
flag = True
for i in range(len(t)):
    if t[i] in moji.keys():
        basho = moji[t[i]]
        for n in range(len(basho)):
            if basho[n] > now:
                now = basho[n]
                break
            elif n == len(basho) - 1 and basho[n] <= now:
                now = basho[0]
                kaisu += 1
    else:
        flag = False
        break
if flag:
    ans = kaisu * len(s) + now + 1
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])
f = [[] for _ in range(26)]

for i in range(len(s)):
    f[ord(s[i])-97].append(i)
g = [-1 for _ in range(len(t))]
if len(f[ord(t[0])-97]) == 0:
    print(-1)
    sys.exit()
g[0] = f[ord(t[0])-97][0]
cnt = 0
for i in range(1,len(t)):
    for j in f[ord(t[i])-97]:
        if j > g[i-1]:
            g[i] = j
            break
    if g[i] == -1:
        if len(f[ord(t[i])-97]) == 0:
            print(-1)
            sys.exit()
        g[i] = f[ord(t[i])-97][0]
    if g[i] <= g[i-1]:
        cnt += 1
    
print(cnt*len(s)+g[-1]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]
sset = set(s)
tset = set(t)
for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for letter in sset:
  i = ord(letter) - 97
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    if table[i][len(s)-j-2] < len(s): break
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

if tset - sset:
  print(-1)
  sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]

for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for i in range(26):
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

for letter in t:
  if s.find(letter) == -1:
    print(-1)
    sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
miru = s
ans = 0

for i in range(len(t)):
  miru = miru + s
  iti = miru.find(t[i])
  if iti == -1:
    ans = -1
    break
  ans += iti + 1
  miru = miru[iti+1:]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = input()
t = input()

t_set = set(t)

if len(t_set -set(s)) != 0:
    print(-1)
    sys.exit()

s_len = len(s)
def index_list(char):
    word = s
    ret = list()
    sum = 0
    try:
        while True:
            index = word.index(char)+ 1        
            sum+=index
            ret.append(sum)
            word = word[index:]
    except:
        if sum == 0:
            ret.append(-1)
    return ret

alpha_dict = dict()
for char in t_set:
    alpha_dict[char] = index_list(char)

index_old = 0
n_s = 0
for char in t:
    index = alpha_dict[char]
    
    if index[0] == -1:
        index_old = -1
        break
    
    flg = True
    for i in index:
        if i>index_old:
            index_old = i
            flg =False
            break
    if flg:
        index_old = index[0]
        n_s += 1

if index_old == -1:
    print(-1)
else:
    print(n_s*s_len + index_old)

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:
s = input()
t = input()

s_len = len(s)

def index_list(char):
    word = s
    ret = list()
    sum = 0
    try:
        while True:
            index = word.index(char)+ 1        
            sum+=index
            ret.append(sum)
            word = word[index:]
    except:
        if sum == 0:
            ret.append(-1)
    return ret

alpha_dict = dict()
for char in 'abcdefghijklmnopqrstuvwxyz':
    alpha_dict[char] = index_list(char)

index_old = 0
n_s = 0
for char in t:
    index = alpha_dict[char]
    
    if index[0] == -1:
        index_old = -1
        break
    
    flg = True
    for i in index:
        if i>index_old:
            index_old = i
            flg =False
            break
    if flg:
        index_old = index[0]
        n_s += 1

if index_old == -1:
    print(-1)
else:
    print(n_s*s_len + index_old)

Submission status: Time Limit Exceeded

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

sum = 0
word = s
try:
    for char in t:
        index = word.index(char)+ 1
        sum+=index 
        word = word[index:] + s
except:
    print(-1)
else:     
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

s = input()
t = input()



count = 0
s_len = len(s)
s_list = np.zeros(len(s))
t_list = []*len(t)

for i,k in enumerate(t):

  indexes = [j for j, x in enumerate(s) if x == k]
  if len(indexes) == 0:
    print(-1)
    sys.exit(0)
  else:
    t_list.insert(i,indexes)
    


pre = -1
for i in range(len(t)):
  
  high = [j  for j in t_list[i] if j > pre]
  if len(high) == 0:
    
    count += s_len - pre  + t_list[i][0]
    pre = t_list[i][0] 
  else:
    
    count += high[0] - pre 
    pre = high[0]

print(count)

Submission status: Time Limit Exceeded

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


def solve(S, T):
    for t in set(T):
        if t not in set(S):
            return -1

    S_double = S+S
    len_s = len(S)
    ans = -1
    for t in T:
        ans += S_double[(ans+1) % len_s:].index(t) + 1
    return ans + 1


print(solve(S, T))

Submission status: Time Limit Exceeded

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

def func(S, T):

    S_2 = S+S
    len_s = len(S)
    merge_S = list(set(S))
    merge_T = list(set(T))

    for t in merge_T:
        if t not in merge_S:
            return -1

    alp2num = {t: merge_T.index(t) for t in merge_T}
    dis_S = [[-1]*len(merge_T) for _ in range(len_s)]
    pt = S.index(T[0])
    ans = pt+1

    for t in T[1:]:
        it = alp2num[t]
        if dis_S[pt][it] == -1:
            dis_S[pt][it] = S_2[pt+1:].index(t) + 1
        ans += dis_S[pt][it]
        pt = (pt + dis_S[pt][it]) % len_s

    return ans

print(func(S,T))

Submission status: Time Limit Exceeded

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

def func(S, T):
    # Tの文字列のうち、一文字でもSにないなら条件を満たさない
    for t in T:
        if t not in S:
            return -1

    S_2 = S+S
    len_s = len(S)
    merge_T = list(set(T))
    alp2num = {t: merge_T.index(t) for t in merge_T}
    dis_S = [[-1]*len(merge_T) for _ in range(len_s)]
    pt = S.index(T[0])
    ans = pt+1

    for t in T[1:]:
        it = alp2num[t]
        if dis_S[pt][it] == -1:
            dis_S[pt][it] = S_2[pt+1:].index(t) + 1
        ans += dis_S[pt][it]
        pt = (pt + dis_S[pt][it]) % len_s

    return ans

print(func(S,T))

Submission status: Time Limit Exceeded

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

length = 0
can = True
for ith_t in t:
    if not ith_t in s:
        can = False
        break
if can:
    for ith_t in t:
        length += min((i-length)%len(s)+1 if s[i] == ith_t else len(s) for i in range(len(s)))

print(length if can else -1)

Submission status: Time Limit Exceeded

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

go = True
index_s = 0
length = 1

can = True
for ith_t in t:
    if not ith_t in s:
        can = False
        break
    while s[index_s] != ith_t:
        index_s = (index_s+1)%len(s)
        length+=1
    index_s = (index_s+1)%len(s)
    length+=1

print(length-1 if can else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = input()
t = input()

including = True
for x in t:
    if x  not in s:
        including = False
        break
if not including:
    print(-1)
    sys.exit()


x = 0
y = 0
while True:
    index = x % len(s)
    if s[index] == t[y]:
        y += 1
        if y == len(t):
            break
    x += 1

print(x + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

n = len(s)
m = len(t)

f = [False]*26
f2 = [False]*26

alpha = "abcdefghijklmnopqrstuvwxyz"
for i in range(n):
    f[alpha.index(s[i])] = True
for j in range(m):
    f2[alpha.index(t[j])] = True

for k in range(26):
    if not f[k] and f2[k]:
        print(-1)
        sys.exit()

ans = 0
ind = s.index(t[0])
ans+= (ind+1)
for i in range(1,m):
    s = s[ind+1:] + s[:ind+1]
    ind = s.index(t[i])
    ans += (ind + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    s2 = s * 2
    sett = list(set((t)))
    settindex = {}
    for i in sett:
        settindex[i] = sett.index(i)
        if i not in s:
            print(-1)
            return
    lens = len(s)
    # index[i文字目以降][settのindex]に何文字目にあるかが格納される
    index = [[] for _ in range(lens)]
    for i in range(lens):
        for j in sett:
            index[i].append(s2[i:].index(j))
    ans = 0
    n = 0
    for i in t:
        j = settindex[i]
        ans += index[n % lens][j] + 1
        n += index[n % lens][j] + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    T=ST()

    N = len(S)
    for t in T:
        if t not in S:
            print(-1)
            exit()

    chr_where = defaultdict(list)
    for i,s in enumerate(S):
        chr_where[s].append(i)
    
    cnt = 0 #何度先頭に戻ったか
    now = -1
    for t in T:
        index = bisect_right(chr_where[t], now)
        if index >= len(chr_where[t]):
            now = chr_where[t][0]
            cnt += 1
        else:
            now = chr_where[t][index]
        
    print(cnt*N + now + 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def func(S, T):
    # tの文字がsになかったら条件を満たさない
    for t in T:
        if t not in S:
            return -1

    ans = 0
    len_s = len(S)
    index = pre_index = -1

    for i in range(len(T)):
        while True:
            index += 1
            if T[i] == S[index%len_s]:
                ans += index - pre_index
                pre_index = index
                break
    return ans

print(func(S,T))

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    sett = list(set((t)))
    settindex = {}
    for i in sett:
        settindex[i] = sett.index(i)
        if i not in s:
            print(-1)
            return
    lens = len(s)
    lent = len(t)
    lensett = len(sett)
    # index[i文字目以降][settのindex]に何文字目にあるかが格納される
    index = [[] for _ in range(lens)]
    for i in range(lens):
        x = s[i:] + s[:i]
        for j in sett:
            index[i].append(x.index(j))
    ans = 0
    n = 0
    for i in t:
        j = settindex[i]
        ans += index[n % lens][j] + 1
        n += index[n % lens][j] + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    sett = list(set((t)))
    for i in sett:
        if i not in s:
            print(-1)
            return
    lens = len(s)
    lent = len(t)
    lensett = len(sett)
    # index[i文字目以降][settのindex]に何文字目にあるかが格納される
    index = [[] for _ in range(lens)]
    for i in range(lens):
        x = s[i:] + s[:i]
        for j in sett:
            index[i].append(x.index(j))
    ans = 0
    n = 0
    for i in t:
        j = sett.index(i)
        ans += index[n % lens][j] + 1
        n += index[n % lens][j] + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    sdash = s * 2
    ans = 0
    for i in t:
        if not i in s:
            print(-1)
            return
        index = sdash.index(i) + 1
        ans += index
        sdash = sdash[index:] + sdash[:index]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def umeru(r, ima):
	# ima: 今使ったカウンタ（※sをnokori込みで何回繰り返したか。端数なし）
	# r: あと埋めなきゃいけない文字
	# nokori: 余分にある文字。nokoriとrはdisjoint←になるなら不要？
	nokori = s
	ima = ima + 1
	count = 0
	for x in r:
		if (x in nokori):
		# xまで消す
			nokori = nokori[nokori.index(x) + 1:]
			count += 1
		else:
			break
	r = r[count:]
	return [r, nokori, ima]


l = sys.stdin.readlines()
s = list(l[0].strip())
t = list(l[1].strip()) 

if (not (set(t) <= set(s))) :
	print(-1)
else:
	r = t
	ima = 0
	ans = 0;
	while True:
		r, nokori, ima = umeru(r, ima)
		# print(r)
		if len(r) == 0:
			break
	ans = len(s) * ima - len(nokori)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
# tの文字種がsの文字種に含まれるなら、無限に繰り返せばO。含まれないならどのみち×。
# 最悪の場合：最初の文字が最後に……と全部リバースしている→この場合文字数分繰り返す
# 最悪の場合でもsの文字数×tの文字数で取得される。10^10

import sys


def umeru(r, nokori, ima):
	# ima: 今使ったカウンタ（※sをnokori込みで何回繰り返したか。端数なし）
	# r: あと埋めなきゃいけない文字
	# nokori: 余分にある文字。nokoriとrはdisjoint←になるなら不要？
	nokori = nokori + s
	ima = ima + 1
	count = 0
	for x in r:
		if (x in nokori):
		# xまで消す
			nokori = nokori[nokori.index(x) + 1:]
			count += 1
		else:
			break
	r = r[count:]
	return [r, nokori, ima]


l = sys.stdin.readlines()
s = list(l[0].strip())
t = list(l[1].strip()) 

if (not (set(t) <= set(s))) :
	print(-1)
else:
	r = t
	ima = 0
	nokori = []
	ans = 0;
	while True:
		r, nokori, ima = umeru(r, nokori, ima)
		# print(r)
		if len(r) == 0:
			break
	ans = len(s) * ima - len(nokori)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Strings of Impurity
from collections import defaultdict

s = input()
t = input()

if (set(s) & set(t)) != set(t):
    print('-1')
else:
    sChar = defaultdict(list)
    for i, v in enumerate(list(s)):
        sChar[v].append(i)
    
    def checkIdx(idxList, pre):
        for i in idxList:
            if i > pre:
                return i
        return -1
        
    i = 0
    preIndex = -1
    for c in list(t):
        idxs = [appear + i * len(s) for appear in sChar[c]]
        ret = checkIdx(idxs, preIndex)
        while ret == -1:
            i += 1
            for j, idx in enumerate(idxs):
                idxs[j] = idx + len(s)
            ret = checkIdx(idxs, preIndex)
        preIndex = ret

    print(preIndex + 1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import *
from collections import defaultdict
import sys
import time


#################### library ####################

def classify(iterable):
	dic = defaultdict(list)
	for k, v in iterable:
		dic[k].append(v)
	return dic


#################### naive ####################

def gen_s(s):
	s_ = ""
	for k in count():
		s_ += s[k%len(s)]
		yield s_

def has_substring(s, t):
	q = 0
	for p, c in enumerate(s):
		if c == t[q]:
			q += 1
			if q == len(t):
				return True
	else:
		return False

def f_naive():
	s, t = read_input()
	if any(c not in s for c in t):
		return -1
	
	for i, s_ in enumerate(gen_s(s), 1):
		if has_substring(s_, t):
			return i


#################### process ####################

def read_input():
#	import random
#	random.seed(11)
#	s = "".join(random.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(10**5))
#	t = "".join(random.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(10**5))
	
#	return ("sosson", "sonssnsso")
	s = raw_input()
	t = raw_input()
	return (s, t)

def make_next_pos(v, L):
	w = [0] * L
	p = 0
	for q in v:
		for k in range(p, q):
			w[k] = q
		p = q
	
	q = v[0]
	for k in range(p, L):
		w[k] = q
	return w

def f():
	s, t = read_input()
	if any(c not in s for c in t):
		return -1
	
	L = len(s)
	dic = classify((s[k], k) for k in range(len(s)))
	table = dict((c, make_next_pos(v, L)) for c, v in dic.items())
	p = -1
	i = -1
	for c in t:
		q = table[c][p]
		i += (q-p-1)%L+1
		"""
		if q == p:
			i += L
		elif q < p:
			i += q - p + L
		else:
			i += q - p
		"""
		p = q
#		print c, q, i
	return i+1


#################### main ####################

#print f_naive()
print f()

Submission status: Time Limit Exceeded

Solution code:
import collections

s = input()
t = input()
s_index = {}
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		if cursor > s_index[target][-1]:
			find = False
		else:
			for j in s_index[target]:
				if j >= cursor:
					find = True
					break
		diff = j - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

s = input()
t = input()
s_index = {}
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		for j in s_index[target]:
			if j >= cursor:
				find = True
				break
		diff = j - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = input()
n = len(s)
t = input()
m = len(t)

d = {}
for c in t:
    if c in d:
        continue
    else:
        d[c] = []
    for i in range(2*n):
        if s[i%n]==c:
            d[c].append(i)

res = -1
for i in range(m):
    c = t[i]
    if len(d[c])==0:
        print(-1)
        exit()

    j = 0
    while res%n>=d[c][j]:
        j += 1
    res += d[c][j] - res%n

print(res+1)

Submission status: Time Limit Exceeded

Solution code:
import collections

s = input()
t = input()
s_counter = collections.Counter(s)
t_counter = collections.Counter(t)
check = [s_counter[k] for k in t_counter.keys()]
if 0 in check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		for j in range(s_size):
			if s[(ans + j) % s_size] == target:
				ans += j + 1
				break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import *
from collections import defaultdict
import sys
import time


#################### library ####################

def classify(iterable):
	dic = defaultdict(list)
	for k, v in iterable:
		dic[k].append(v)
	return dic


#################### naive ####################

def gen_s(s):
	s_ = ""
	for k in count():
		s_ += s[k%len(s)]
		yield s_

def has_substring(s, t):
	q = 0
	for p, c in enumerate(s):
		if c == t[q]:
			q += 1
			if q == len(t):
				return True
	else:
		return False

def f_naive():
	s, t = read_input()
	if any(c not in s for c in t):
		return -1
	
	for i, s_ in enumerate(gen_s(s), 1):
		if has_substring(s_, t):
			return i


#################### process ####################

def read_input():
#	return ("sosson", "sonssnsso")
	s = raw_input()
	t = raw_input()
	return (s, t)

def make_next_pos(v, L):
	w = [0] * L
	p = 0
	for q in v:
		for k in range(p, q):
			w[k] = q
		p = q
	
	q = v[0]
	for k in range(p, L):
		w[k] = q
	return w

def f():
	s, t = read_input()
	if any(c not in s for c in t):
		return -1
	
	L = len(s)
	dic = classify((s[k], k) for k in range(len(s)))
	table = dict((c, make_next_pos(v, L)) for c, v in dic.items())
	p = -1
	i = -1
	for c in t:
		q = table[c][p]
		if q == p:
			i += L
		elif q < p:
			i += q - p + L
		else:
			i += q - p
		p = q
#		print c, q, i
	return i+1


#################### main ####################

#print f_naive()
print f()

Submission status: Time Limit Exceeded

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

if len(list(set(list(t))-set(list(s))))!=0:
    print("-1")
else:
    import copy
    def make_dict(s):
        s= str(s)
        ret={}
        for char_index in range(len(s)):
            char=list(s)[char_index]
            if char not in ret:
                ret[char]=[]
            ret[char].append(char_index)
        return ret
    dict_of_the_sentence=make_dict(s)
    s_len=len(s)
    t_len=len(t)
    ind_int=0
    insent_ind=0
    used={char:[] for char in dict_of_the_sentence}
    for char in list(t):
        while True:
            if not dict_of_the_sentence[char].__len__()==0:
                    temp_ind=dict_of_the_sentence[char].pop(0)
                    used[char].append(temp_ind)
                    if temp_ind>=insent_ind:
                        insent_ind=temp_ind
                        break
                    else:
                        pass
            else:
                ind_int=ind_int+s_len
                insent_ind=0
                for chars in used:
                    t_list=list(set(dict_of_the_sentence[chars])|set(used[chars]))
                    t_list.sort()
                    dict_of_the_sentence[chars]=t_list
                used = {chara: [] for chara in dict_of_the_sentence}

    ind_int=ind_int+insent_ind+1
    print(ind_int)

Submission status: Time Limit Exceeded

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

if len(list(set(list(t))-set(list(s))))!=0:
    print("-1")
else:
    import copy
    def make_dict(s):
        s= str(s)
        ret={}
        for char_index in range(len(s)):
            char=list(s)[char_index]
            if char not in ret:
                ret[char]=[]
            ret[char].append(char_index)
        return ret
    dict_of_the_sentence=make_dict(s)
    backup=copy.deepcopy(dict_of_the_sentence)
    s_len=len(s)
    t_len=len(t)
    ind_int=0
    insent_ind=0
    for char in list(t):
        while True:
            dict_of_the_sentence[char] = [thing for thing in dict_of_the_sentence[char] if thing >= insent_ind]
            if not dict_of_the_sentence[char].__len__()==0:
                insent_ind=dict_of_the_sentence[char].pop(0)
                break
            else:
                ind_int=ind_int+s_len
                insent_ind=0
                dict_of_the_sentence=copy.deepcopy(backup)
    ind_int=ind_int+insent_ind+1
    print(ind_int)

Submission status: Time Limit Exceeded

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

if len(list(set(list(t))-set(list(s))))!=0:
    print("-1")
else:
    import copy
    def make_dict(s):
        s= str(s)
        ret={}
        for char_index in range(len(s)):
            char=list(s)[char_index]
            if char not in ret:
                ret[char]=[]
            ret[char].append(char_index)
        return ret
    dict_of_the_sentence=make_dict(s)
    backup=copy.deepcopy(dict_of_the_sentence)
    s_len=len(s)
    t_len=len(t)
    ind_int=0
    insent_ind=0
    for char in list(t):
        while True:
            if not dict_of_the_sentence[char].__len__()==0:
                    temp_ind=dict_of_the_sentence[char].pop(0)
                    if temp_ind>=insent_ind:
                        insent_ind=temp_ind
                        break
                    else:
                        pass
            else:
                ind_int=ind_int+s_len
                insent_ind=0
                dict_of_the_sentence=copy.deepcopy(backup)
    ind_int=ind_int+insent_ind+1
    print(ind_int)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

else:
  d = {}
  for i in range(ls):
    if s[i] in d.keys():
      d[s[i]] += [i+1]
    else:
      d[s[i]] = [i+1]
  
  c = 0
  x = 0
  for j in range(lt):
    a = np.array(d[t[j]])
    idx = min(np.r_[a[a >= x], a[a < x]+ls])
    c += idx - x
    x = c % ls
    
  print(c)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import *
from collections import defaultdict
import sys
import time


#################### library ####################

def classify(iterable):
	dic = defaultdict(list)
	for k, v in iterable:
		dic[k].append(v)
	return dic


#################### naive ####################

def gen_s(s):
	s_ = ""
	for k in count():
		s_ += s[k%len(s)]
		yield s_

def has_substring(s, t):
	q = 0
	for p, c in enumerate(s):
		if c == t[q]:
			q += 1
			if q == len(t):
				return True
	else:
		return False

def f_naive():
	s, t = read_input()
	if any(c not in s for c in t):
		return -1
	
	for i, s_ in enumerate(gen_s(s), 1):
		if has_substring(s_, t):
			return i


#################### process ####################

def read_input():
#	return ("sosson", "sonssnsso")
	s = raw_input()
	t = raw_input()
	return (s, t)

def next_pos(c, p, dic):
	def bin_search(first, last, q):
		if last - first == 1:
			if v[first] == q-1:
				return v[first+1]
			else:
				return v[first]
		
		mid = (first + last) / 2
		if v[mid] > q:
			return bin_search(first, mid, q)
		else:
			return bin_search(mid, last, q)
	
	v = dic[c]
	if p == -1 or v[-1] <= p:
		return v[0]
	
	return bin_search(0, len(v), p+1)

def make_next_pos(v, L):
	w = [0] * L
	p = 0
	for q in v:
		for k in range(p, q):
			w[k] = q
		p = q
	
	q = v[0]
	for k in range(p, L):
		w[k] = q
	return w

def f():
	s, t = read_input()
	if any(c not in s for c in t):
		return -1
	
	L = len(s)
	dic = classify((s[k], k) for k in range(len(s)))
	table = dict((c, make_next_pos(v, L)) for c, v in dic.items())
	p = -1
	i = -1
	for c in t:
		q = table[c][p]
		if q == p:
			i += L
		elif q < p:
			i += q - p + L
		else:
			i += q - p
		p = q
#		print c, q, i
	return i+1


#################### main ####################

#print f_naive()
print f()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)

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

else:
  i = 0
  j = 0
  while True:
    if s[i % ls] == t[j]:
      j += 1
    
    if j >= lt:
      break
    
    i += 1

  print(i + 1)

Submission status: Time Limit Exceeded

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

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
t = raw_input()
s = raw_input()
def longest_subsequence_prefix(s, t):
    f = [[False for _ in range(len(t))] for _ in range(len(s))]

    f[0][0] = s[0] == t[0]

    for i in range(1, len(s)):
        f[i][0] = True if s[i] == t[0] else f[i-1][0]

    for i in range(1, len(s)):
        for j in range(1, len(t)):
            f[i][j] = s[i] == t[j] and f[i-1][j-1] or f[i-1][j]

    # for i in range(len(s)):
    #     print ' '.join(map(str, f[i]))

    for j in range(len(t)-1, -1, -1):
        for i in range(len(s)):
            if f[i][j]:
                return j, i

    return 0

from collections import Counter
import sys
from math import floor

def find_i(s, t):
    cs = Counter(s)
    ct = Counter(t)
    for char in ct:
        if char not in cs:
            return -1

    output = 0
    while len(t) > 0:
        idx_t, idx_s = longest_subsequence_prefix(s, t)
        if idx_t < len(t) - 1:
            output += len(s)
        else:
            output += idx_s + 1
        t = t[idx_t+1:]

    return output


# print(find_i("contest", "son"))

print(find_i(t, s))