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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input().rstrip()
x=list(s)
t=input().rstrip()
y=list(t)
l=[]
d=0;
for i in range(0,26):
    D=[]
    D.append(-1)
    l.append(D)
for i in range(0,len(s)):
    A=ord(s[i])-97;
    l[A].append(i)
for i in range(0,26):
    del(l[i][0])
KK=0;
for i in range(0,len(y)):
    if y[i] not in x:
        KK=1;
        break;        
    if i==0:
        A=ord(y[i])-97;
        C=l[A][0];
    else:
        A=ord(y[i])-97;
        R=l[A];
        I=0;
        J=len(R)-1;
        H=-999;
        while(I<=J):
            m=(I+J)//2;
            if R[m]<=C:
                I=m+1;
            else:
                H=R[m];
                J=m-1;
        if H==-999:
            C=R[0];
            d+=1;
        else:
            C=H;
if KK==1:
    print(-1)
else:
    print(d*len(x)+1+C)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
S_len = len(S)
S = S*2
if set(T) <= set(S):
    cnt = 0
    for t in T:
        cnt += S.index(t)+1
        S = S[S.index(t)+1:S.index(t)+1+S_len]*2
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

if (set(t) <= set(s)) == False:
    print(-1)
    exit()

len_s = len(s)
d = {}
for num, con in enumerate(s):
    d.setdefault(con, []).append(num+1)

cur = 0
ans = 0
for i in list(t):
    move = min(j - cur if j > cur else len_s + j - cur for j in d[i])
    ans += move
    cur = (cur + move) % len_s

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

debug = True
debug = False

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

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

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

    import collections
    didx = collections.defaultdict(int)

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

    dprint(d)
    dprint(didx)

    import bisect

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

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

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

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

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

main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
t = list(input())
n = len(s)
m = len(t)
s1 = list(set(s))
t1 = list(set(t))
key = 0
for i in range(len(t1)):
    if t1[i] not in s1:
        key = 1
if key == 0:
    count = 0
    i = 0
    j = 0
    while j < m:
        if s[i] == t[j]:
            i = i + 1
            j = j + 1
        else:
            i = i + 1
        if i == n:
            count = count + 1
            i = 0
    print(count*n+i)
else:
    print("-1")

Submission status: Time Limit Exceeded

Solution code:
import collections

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

    ns, nt = len(s), len(t)
    cs, ct = set(list(s)), set(list(t))
    for c in ct:
        if c not in cs: return -1

    d = collections.defaultdict(list)
    for i in range(ns):
        if s[i] in ct: d[s[i]].append(i)

    i = 0
    for c in t:
        while d[c][0] < i:
            d[c].append(d[c].pop(0)+ns)
        i = d[c][0]+1
    return i


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

Submission status: Time Limit Exceeded

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

jisho={}
alphabets = [chr(ord('a') + i) for i in range(26)]
for moji in alphabets:
    jisho[moji] = [i for i,x in enumerate(s) if x==moji]

lis = [jisho[moji] for moji in t]
if [] in lis:
    print(-1)
else:    
    old=-1
    count=0
    for i,cand in enumerate(lis):
        tes = [temp for temp in cand if temp>old]
        if len(tes)==0:
            num = min(cand)
        else:
            num = min(tes)
        if num<=old: count+=1
        old=num
    print(count*len(s)+old+1)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
res=0
if len(set(t)-set(s)) > 0:
    res=-1
else:
    pos={}
    set_t=set(t)
    for e_t in t:
        pos[e_t]=[]
    for i in range(len(s)):
        if s[i] in set_t:
            pos[s[i]].append(i+1)
    cur = 0
    nxt=0
    for i in range(len(t)):
        for e in pos[t[i]]:
            if e > cur:
                nxt=e
                break
        if nxt == cur:
            nxt = pos[t[i]][0]
            res+=len(s)
        cur=nxt
    res+=cur
print(res)

Submission status: Time Limit Exceeded

Solution code:

s = input()

t = input()

counter = 0
tmp = s

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

    elif i not in tmp:
        tmp = tmp + s

    num = tmp.find(i) + 1
    tmp = tmp[num:]
    
    counter += num

print(counter)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
i=0
flag2=1
flag=0
ls=len(s)
for char2 in t:
    for _ in range(ls):
        char=s[i%ls]
        i+=1
        if char==char2:
            flag=1
            break
    if flag:
        flag=0
    else:
        flag2=0
        break
if flag2:
    print(i)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
