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: Wrong Answer

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_left

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

d = defaultdict(list)
for i,ch in enumerate(s):
    d[ch].append(i)

i = 0
n = 1
for ch in t:
    temp = d[ch]
    if temp == []:
        print(-1)
        exit()
    place = bisect_left(temp,i)
    if place==len(temp):
        n += 1
        i = temp[0]
    else:
        i = temp[place]

print((n-1)*len(s)+i+1)

Submission status: Wrong Answer

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

#str t の文字でstr sに存在しないものがあったら絶対成り立たない
if not len(set(t) - set(s)) == 0:
    print(-1)
else:
    idxes = [s.index(ti) for ti in t]
    cnt = 0
    n = 0
    
    for i in idxes[:-1]:
        if n > i:
            cnt += 1
        n = i

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

Submission status: Wrong Answer

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

m = 1000000000

d = {chr(i + ord('a')): m for i in range(26)}

for i, c in enumerate(s):
    d[c] = min(i + 1, d[c])

acc = 0
b = 0
for c in t:
    a = d[c]
    if a == m:
        acc = -1
        break
    if a > b:
        acc, b = acc + a - b, a
    else:
        acc, b = acc + N - b + a, a

print(acc)

Submission status: Wrong Answer

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

def bs(tl, i, l, r):
  while l < r:
    mid = (l + r) // 2
    if tl[mid] <= i:
      l = mid + 1
    else:
      r = mid
  return r


def main():
  s = input().strip()
  t = input().strip()
  sd = defaultdict(lambda: [])
  for i, _s in enumerate(s):
    sd[_s].append(i)

  for k, v in sd.items():
    sd[k] = list(sorted(v))

  ans = 0
  prev = -1
  for _t in t:
    if _t not in sd:
      break
    else:
      idx = bs(sd[_t], prev, 0, len(sd[_t])-1)
      idx = sd[_t][idx]
      if idx <= prev:
        ans += len(s) - prev + idx
      else:
        ans += idx - prev
      prev = idx
      if prev == len(s)-1:
        prev = -1
  else:
    print(ans)
    sys.exit(0)

  print(-1)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
ss=set(s)
tt=set(t)
tt <=ss
flag=0
if not tt<= ss:
    flag=1
if flag==1:
    print(-1)
else:
    ss=list(s)
    tt=list(t)
    l=len(ss)
    position=[]
    for x in tt:
        position.append(ss.index(x))
    count=0
    y=l
    for x in position:
        if x<y:
            y=x
        else:
            count+=1
    ans=count*l+x+1
    print(ans)

Submission status: Wrong Answer

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

m = 1000000000

d = {chr(i + ord('a')): m for i in range(26)}

for i, c in enumerate(s):
    d[c] = min(i + 1, d[c])

acc = 0
b = 0
for c in t:
    a = d[c]
    if a == m:
        acc = -1
        break
    if a > b:
        acc, b = acc + a - b, a
    else:
        acc, b = acc + 7 - b + a, a

print(acc)

Submission status: Wrong Answer

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

def main():
    # N = int(input())
    # N, K = map(int, input().split())
    # a = list(map(int, input().split()))
    s = input().strip()
    t = input().strip()
    len_s = len(s)

    dic = {}
    for i in range(len_s):
        if s[i] in dic:
            dic[s[i]].append(i)
        else:
            dic[s[i]] = [i]
    
    ok = True
    now = 0
    ans = 1
    for i in range(len(t)):
        if t[i] not in dic:
            ok = False
            break
        else:
            index = bisect.bisect(dic[t[i]], now)
            if index >= len(dic[t[i]]):# １週回ってからしかない
                ans += len_s
                now = dic[t[i]][0]
            else:# １週回るまでに見つかった
                now = dic[t[i]][index]
    if ok:
        print(ans+now)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
sd = s*150
c=0
try:
  for st in t:
    while not st == sd[c]:
      c=c+1
  print(c+1)