T = list(input())
S_len = len(S)
S = S*2
if set(T) <= set(S):
    cnt = 0
    for t in T:
        cnt += S.index(t)+1
        S = S[S.index(t)+1:S.index(t)+1+S_len]*2
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
'''p=input().rstrip().split(' ')
l=[]
q=[]
for i in range(0,int(p[0])-1):
    u=input().rstrip().split(' ')
    D=[]
    D.append(int(u[0]))
    E=[]
    E.append(int(u[1]))
    if D not in l:
        l.append(D)
        q.append(E)
    else:
        V=l.index(D)
        q[V].append(int(u[1]))
w=[0]*int(p[0])
S=[]
D=[]
for i in range(0,int(p[1])):
    u=input().rstrip().split(' ')
    if int(u[0]) not in S:
        S.append(int(u[0]))
        D.append(int(u[1]))
    else:
        G=S.index(int(u[0]))
        D[G]+=int(u[1])
V=[]
W=[]
for i in range(1,int(p[0])+1):
    DD=[]
    DD.append(i)
    XX=[]
    if DD in l:
        V.append(i)
        C=l.index(DD)
        A=q[C];
        G=0;
        while(len(A)!=0):
            X=A[0]
            XX.append(X)
            O=[]
            O.append(X)
            if O in l:
                Z=l.index(O)
                B=q[Z];
                for j in range(0,len(B)):
                    A.append(B[j])
            del(A[0])
    XX=list(set(XX))
    W.append(XX)
#print(V,W)
#print(S,D)
for i in range(0,len(S)):
    if S[i] in V:
        H=V.index(S[i])
        J=W[H];
        w[S[i]-1]+=D[i]
        for j in range(0,len(J)):
            w[J[j]-1]+=D[i];
    else:
        w[S[i]-1]+=D[i]
print(*w)'''


'''s=input().rstrip()
x=list(s)
t=input().rstrip()
y=list(t)
VVV=0;
if(1):
    C=-1;
    D=0;
    for i in range(0,len(y)):
        if y[i] not in x:
            VVV=1;
            break;
        T=y[i]
        CC=x[C+1:len(x)]
        if T in CC:
            V=CC.index(T)
            C=V+(C+1);
        else:
            D+=1;
            V=x.index(T)
            C=V;
    if VVV==1:
        print(-1)
    else:
        print(D*len(x) + C+1)'''


s=input().rstrip()
x=list(s)
t=input().rstrip()
y=list(t)
l=[]
q=[]
w=[]
S=[]
D=[]
d=0;
for i in range(0,26):
    D=[]
    D.append(-1)
    l.append(D)
for i in range(0,len(s)):
    A=ord(s[i])-97;
    l[A].append(i)
for i in range(0,26):
    del(l[i][0])
KK=0;
for i in range(0,len(y)):
    if y[i] not in x:
        KK=1;
        break;        
    if i==0:
        A=ord(y[i])-97;
        C=l[A][0];
    else:
        A=ord(y[i])-97;
        R=l[A];
        I=0;
        J=len(R)-1;
        H=-999;
        while(I<=J):
            m=(I+J)//2;
            if R[m]<=C:
                I=m+1;
            else:
                H=R[m];
                J=m-1;
        if H==-999:
            C=R[0];
            d+=1;
        else:
            C=H;
if KK==1:
    print(-1)
else:
    print(d*len(x)+1+C)

Submission status: Time Limit Exceeded

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

len_s = len(s)
d = {}
for num, con in enumerate(s):
    d.setdefault(con, []).append(num+1)

cur = 0
ans = 0
for i in list(t):
    x = d.get(i)
    if x == None:
        print(-1)
        exit()
   
    move = min([j - cur if j > cur else len_s + j - cur for j in x])
    ans += move
    cur = (cur + move) % len_s

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(1000000000)

def solve(positions, s, t):
    # print('{}, s = {}, t = {}'.format(positions, s, t))
    ans = 0
    while len(t) > 0:
        if len(positions[t[0]]) == 0:
            return -1

        i = 0
        j = 0
        while i < len(s) and j < len(t):
            candidates = positions[t[j]]
            pos = bisect.bisect_left(candidates, i)
            if pos == len(candidates):
                break

            i = candidates[pos] + 1
            j += 1

        if j == len(t):
            ans += i
            break
        else:
            ans += len(s)
            t = t[j:]

    return ans

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

    positions = defaultdict(list)
    for i in range(len(s)):
        positions[s[i]].append(i)

    print(solve(positions, s, t))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input() # 文字列を変数に格納
t = input() # 文字列を変数に格納

p = 0
count = 0

for i in range(len(t)):
    flag = 0
    for j in range(p,len(s)):
        if t[i] == s[j]:
            p = j+1
            flag = 1
            break
    if flag == 0:
        count += 1
        for j in range(0,p):
            if t[i] == s[j]:
                p = j+1
                flag = 1
                break
    if flag == 0:
        flag = 2
        break
        
if flag == 2:
    print(-1)
else:
    print(count*len(s) + p)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
res=0
if len(set(t)-set(s)) > 0:
    res=-1
else:
    dic={}
    set_t=set(t)
    for e_t in t:
        dic[e_t]=[]
    for i in range(len(s)):
        if s[i] in set_t:
            dic[s[i]].append(i+1)
    cur = 0
    for i in range(len(t)):
        nxt=cur
        for e in dic[t[i]]:
            if e > cur:
                nxt=e
                break
        if nxt == cur:
            nxt = dic[t[i]][0]
            res+=len(s)
        cur=nxt
    res+=cur
print(res)

Submission status: Time Limit Exceeded

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

debug = True
debug = False

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

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

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

    org_didx = {}
    for k in d.keys():
        org_didx[k] = 0

    didx = org_didx.copy()

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

    dprint(d)
    dprint(didx)

    import bisect

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

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

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

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

S = input()
T = input()
LS = len(S)
LT = len(T)

s = 0
t = 0
check = 0
loop = 0
while t < LT:
    if T[t] == S[s]:
        s += 1
        if s == LS:
            loop += 1
            s = 0
        t += 1
        check = 0
    else:
        s += 1
        if s == LS:
            loop += 1
            s = 0
        check += 1
        if check == LS:
            print('-1')
            sys.exit()

print(loop*LS+s)

Submission status: Time Limit Exceeded

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

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

ans = 0
index_sum = 0
s_work = s[:]
for i in t:
    index = s_work.find(i)
    if index == -1:
        ans += len(s)
        index_sum = 0
        s_work = s[:]
        index = s_work.find(i)
        index_sum += index + 1
    else:
        index_sum += index + 1
    s_work = s_work[index + 1:]

print(ans + index_sum)

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

d = [[] for _ in range(27)]
alpha2num = lambda c: ord(c) - ord("a") + 1
ans = 0

for i, s in enumerate(S):
    d[alpha2num(s)].append(i)