except IndexError:
  print(-1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
sd = s*30
c=0
try:
  for st in t:
    while not st == sd[c]:
      c=c+1
  print(c+1)
except IndexError:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import bisect

s = input().strip()
n = len(s)
t = input().strip()
m = len(t)

pos = [[] for i in range(26)]
for i, c in enumerate(s):
    pos[ord(c) - ord("a")].append(i)

poslen = [len(p) for p in pos]

syu = 0
tmp = 0
for c in t:
    tgt = pos[ord(c) - ord("a")]
    tlen = poslen[ord(c) - ord("a")]
    if not tgt:
        print(-1)
        sys.exit()
    else:
        ins = bisect.bisect_left(tgt, tmp+1)
        if ins == tlen:
            syu += 1
            tmp = tgt[0]
        else:
            # print(c, tgt, ins)
            tmp = tgt[ins]
print(syu*n + tmp + 1)

Submission status: Wrong Answer

Solution code:
abc=list(map(chr,range(97,123)))

s=input()
t=input()
m=len(s)
n=len(t)
for x in abc:
    if x in t and x not in s:
        print(-1)
        exit()
i=0
j=0
c=0
while j<n:
    while s[i]!=t[j]:
        if i!=m-1:i+=1
        else:c+=1;i=0
    j+=1
print(c*m+i+1)

Submission status: Wrong Answer

Solution code:
s=list(input())
t=input()
T=[]
for i in range(len(t)):
    if t[i] in s:
        T.append(s.index(t[i]))
    else:
        print(-1)
        exit()
ans=1
for k in range(len(T)-1):
    if T[k]<T[k+1]:
        continue
    else:
        ans+=1
print((ans-1)*len(s)+T[-1]+1)

Submission status: Wrong Answer

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

def bs(tl, i, l, r):
  while l < r:
    mid = (l + r) // 2
    if tl[mid] <= i:
      l = mid + 1
    else:
      r = mid
  return r


def main():
  s = input().strip()
  t = input().strip()
  sd = defaultdict(lambda: [])
  for i, _s in enumerate(s):
    sd[_s].append(i)

  for k, v in sd.items():
    sd[k] = list(sorted(v))

  ans = 0
  prev = -1
  for _t in t:
    if _t not in sd:
      break
    else:
      idx = bs(sd[_t], prev, 0, len(sd[_t])-1)
      idx = sd[_t][idx]
      if idx <= prev:
        ans += len(s) - prev + idx
      else:
        ans += idx - prev
      prev = idx
  else:
    print(ans)
    sys.exit(0)

  print(-1)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

ct = 0
k = 0
for i in t:
    f = s.find(i, k+1)
    if f < 0:
        ct += 1
        f = s.find(i)
        if f == -1:
            print(-1)
            break
        else:
            k = f
    else:
        k = f
else:
    print(ct*len(s)+k+1)

Submission status: Wrong Answer

Solution code:
import bisect
S=input()
T=input()
N=len(S)
M=len(T)
chardict=dict()
for i in range(26):
    chardict[chr(i+97)]=[]
for i in range(2*N):
    chardict[S[i%N]].append(i)
dp=[0 for i in range(M+1)]
for i in range(M):
    nowpoint=dp[i]%N
    cycle=dp[i]//N
    #cycle 周していて　nowpoint番目にいる
    if len(chardict[T[i]])==0:
        print(-1)
        exit()
    tmp=bisect.bisect_right(chardict[T[i]],nowpoint)
    dp[i+1]=cycle*N+chardict[T[i]][tmp]
print(dp[M]+1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    d = defaultdict(lambda : [])
    for i in range(n):
        d[s[i]].append(i)
    f = [0]*m
    alp = list("abcdefghijklmnopqrstuvwxyz")
    for i in range(m):
        if not d[t[i]]:
            print(-1)
            return
        j = bisect.bisect_right(d[t[i]],f[i-1])
        if j == len(d[t[i]]):
            f[i] = d[t[i]][0]
        else:
            f[i] = d[t[i]][j]
    ans = 0
    for i in range(m-1):
        if f[i] >= f[i+1]:
            ans += 1
    print(ans*n+f[-1]+1)
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
S = [ord(s)-97 for s in input().strip()]
T = [ord(t)-97 for t in input().strip()]

ls = len(S)

inf = 2*10**9

table = [None]*(2*ls)

ss = S + S
t = [inf]*26
for i in range(2*ls-1, -1, -1):
    z = ss[i]
    t[z] = i
    table[i] = t[:]

if any(table[0][ti] == inf for ti in T):
    print(-1)

else:
    ans = 0
    for ti in T:
       j = ans%ls
       k = table[j+1][ti] % ls
       if j < k:
           ans += k - j
       else:
           ans += ls + k - j
    print(ans + 1)

Submission status: Wrong Answer

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

ct = 0
k = 0
for i in t:
    f = s.find(i, k)
    if f < 0:
        ct += 1
        f = s.find(i)
        if f == -1:
            print(-1)
            break
        else:
            k = f
    else:
        k = f
else:
    print(ct*len(s)+k+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
S = input()
T = input()

cs = [[] for i in range(26)]
for i,s in enumerate(S):
    j = ord(s) - ord('a')
    cs[j].append(i)

for c in set(T):
    if not cs[ord(c) - ord('a')]:
        print(-1)
        exit()

rnd = k = 0
for t in T:
    ti = ord(t) - ord('a')
    i = bisect(cs[ti], k)
    if i == len(cs[ti]):
        k = cs[ti][0]
        rnd += 1
    else:
        k = cs[ti][i]

print(rnd*len(S) + k + 1)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
d = {}
for i in range(len(s)):
  if s[i] in d:
    d[s[i]] += [i]
  else:
    d[s[i]] = [i]
c = 0
cur = 0
for i in t:
  if i not in d:
    print(-1)
    exit()
  if cur < d[i][-1]:
    cur = d[i][bisect.bisect_right(d[i],cur)]
    continue
  else:
    cur = d[i][0]
    c += 1
print(c*len(s)+cur+1)

Submission status: Wrong Answer

Solution code:
import unittest
import collections
import bisect


def solve(s, t):
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)
    i = 0
    n = 0
    for c in t:
        if len(d[c]) == 0:
            return - 1
        k = bisect.bisect_left(d[c], i)
        if k == len(d[c]):
            n += 1
            k = bisect.bisect_left(d[c], 0)
        i = d[c][k]
    return len(s)*n+i+1


def main():
    s = input()
    t = input()
    print(solve(s, t))


class TestAbc138_e(unittest.TestCase):
    def test_abc138_e(self):
        self.assertEqual(solve('contest', 'son'), 10)
        self.assertEqual(solve('contest', 'programming'), -1)
        self.assertEqual(solve('contest', 'sentence'), 33)


if __name__ == "__main__":
    # unittest.main()
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s,t = input(),input()
s = [ord(v)-ord('a') for v in s]
t = [ord(v)-ord('a') for v in t]
indices = [list() for _ in range(26)]
for i,v in enumerate(s):
    indices[v].append(i)

loop = 0
cur = 0
for c in t:
    l = indices[c]

    if not l:
        cnt = -1
        break
    if l[-1] < cur:
        cur = l[0]+1
        loop += 1
    else:
        cur = l[bisect_left(l, cur)]+1
        if cur == len(s):
            cur = 0
print(loop*len(s)+cur)

Submission status: Wrong Answer

Solution code:
import bisect
s = input()
t = input()
d = {}
for i in range(len(s)):
  if s[i] in d:
    d[s[i]] += [i]
  else:
    d[s[i]] = [i]
c = 0
cur = 0
for i in t:
  if i not in d:
    print(-1)
    exit()
  if cur < d[i][-1]:
    cur = d[i][bisect.bisect_left(d[i],cur)]
    continue
  else:
    cur = d[i][0]
    c += 1
print(c*len(s)+cur+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s,t = input(),input()
s = [ord(v)-ord('a') for v in s]
t = [ord(v)-ord('a') for v in t]
indices = [list() for _ in range(26)]
for i,v in enumerate(s):
    indices[v].append(i)

loop = 0
cur = 0
for c in t:
    l = indices[c]

    if not l:
        cnt = -1
        break
    if l[-1] < cur:
        cur = l[0]
        loop += 1
    else:
        cur = l[bisect_left(l, cur)]+1
        if cur == len(s):
            cur = 0
print(loop*len(s)+cur)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    d = defaultdict(lambda : [])
    for i in range(n):
        d[s[i]].append(i)
    f = [0]*m
    alp = list("abcdefghijklmnopqrstuvwxyz")
    k = [0]*26
    for i in range(m):
        ai = alp.index(t[i])
        if not d[t[i]]:
            print(-1)
            return
        f[i] = d[t[i]][k[ai]]
        k[ai] = (k[ai]+1)%len(d[t[i]])
    ans = 0
    for i in range(m-1):
        if f[i] >= f[i+1]:
            ans += 1
    print(ans*n+f[-1]+1)
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
s = str(input())
t = str(input())
eng = [0 for i in range(26)]
  # print(ord("a"))
num = len(s)
for i in range(num):
    if eng[ord(s[i])-ord("a")] == 0:
        eng[ord(s[i])-ord("a")] = (i+1)
ans = eng[ord(t[0])-ord("a")]
if ans == 0:
    print("-1")
    exit()
nu = len(t)
for i in range(1,nu):
    if eng[ord(t[i])-ord("a")] == 0:
        print("-1")
        exit()
    if eng[ord(t[i-1])-ord("a")] < eng[ord(t[i])-ord("a")]:
        ans += (eng[ord(t[i])-ord("a")]-eng[ord(t[i-1])-ord("a")])
    else:
        ans += (eng[ord(t[i])-ord("a")]-eng[ord(t[i-1])-ord("a")])+num
print(ans)
  # print(eng)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  t=S()
  n2=len(t)

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

  # print(d)
  i=0
  j=0
  ans=1
  while j<n2:
    check=t[j]
    if check not in d:
      return -1
    l=d[check]
    if i<l[0]:
      ans+=l[0]-i+1
      i=l[0]+1
      j+=1
    elif l[-1]<i:
      ans+=n-(i+1)+l[0]+2
      i=l[0]+1
      j+=1
    else:
      if i==l[0]:
        ans+=1
        i+=1
        j+=1
      elif i==l[-1]:
        ans+=1
        i+=1
        j+=1
      else:
        left=0
        right=len(l)
        while right-left>1:
          m=(right-left)//2
          if l[m]>=i:
            right=m
          else:
            left=m
        ans+=l[right]-i+1
        i=l[right]+1
        j+=1

    # print(i,ans)

    i%=n

  return ans-1

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
setT=list(set(T))    
    
if set(T)<=set(S):
    i=0
    j=0
    while 1:
        if S[i%len(S)]==T[j]:
            j+=1
        if j==len(T):
            break
        i+=1
    print(i+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
setT=set(T)
flg=True
for t in setT:
    if not t in S:
        flg=False
if flg:
    i=0
    j=0
    while 1:
        if S[i%len(S)]==T[j]:
            j+=1
        if j==len(T):
            break
        i+=1
    print(i+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import lru_cache
    S = input()
    T = input()
    if set(S) & set(T) != set(T):
        print(-1)
    else:
        lt = len(T)
        st = set(T)
        D = dict()
        for t in st:
            D[t] = list()
            for i, s in enumerate(S):
                if t == s:
                    D[t].append(i)
        pre = -1
        cnt = 0

        @lru_cache(maxsize=None)
        def judge(pre, t):
            X = D[t]
            for x in X:
                if pre < x:
                    return (x, False)
                    break
            else:
                return (X[0], True)

        for t in T:
            J = judge(pre, t)
            pre = J[0]
            if J[1]:
                cnt += 1

        print(cnt * len(S) + pre + 1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
if set(S) & set(T) != set(T):
    print(-1)
else:
    lt = len(T)
    st = set(T)
    D = dict()
    for t in st:
        D[t] = list()
        for i, s in enumerate(S):
            if t == s:
                D[t].append(i)
    pre = -1
    cnt = 0

    for t in T:
        X = D[t]
        for x in X:
            if pre < x:
                pre = x
                break
        else:
            cnt += 1
            pre = X[0]
    print(cnt * len(S) + pre + 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


s = S()
t = S()
set_s = set(s)
set_t = set(t)
if (set_t <= set_s) is False:
    print(-1)
    exit()
alphabet2index = defaultdict(list)
for i, alphabet in enumerate(s):
    alphabet2index[alphabet].append(i+1)
ans = 0
pos = 0
prev_pos = 0
base = 0
n = -1
c = 0
for _t in t:
    n = s.find(_t, n+1)
    if (n == -1):
        c += 1
        n = s.find(_t)
ans = n + c*len(s) + 1
"""

    ng_flg = True
    while ng_flg:
        pos_lis = alphabet2index[_t]
        i = 0
        while len(pos_lis) > i:
            if (pos_lis[i] >= pos):
                pos = pos_lis[i]
                ans += (pos_lis[i]-prev_pos)
                # print(pos_lis[i], prev_pos, )
                prev_pos = pos
                ng_flg = False
                break
            i += 1
        else:
            prev_pos = pos - len(s)
            # print(prev_pos)
            # print('base', base)
            pos = 0
    """
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
if set(t) & set(s) == set(t):
    n = -1
    c = 0
    for i in t:
        try:
            n = list(s)[n + 1:].index(i) + n + 1
        except:
            n = -1
        if n == -1:
            c += 1
            try:
                n = list(s).index(i)
            except:
                n = -1
    print(n + len(s) * c + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
arr=[[] for i in range(len(t))]
ans=0

for i in range(len(t)):
    for j in range(len(s)):
        if t[i]==s[j]:
            arr[i].append(j)
    if arr[i]==[]:
        ans=-1
        break


if ans!=-1:
    d=arr[0][0]
    pos=arr[0][0]
    ans=d+1
    for i in range(len(t)-1):
        kari=len(s)
        for j in range(len(arr[i+1])):
            #print("a",arr[i+1][j]<=d)
            if arr[i+1][j]>d:
                if kari>arr[i+1][j]-d:
                    kari=arr[i+1][j]-d
                    pos=arr[i+1][j]
                    #print("b",arr[i+1][j])
            elif arr[i+1][j]<=d:    
                if kari>(len(s)-(d+1)+arr[i+1][j]+1):
                    kari=len(s)-(d+1)+arr[i+1][j]+1
                  
                    pos=arr[i+1][j]
                    #print("c",arr[i+1][j])
               
        #print(ans,arr[i+1][j],d,pos,kari)
        ans+=kari        
        d=pos     
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections,math
s = input()
t = input()
#tを構成文字で、sにない文字があったらダメ。
#構成できるなら最大でもlen(t)個しかないから、10^100の連結は必要ない
 
#最も不足する文字を探す
ls = collections.Counter(s)
lt = collections.Counter(t)
 
time_dict ={}
tmp=0
max_time=0#一番少ないやつ
for t_key,t_val in lt.items():
    if t_key not in ls:#sの中にtの文字がない
        print(-1)
        exit()
 
#多分TLEするけど、愚直解
cnt = 0
tt = list(t[::-1])
idx=0
while tt!=[]:
    if tt[-1]==s[idx]:
        tt.pop()
    cnt+=1
    idx = (idx+1)%len(s)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections,math
s = input()
t = input()
#tを構成文字で、sにない文字があったらダメ。
#構成できるなら最大でもlen(t)個しかないから、10^100の連結は必要ない

#最も不足する文字を探す
ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0#一番少ないやつ
for t_key,t_val in lt.items():
    if t_key not in ls:#sの中にtの文字がない
        print(-1)
        exit()

#多分TLEするかも。。数えすぎか
cnt = 0
tt = list(t[::-1])
idx=0
ss = s
while tt!=[]:
    next_t = tt.pop()
    idx=ss.find(next_t)
    if idx == -1:
        cnt += len(ss)
        idx = s.find(next_t)
        ss = s[idx+1:]
        cnt += idx+1
    else:
        cnt += idx+1
        ss = ss[idx+1:]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections,math
s = input()
t = input()
#tを構成文字で、sにない文字があったらダメ。
#構成できるなら最大でもlen(t)個しかないから、10^100の連結は必要ない

#最も不足する文字を探す
ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0#一番少ないやつ
for t_key,t_val in lt.items():
    if t_key not in ls:#sの中にtの文字がない
        print(-1)
        exit()

#多分TLEするけど、愚直解
cnt = 0
tt = list(t[::-1])
idx=0
while tt!=[]:
    if tt[-1]==s[idx]:
        tt.pop()
    cnt+=1
    idx = (idx+1)%len(s)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ans=0
cnt=0
while True:
  pin=0
  for i in range(len(s)):
    if s[i]==t[cnt]:
      cnt+=1
      pin+=1
      if cnt==len(t):
        ans+=i+1
        print(ans)
        exit()
     
  if pin==0:
      print(-1)
      exit()

  ans+=len(s)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    s = SS()
    t = SS()

    len_s = len(s)
    len_t = len(t)

    # アルファベットのs内のindex一覧
    l = [[] for _ in range(26)] 
    for i in range(len_s):
        l[ord(s[i]) - ord('a')].append(i)
    # print(l)

    if len([i for i in t if i in set(s)]) == len_t:
        # t内の文字がs内の何番目に登場するか
        t_idx = [l[ord(i)-ord('a')] for i in t]
        # print(t_idx)

        # 昇順部分がなるべく多くなるようにindexを選ぶ
        t_idx_best = [t_idx[0][0]]
        for i in range(1, len_t):
            p = t_idx_best[-1]
            idx = bisect.bisect_left(t_idx[i], p)
            if idx == len(t_idx[i]):
                t_idx_best.append(t_idx[i][0])
            else:
                t_idx_best.append(t_idx[i][idx])
        # print(t_idx_best)

        # 昇順じゃないところでsがもう一個必要になる
        ans = 0
        for i in range(len_t - 1):
            if t_idx_best[i] >= t_idx_best[i+1]:
                ans += len_s
        ans += t_idx_best[-1] + 1
        print(ans)

    else:
        print(-1)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from string import ascii_lowercase


def main():
    s = input()
    t = input()
    s_all = {s: 0 for s in ascii_lowercase}
    for ss in s:
        s_all[ss] += 1
    ans = 0
    if any(s_all[tt] == 0 for tt in t):
        ans = -1
    else:
        s_ind = -1
        rest = 0
        for i in range(len(t)):
            while True:
                s_ind += 1
                if s_ind == len(s):
                    s_ind = 0
                    ans += 1
                if s[s_ind] == t[i]:
                    rest = s_ind + 1
                    break
        ans *= len(s)
        ans += rest
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
s = str(input())
t = str(input())

alpha2num = lambda c: ord(c) - ord('a')

S2 = [[] for i in range(26)]
for i in range(len(s)):
  S2[alpha2num(s[i])].append(i)
  
#print(S2)
time = 0
place = -1
for i in range(len(t)):
  now = alpha2num(t[i])
  if S2[now] == []:
    print(-1)
    quit()
  else:
    if place not in S2[now]:
      index = bisect.bisect_left(S2[now], place)
    else:
      index = bisect.bisect_left(S2[now], place + 1)
    #print(index, S2[now])  
      
    if index == len(S2[now]):
      place = S2[now][0]
      time += 1
    else:  
      place = S2[now][index]
  #print(place, time)  
    
    
ans = len(s) * time + place + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import bisect
s = input()
t = input()

counter = defaultdict(list)
for i,c in enumerate(s):
  counter[c].append(i)

prev = 10**10
cycle = 0
for i,c in enumerate(t):
  if c not in counter:
    print(-1)
    exit()

  idx = counter[c]
  found = -1
  for j in idx:
    if j > prev:
      found = j
      break

  if found == -1:
    cycle += 1
    prev = idx[0]
  else:
    prev = found

print( (cycle-1)*len(s) + prev+1 )

Submission status: Time Limit Exceeded

Solution code:
s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	nx[('.',c)] = i+1
	for j in range(i+1,len(x)):
		if nx.get((c,x[j])) is None:
			nx[(c,x[j])] = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
def my_index(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default
s=list(input())
n=len(s)
t=input()
m=len(t)
rs=set(s)
b=0
ans=0
for i in range(m):
    if t[i] not in rs:
        print(-1)
        exit()
    ind=my_index(s[b:],t[i])
    if ind==-1:
        ind=my_index(s,t[i])+1
        ans+=n-b+ind
        b=ind
    else:
        ans+=ind+1
        b+=ind+1
print(ans)