idx = -1
for t in T:
    dl = d[alpha2num(t)]
    if not(dl):
        ans = -1
        break
    for i in dl:
        if i > idx:
            ans += i - idx
            idx = i
            break
    else:
        ans += (len(S) - idx + dl[0])
        idx = dl[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def p_e():
    s = input()
    t = input()
    l = defaultdict(list)

    for i, c in enumerate(list(s)):
        l[c].append(i + 1)

    for c in list(t):
        if c not in l.keys():
            print(-1)
            exit()

    N = 0
    current = 0
    for c in list(t):
        R = l[c]

        if current >= R[-1]:
            current = R[0]
            N += 1
            continue

        for i in R:
            if current < i:
                current = i
                break

    print(N * len(s) + current)


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict

S=input()
T=input()

def solve():
    obj=defaultdict(list)
    for i,s in enumerate(S):
        obj[s].append(i)

    result=1
    mx=-1
    for t in T:
        flag=True

        if not obj[t]:
            return -1

        
        pos=(obj[t]+[-1])[bisect.bisect_right(obj[t],mx)]
        if pos==-1:
            mx=obj[t][0]
            result+=1
        else:
            mx=pos

    if pos==-1:
        pos=obj[t][0]
    return len(S)*(result-1)+pos+1
print(solve())

Submission status: Time Limit Exceeded

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

alphabet = 'abcdefghijklmnopqrstuvwxyz'
alphaset = set(s)
cache = []

def search(origin, c, offset):
    if c not in alphaset:
        return None
    offset = offset % len(origin)
    o = origin[offset:] + origin
    try:
        return o.index(c)
    except ValueError:
        return None


cache.append({c2: 0 for c2 in alphabet})
for c2 in alphabet:
    offset2 = search(s, c2, 1)
    if offset2 is None:
        cache[0][c2] = None
        continue
    cache[0][c2] = offset2 + 1
for i in range(1, len(s)):
    cache.append({c2: 0 for c2 in alphabet})
    for c2 in alphabet:
        if s[i] == c2:
            offset2 = search(s, c2, i + 1)
            if offset2 is None:
                cache[i][c2] = None
                continue
            cache[i][c2] = offset2 + 1
        else:
            offset2 = cache[i-1][c2]
            if offset2 is None:
                cache[i][c2] = None
                continue
            cache[i][c2] = offset2 - 1


a = search(s, t[0], 0)
if a is None:
    print(-1)
    exit()

result = a
for i in range(1, len(t)):
    k = cache[result % len(s)][t[i]]
    if k is None:
        print(-1)
        exit()
    result += k

print(result+1)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
if not set(t)<=set(s):
    print(-1)
else:
    ans=0
    for i in range(len(t)):
        ans=ans+int(s.index(t[i]))+1
        s=s[int(s.index(t[i]))+1:]+s[:int(s.index(t[i]))+1]
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
s=input().strip()
t=input().strip()
def gg(cc, c, l, d):
    if d[c][-1] <= cc:
        return d[c][1], l+1
    ll = d[c]
    mx, mn = len(ll)-2, 0
    x = (mx - mn)//2
    while True:
        if ll[x] <= cc and cc < ll[x+1]:
            return ll[x+1], l
        if cc < ll[x]:
            mx = x
            x = (mx-mn)//2
        else:
            mn = x
            x = (mx-mn)//2

def main():
    ss=set(s)
    tt=set(t)
    if len(tt - ss) != 0: 
        return -1
    d = dict()
    for i, c in enumerate(s):
        if c not in d:
            d[c] = [0]
        d[c].append(i+1)
    cc, l = 0, 0
    for c in t:
        cc, l = gg(cc, c, l, d)
    return l*len(s) + cc

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = list(input())
if not set(s) >= set(t):
    exit(print(-1))
i = 0
char = t.pop(0)
while True:
    if s[i % len(s)] == char:
        if t:
            char = t.pop(0)
        else:
            break
    i += 1
print(i+1)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
for i in T:
    if i not in S:
        print(-1)
        exit()

N = len(S)
nex = [[N] * 26 for i in range(N + 1)]
for i in range(N - 1, -1, -1):
    for j in range(26):
        nex[i][j] = nex[i + 1][j]
    nex[i][ord(S[i]) - ord('a')] = i


M = len(T)
i = 0
num = 0
j = 0
while j < M:
    if nex[i][ord(T[j]) - ord('a')] < N:
        num += nex[i][ord(T[j]) - ord('a')] - i + 1
        i = nex[i][ord(T[j]) - ord('a')] + 1
        j += 1
    else:
        num += N - i
        i = 0

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = str(input())
t = str(input())

uniq_t = list(set(list(t)))

uniq_s = list(set(list(s)))
for i in range(len(uniq_t)):
    if(uniq_t[i] not in uniq_s):
        print(-1)
        sys.exit()
i=0
s_i=0
t_j=0
while t_j<len(t):
    if(s[s_i] == t[t_j]):
        t_j += 1
    i+=1
    s_i+=1
    if(s_i >= len(s)):
        s_i = 0

print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def p_e():
    s = input()
    t = input()
    l = defaultdict(list)

    for i, c in enumerate(list(s)):
        l[c].append(i + 1)
    # 
    # for c in list(t):
    #     if c not in l.keys():
    #         print(-1)
    #         exit()

    N = 0
    current = 0
    for c in list(t):
        if not l[c]:
            print(-1)
            exit()

        if current >= l[c][-1]:
            current = l[c][0]
            N += 1
            continue

        for i in l[c]:
            if current < i:
                current = i
                break

    print(N * len(s) + current)


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
j = 0
cnt = 0
f = len(t)
g = len(s)
flag = True

while flag:
    c = 0
    cnt += 1
    for i in range(g):
        if s[i] == t[j]:
            j += 1
            c +=1
            if j == f:
                flag = False
                break
    

    if c == 0:
        if flag:
            print(-1)
            exit()

print((cnt-1)*g+i+1)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t= input()
if not set(t)<=set(s):
    print(-1)
else:
    ans=0
    for i in range(len(t)):
        n=int(s.index(t[i]))+1
        ans=ans+n
        s=s[n:]+s[:n]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections


def main():
    s = input()
    t = input()
    t_queue = collections.deque(t)
    tmp = t_queue.popleft()
    ans = 0
    for i in range(10 ** 100):
        length = len(t_queue)
        for j in range(len(s)):
            if s[j] == tmp:
                try:
                    tmp = t_queue.popleft()
                except IndexError:
                    ans = ((i) * len(s)) + j + 1
                    tmp = None
        if tmp is None:
            break
        if length == len(t_queue):
            ans = -1
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

s = input()
t = input()

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

# print(s_dict)

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

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