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: Accepted

Solution code:

import bisect
import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

s = input()
t = input()

n = len(s)

def toi(c):
    return ord(c) - ord('a')

next_pos = array2d(n, 26, -1)

for i in range(n):
    c = toi(s[i])
    next_pos[i][c] = i

for i in range(n-2,-1,-1):
    for c in range(26):
        if next_pos[i][c] == -1 and next_pos[i+1][c] >= 0:
            next_pos[i][c] = next_pos[i+1][c]

res, now = 0, 0
for c in t:
    c = toi(c)
    if next_pos[now][c] < 0:
        res += n - now
        now = 0
        if next_pos[now][c] < 0:
            res = -1
            break
        else:
            res += next_pos[now][c] + 1
            now = next_pos[now][c] + 1
    else:
        res += next_pos[now][c] - now + 1
        now = next_pos[now][c] + 1
    now = now % n

print(res)

Submission status: Accepted

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

sc = [0] * 26
tc = [0] * 26

for i in range(len(s)):
    sc[ord(s[i]) - ord("a")] += 1
for i in range(len(t)):
    tc[ord(t[i]) - ord("a")] += 1

# 不可能な場合
for i in range(26):
    if tc[i] > 0 and sc[i] == 0:
        print(-1)
        exit()


alph = [[] for _ in range(26)]
for i in range(len(s)):
    alph[ord(s[i]) - ord("a")].append(i)

ans = [0] * len(t)
pre_num = -1
for i in range(len(t)):
    num = ord(t[i]) - ord("a")
    if i > 0:
        idx = bisect.bisect_right(alph[num], pre_num)
        if idx >= len(alph[num]):
            num_idx = alph[num][0]
        else:
            num_idx = alph[num][idx]
    else:
        num_idx = alph[num][0]
    ans[i] = num_idx
    pre_num = num_idx

count = 0
pre = -1
for v in ans:
    if pre >= v:
        count += 1
    pre = v

print(count * len(s) + ans[-1] + 1)

Submission status: Accepted

Solution code:
import sys

s = input()
t = input()
s_ = s
num = 1

for i in range(len(t)):
    if s.find(t[i]) == -1:
        print(-1)
        sys.exit()
    elif s_.find(t[i]) == -1:
        num += 1
        s_ = s[s.find(t[i]) + 1:]
    else:
        s_ = s_[s_.find(t[i]) + 1:]

print(num*len(s) - len(s_))

Submission status: Accepted

Solution code:
import sys

s = input()
t = input()
s_ = s
num = 1

for i in range(len(t)):
    if s.find(t[i]) == -1:
        print(-1)
        sys.exit()
    elif s_.find(t[i]) == -1:
        num += 1
        s_ = s[s.find(t[i]) + 1:]
    else:
        s_ = s_[s_.find(t[i]) + 1:]

print(num*len(s) - len(s_))

Submission status: Accepted

Solution code:
from pprint import pprint
import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

len_s = len(s)
ss = s+s
 
#table[ord(t)-97][i] = 文字tがi番目orそれ以降で登場する最初のindex
table = [[-1] * (len_s * 2) for _ in range(26)]
prev = [-1] * 26
for i,c in enumerate(ss):
    c_index = ord(c)-97
    # table[c_index][prev[c_index]+1:i+1] = [i] * (i - prev[c_index])
    for j in range(prev[c_index] + 1, i + 1):
        table[c_index][j] = i
    prev[c_index] = i
# pprint(table)

ans = 0
now = 0
for i in t:
    pos = table[ord(i)-97][now]
    if pos == -1:
        print(-1)
        exit()

    ans += pos + 1 - now
    now = ans % len_s

print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint
import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

len_s = len(s)
ss = s+s
 
#table[ord(t)-97][i] = 文字tがi番目orそれ以降で登場する最初のindex
table = [[-1] * (len_s * 2) for _ in range(26)]
prev = [-1] * 26
for i,c in enumerate(ss):
    cind = ord(c)-97
    table[cind][prev[cind]+1:i+1] = [i] * (i - prev[cind])
    prev[cind] = i
# pprint(table)

ans = 0
now = 0
for i in t:
    pos = table[ord(i)-97][now]
    if pos == -1:
        print(-1)
        exit()

    ans += pos + 1 - now
    now = ans % len_s

print(ans)

Submission status: Accepted

Solution code:
class Solution:
    def main(self):
        s = input()
        t = input()
        loop = 0
        string = s
        for i in range(len(t)):
            if s.find(t[i]) == -1:
                print(-1)
                return
            elif string.find(t[i]) == -1:
                loop += 1
                string = s[s.find(t[i])+1:]
            else:
                string = string[string.find(t[i])+1 :]

        print((loop+1)*len(s) - len(string))
        return

if __name__ == '__main__':
    Solution().main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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

ss = s+s

#table[ord(t)-97][i] = 文字tがi番目orそれ以降で登場する最初のindex
table = [[-1]*(ls*2) for _ in range(26)]
prev = [-1]*26
for i,c in enumerate(ss):
    cind = ord(c)-97
    table[cind][prev[cind]+1:i+1] = [i]*(i-prev[cind])
    prev[cind] = i

#print(table)

ans = 0
now = 0
for i in t:
    pos = table[ord(i)-97][now]
    if pos == -1:
        print(-1)
        exit()
    diff = pos +1 - now 
    ans += diff
    now = (now+diff)%ls


print(ans)

Submission status: Accepted

Solution code:
import sys
s=str(input())
t=list(input())
string=s
l=1
for i in range(len(t)):
  if s.find(t[i])==-1:
    print(-1)
    sys.exit()
  elif string.find(t[i])==-1:
    l+=1
    string=s[s.find(t[i])+1:]
  else:
    string=string[string.find(t[i])+1:]
  #print(string,l)

print(l*len(s)-len(string))

Submission status: Accepted

Solution code:
from bisect import bisect

s = input()
t = input()

indices = {}
N = len(s)
for i in range(N):
  try:
    indices[s[i]].append(i)
  except:
    indices[s[i]] = [i]

min_i = 0
cur = -1
for i in range(len(t)):
  try:
    idx = bisect(indices[t[i]], cur)
    try:
      n = indices[t[i]][idx]
    except:
      n = indices[t[i]][0]

    if n <= cur:
      min_i += (N - cur) + n
    else:
      if cur == -1:
        cur = 0
      min_i += (n - cur)
    cur = n
  except:
    print(-1)
    break
else:
  print(min_i + 1)

Submission status: Accepted

Solution code:
import sys

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

string = s
length = 1

for i in range(len(t)):
	if s.find(t[i])==-1:
		print(-1)
		sys.exit()
	if string.find(t[i])==-1:
		string = s
		length += 1
	string = string[string.find(t[i])+1 : ]
	
print(length*len(s)-len(string))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
alp=string.ascii_lowercase
d_al=dict([(i,j) for j,i in enumerate(alp)])

s=[d_al[i] for i in input()]
t=[d_al[i] for i in input()]
Ss=set(s)
St=set(t)
ns=len(s)
nt=len(t)
ss=s*2

g=[{} for _ in range(ns)]
pos=[-1]*26
for i in range(ns*2)[::-1]:
    for j in Ss:
        if i<ns:
            g[i][j]=pos[j]-i
    pos[ss[i]]=i

if len(St-Ss)!=0:
    ans=-1
else:
    cur=0
    cur+=g[-1][t[0]]-1
    for i in range(1,nt):
        cur+=g[cur%ns][t[i]]
    ans=cur+1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
alp=string.ascii_lowercase
d_al=dict([(i,j) for j,i in enumerate(alp)])

s=[d_al[i] for i in input()]
t=[d_al[i] for i in input()]
Ss=set(s)
St=set(t)
ns=len(s)
nt=len(t)
ss=s*2
#print(ss)

g=[{} for _ in range(ns)]
pos=[-1]*26
for i in range(ns*2)[::-1]:
    for j in Ss:
        if i<ns:
            g[i][j]=pos[j]-i
    pos[ss[i]]=i
#for i in range(len(g)):
#    print(g[i])

if len(St-Ss)!=0:
    ans=-1
else:
    cur=0
    cur+=g[-1][t[0]]-1
    #print(cur)
    for i in range(1,nt):
        #print(cur,s[cur%ns],'tg=',t[i],g[cur%ns][t[i]])
        cur+=g[cur%ns][t[i]]
    ans=cur+1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    t = S()
    ans = 0
    s_dict = defaultdict(list)
    for ix, c in enumerate(s):
        s_dict[c].append(ix)
    cur_ix = -1 
    for counter, c in enumerate(t):
        if s_dict.get(c) == None:
            print(-1)
            return
        char_ix_list = s_dict.get(c)
        # cur_ixより大きい値を見つける
        pos = bisect.bisect_right(char_ix_list, cur_ix)
        # cur_ixより大きい値がないとき、リセット
        if pos >= len(char_ix_list):
            ans += len(s)
            cur_ix = char_ix_list[0]
        # cur_ixより大きい値が見つかった時、cur_ixを更新
        else:
            cur_ix = s_dict.get(c)[pos]
        # if last, add cur_ix to answer
        if counter == len(t)-1:
            ans += (cur_ix + 1)
    print(ans)
main()

Submission status: Accepted

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

n = len(s)
ds = defaultdict(list)
for i in range(n*2):
    ds[s[i%n]].append(i)

ans = 0
x = -1
for i in range(len(t)):
    if t[i] not in ds:
        ans = -1
        break

    x_next = ds[t[i]][bisect_right(ds[t[i]], x)]
    ans += x_next - x
    x = x_next % n
    # print(ans, t[i])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from re import finditer
from bisect import bisect_right

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


    str_dict = defaultdict(list)



    for char in set(t):
        c_iter = finditer(char, s)
        flag = True
        for j in c_iter:
            flag = False
            str_dict[char] += [j.start() + 1]
        if flag:
            return '-1'


    ans = 0
    for i in t:
        remain = ans % len(s)
        array = str_dict[i]
        str_ind = bisect_right(array, remain)
        if str_ind != len(array):
            ans += array[str_ind] - remain
        else:
            ans += len(s) - remain + array[0]
    return ans


print(main())

Submission status: Accepted

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

ds = defaultdict(int)
for i in range(len(s)):
    ds[s[i]] += 1
dt = defaultdict(int)
for i in range(len(t)):
    dt[t[i]] += 1

possible = True
for ti in dt:
    if ti not in ds:
        possible = False
        break


if possible:
    n = len(s)
    pos = defaultdict(list)
    for i in range(n*2):
        pos[s[i%n]].append(i)

    edge = defaultdict(list)
    for c in pos:
        x = 0
        for i in range(n):
            if i >= pos[c][x]:
                x += 1
            edge[c].append(pos[c][x])

    # print(pos)
    # print(edge)
    ans = 0
    x = 0
    for i in range(n):
        if s[i] == t[0]:
            ans = i + 1
            x = i
            break

    # print(ans)
    for i in range(1, len(t)):
        ans += edge[t[i]][x%n] - x
        x = edge[t[i]][x%n] % n
        # print(ans, t[i])

else:
    ans = -1

print(ans)

Submission status: Accepted

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

d=defaultdict(list)

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

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

buf=-1
l=0
for i in range(lt):
    if not d[t[i]]:
        print(-1)
        sys.exit()
    idx=bisect.bisect_right(d[t[i]],buf)
    if idx>=len(d[t[i]]):
        buf=d[t[i]][0]
        l+=1
    else:
        buf=d[t[i]][idx]
print(l*ls+buf+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from bisect import bisect_left

S = input().rstrip()
T = input().rstrip()

LS = len(S)

index = defaultdict(list)

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

x = -1
for t in T:
    arr = index[t]
    if len(arr) == 0:
        x = -2
        break
    y = (x+1) % LS
    i = bisect_left(arr,y)
    if i < len(arr):
        next_x = (x+1) + arr[i] - y
    else:
        next_x = (x+1) + arr[0] - y + LS
    x = next_x

print(x + 1)

Submission status: Accepted

Solution code:
from bisect import bisect
S=input()
T=input()
c=[[] for _ in range(26)]
for i,s in enumerate(S):
    j=ord(s)-ord("a")
    c[j].append(i)
for t in set(T):
    if not c[ord(t)-ord("a")]:
        print(-1)
        exit()
rnd=0
k=-1
for t in T:
    ti=ord(t)-ord("a")
    i=bisect(c[ti],k)
    if i==len(c[ti]):
        k=c[ti][0]
        rnd+=1
    else:
        k=c[ti][i]
        
print(rnd*len(S)+k+1)

Submission status: Accepted

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

for i in range(len(t)):
  if not t[i] in s:
    print(-1)
    break
else:
  j = -1
  counter = 0
  for i in range(len(t)):
    if t[i] in s[j+1:]:
      j = s[j+1:].find(t[i]) + j + 1
    else:
      counter += 1
      j = s.find(t[i])
  print(counter * len(s) + j + 1)

Submission status: Accepted

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


idx = -1
count = 0
if set(t) <= set(s):
    for i in t:
        idx = s.find(i,idx + 1)
        if idx == -1:
            idx = s.find(i)
            count += 1
        rep = count * len(s)
    print(idx+1+rep)
else:
    print(-1)

Submission status: Accepted

Solution code:
import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

s = ns()
t = ns()

# 判定
ok = True
sset = set(list(s))
tset = set(list(t))
for ti in tset:
    if ti not in sset:
        ok = False

if not ok:
    print(-1)
else:
    n = len(s)
    nex = [[] for _ in range(26)]
    sdouble = s + s
    orda = ord("a")
    for i, si in enumerate(sdouble):
        nex[ord(si) - orda].append(i)

    bef = t[:1]
    cur = s.index(t[:1])
    ans = cur

    for ti in t[1:]:
        chridx = ord(ti) - orda
        dest = bisect_right(nex[chridx], cur)
        ans += (nex[chridx][dest] - cur)
        cur = ans % n

    print(ans+1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from bisect import bisect_right


def solve():
  ## input
  S = str(input())
  T = str(input())

  ## solve
  Sdict = defaultdict(lambda:list())
  for i,c in enumerate(S):
    Sdict[c].append(i+1)

  idx = 0
  Tidx = [0 for _ in range(len(T)+1)]
  for i,c in enumerate(T):
    if len(Sdict[c]) == 0:
      return -1
    else:
      pos = bisect_right(Sdict[c],idx)
      if pos < len(Sdict[c]):
        Tidx[i+1] = Sdict[c][pos]
      else:
        Tidx[i+1] = Sdict[c][0]
      idx = Tidx[i+1]

  ans = 0
  for i in range(1,len(Tidx)):
    if Tidx[i-1] < Tidx[i]:
      ans += Tidx[i]-Tidx[i-1]
    else:
      ans += len(S)-Tidx[i-1]+Tidx[i]
  return ans


ans = solve()
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
S = input()
T = input()
ds = {}
for i,s in enumerate(S) :
    if s not in ds :
        ds[s] = [i]
    else :
        ds[s].append(i)

ind = -1
cnt = 0

for t in T :
    if t not in ds :
        ans = -1
        break
else :
    for t in T :
        if ds[t][-1] <= ind :
            ind = ds[t][0]
            cnt += 1
        else :
            ind = ds[t][bisect_right(ds[t], ind)]
    ans = cnt * len(S) + ind + 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right as bisect
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[ord(s[k])-97] += [k+1]
    ans = 0
    now = 0
    for k in range(len(t)):
        a = ord(t[k]) - 97
        if len(A[a]) == 0:
            print(-1)
            exit(0)
        if A[a][-1] <= now:
            ans += len(s)
            now = A[a][0]
        else:
            now = A[a][bisect(A[a],now)]
    print(ans+now)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
 
idx = -1
count = 0
if set(t) <= set(s):
    for i in t:
        idx = s.find(i, idx+1)
        if idx == -1:
            idx = s.find(i)
            count += 1
    pdc = count * len(s)
    print((idx + 1) + pdc)
else:
    print(-1)

Submission status: Accepted

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

    char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
    for i, ch in enumerate(S):
        char_appear[ch].append(i)

    # editorial における二分探索を使うやり方
    p = -1  # 文字 t は S' の p (mod |S|) 番目に現れた
    loop = 0
    for t in T:
        if not char_appear[t]:
            return -1  # 文字tが存在しなかった
        idx = bisect(char_appear[t], p)
        # idx がリストの末尾を指す場合、次のSを指しているということ
        loop += 1 if idx == len(char_appear[t]) else 0
        p = char_appear[t][idx % len(char_appear[t])]
    return loop * len(S) + p + 1

print(e_strings_of_inpurity())

Submission status: Accepted

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

    char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
    for i, ch in enumerate(S):
        char_appear[ch].append(i)

    # editorial における二分探索を使うやり方
    p = -1  # 文字 t は S' の p (mod |S|) 番目に現れた
    loop = 0
    for t in T:
        if not char_appear[t]:
            return -1  # 文字tが存在しなかった
        idx = bisect(char_appear[t], p)
        if idx == len(char_appear[t]):
            loop += 1  # リストの右端を指したということは、次のSを指すことになる
            p = char_appear[t][0]
        else:
            p = char_appear[t][idx]
    return loop * len(S) + p + 1

print(e_strings_of_inpurity())

Submission status: Accepted

Solution code:
from bisect import bisect_left

ALPHABET = "abcdefghijklmnopqrstuvwxyz"


def main(s, t):
    positions = {char: [] for char in ALPHABET}
    for i, char in enumerate(s):
        positions[char].append(i)

    current = 0
    answer = 0
    for char in t:
        pos_num = len(positions[char])
        if pos_num < 1:
            return -1
        idx = bisect_left(positions[char], current)
        if idx < pos_num:
            current = positions[char][idx] + 1
        else:
            answer += len(s)
            idx = bisect_left(positions[char], 0)
            current = positions[char][idx] + 1

    answer += current
    return answer


s = input()
t = input()
print(main(s, t))

Submission status: Accepted

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

idx = -1
count = 0
if set(t) <= set(s):
    for i in t:
        idx = s.find(i, idx+1)
        if idx == -1:
            idx = s.find(i)
            count += 1
    pdc = count * len(s)
    print((idx + 1) + pdc)
else:
    print(-1)

Submission status: Accepted

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

idx = -1
count = 0

if set(t) <= set(s):
    for i in t:
        idx = s.find(i, idx+1)
        if idx == -1:
            idx = s.find(i)
            count += 1
    pdc = count * len(s)
    total_idx = (idx + 1) + pdc 
    print(total_idx)
else:
    print(-1)

Submission status: Accepted

Solution code:
import bisect

NUM_LETTER = 26

def solve():
    s = list(raw_input())
    t = list(raw_input())
    Ns = len(s)
    # Create charDict
    charDict = [[] for i in range(NUM_LETTER)]
    for i in range(Ns):
        charDict[ord(s[i]) - ord('a')].append(i)
    # print charDict
    # Search
    ret = 0
    pk_1 = -1
    for i in range(len(t)):
        hashCharDict = ord(t[i]) - ord('a')
        # print "hashCharDict: " + str(hashCharDict)
        if len(charDict[hashCharDict]) == 0:
            ret = -1
            break
        else:
            ind = bisect.bisect(charDict[hashCharDict], pk_1)
            if ind == len(charDict[hashCharDict]):
                ret += Ns - pk_1
                pk_1 = charDict[hashCharDict][0]
                ret += pk_1
            else:
                ret += charDict[hashCharDict][ind] - pk_1
                pk_1 = charDict[hashCharDict][ind]
        # print "ret: " + str(ret)
    print ret

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    s = input().splitlines()[0]
    t = input().splitlines()[0]

    Slen = len(s)

    LookupTable = [[] for i in range(26)]
    for i, c in enumerate(s):
        v = ord(c) - ord('a')
        LookupTable[v].append(i)
    for i in range(26):
        LookupTable[i].append(-1)
        
    IndexTable = [0 for i in range(26)]
    NextTable = []
    for i, c in enumerate(s):
        v = ord(c) - ord('a')
        NextTable.append( [LookupTable[k][IndexTable[k]] for k in range(26)] )
        IndexTable[v] += 1
        if LookupTable[v][IndexTable[v]] < 0:
            IndexTable[v] = 0

    Index = 0
    Loop = 0
    for i, c in enumerate(t):
        v = ord(c) - ord('a')
        if NextTable[Index][v] < Index:
            Loop += 1
        Index = NextTable[Index][v]
        if Index < 0:
            print(-1)
            return
        Index += 1
        if Index >= Slen:
            Index = 0
            Loop += 1

    print(Loop*Slen+Index)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

if not set(t) <= set(s):
  print(-1)
  exit()
  
result = 0
now_i = 0
for c in t:
  #print(c, now_i, result)
  if not c in s[now_i:]: # リセット
    result += len(s)-now_i
    now_i = 0
  di = s[now_i:].index(c)
  di += 1
  result += di
  now_i = (now_i + di) % len(s)
print(result)

Submission status: Accepted

Solution code:
import bisect

def ctoi(char):
  return ord(char)-97

s=input()
ls=len(s)
t=input()
lt=len(t)
pos=[[] for _ in range(26)]
for i in range(ls):
  val=ctoi(s[i])
  pos[val].append(i)
larr=[0]*26
for i in range(26):
  larr[i]=len(pos[i])
pos2=[]
cnt=[0]*26
flag=True
num=-1
for i in range(lt):
  val=ctoi(t[i])
  if larr[val]==0:
    flag=False
    break
  tmp=bisect.bisect_right(pos[val],num)
  if tmp==larr[val]:
    num=pos[val][0]
  else:
    num=pos[val][tmp]
  pos2.append(num)
if flag==False:
  print(-1)
else:
  loop=0
  tmp=pos2[0]
  for i in range(1,lt):
    if pos2[i]<=tmp:
      loop+=1
    tmp=pos2[i]
  ans=loop*ls+(pos2[-1]+1)
  print(ans)

Submission status: Accepted

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

alphabet = 'abcdefghijklmnopqrstuvwxyz'
char = {c: [] for c in alphabet}
for i, c in enumerate(s):
    char[c].append(i)

if len(char[t[0]]) == 0:
    print(-1)
    exit()

result = char[t[0]][0]

for c in t[1:]:
    if len(char[c]) == 0:
        print(-1)
        exit()
    idx = bisect(char[c], result % len(s))
    result = result - result % len(s)
    try:
        result += char[c][idx]
    except IndexError:
        result += len(s) + char[c][0]

print(result+1)

Submission status: Accepted

Solution code:
import bisect

def main():
    s = input()
    t = input()
    sletters = [0]*26
    for i in range(len(s)):
        x = ord(s[i])-ord('a')
        if sletters[x] == 0:
            sletters[x] = [i]
        else:
            sletters[x].append(i)

    ans = 0
    curr_index = -1
    for i in t:
        x = ord(i)-ord('a')
        if sletters[x] == 0:
            print(-1)
            return
        index = bisect.bisect(sletters[x],curr_index)
        #print(sletters[x],i,curr_index,index)
        if index == len(sletters[x]):
            ans += len(s)-curr_index
            curr_index = sletters[x][0]
            ans += curr_index
        else:
            ans += sletters[x][index]-curr_index
            curr_index = sletters[x][index]
        

    print(ans)


main()

Submission status: Accepted

Solution code:
s = input()
t = input()
c = [[] for _ in range(26)]
total = 0
for i in range(len(s)):
    c[ord(s[i])-ord('a')].append(i)
idex = 0
run = -1
while(idex<len(t)):
    need = ord(t[idex])-ord('a')
    if len(c[need])==0:
        print(-1)
        exit()
    else:
        l = 0
        r = len(c[need])-1
        while(l<r):
            next = (l+r)//2
            if (c[need][next]> run):
                r=next
            else:
                l=next+1
        if c[need][r]>run:
            total+= c[need][r]-run
            run = c[need][r]

        else:
            total+=len(s)-1-run
            total+=c[need][0]+1
            run=c[need][0]
    idex+=1
print(total)

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

s = stdin.readline().rstrip()
t = stdin.readline().rstrip()

ss = s+s
alpos = []

for i in range(26):
    alpos.append([])

for i in range(len(ss)):
   alpos[ord(ss[i])-ord('a')].append(i)

pos = -1
mpos= -1
for i in range(len(t)):
    tn = ord(t[i])-ord('a')
    if ( len(alpos[tn]) == 0 ):
        pos = -2
        break
    bpos = bisect.bisect_left(alpos[tn], mpos+1)
    pos += alpos[tn][bpos]-mpos
    mpos = pos%len(s)

print(pos+1)

Submission status: Accepted

Solution code:
s = input()
ns = len(s)
x = {}
for i in range(len(s)):
    if s[i] in x:
        x[s[i]] += [i]
    else:
        x[s[i]] = [i]
t = input()
i = len(s)-1
count = 0
import bisect
for j in range(len(t)):
    if t[j] in x:
        ni = bisect.bisect_right(x[t[j]],i)
        if ni == len(x[t[j]]):
            i = x[t[j]][0]
            count += 1
        else:
            i = x[t[j]][ni]
    else:
        print(-1)
        exit()
    
print(len(s)*(count-1)+i+1)

Submission status: Accepted

Solution code:
S = [ord(s) - 97 for s in input()]
T = [ord(t) - 97 for t in input()]
SS = S + S
ls = len(S)

indexes = [[] for _ in range(26)]
for i, s in enumerate(SS):
    indexes[s].append(i)
m = [[-1] * 26 for _ in range(2 * ls)]
for s in range(26):
    inds = [0] + indexes[s]
    for r in range(1, len(inds)):
        for i in range(inds[r-1], inds[r]):
            m[i][s] = inds[r] - i

ans = 0
i = ls - 1
for t in T:
    cnt = m[i][t]
    if cnt == -1:
        print(-1)
        exit()
    ans += cnt
    i = (i + cnt) % ls
print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
t_long = len(t)
position = [0] * t_long
rep = 0

if set(t) <= set(s):
    position[0] = s.find(t[0])
    for i in range(1, t_long):
        if s.find(t[i], position[i - 1] + 1) > -1:
            position[i] = s.find(t[i], position[i - 1] + 1)
        else:
            position[i] = s.find(t[i])
    for k in range(t_long - 1):
        if position[k + 1] <= position[k]:
            rep += 1
    print(rep * len(s) + position[t_long - 1] + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import collections, bisect
s = tuple(input())
t = tuple(input())
ls = len(s)
idx = collections.defaultdict(list)
dct = collections.defaultdict(list)
ln = -1
loop = 0
for i, v in enumerate(s):
    idx[v].append(i)
for i in t:
    t_idx = idx[i]
    if t_idx:
        bn = bisect.bisect_left(t_idx, ln + 1)
        if bn >= len(t_idx):
            ln = t_idx[0]
            loop += 1
        else:
            ln = t_idx[bn]
    else:
        print(-1)
        exit()
print(ls * loop + ln + 1)

Submission status: Accepted

Solution code:
s = input()
t = input()
max = 10**100
now = t[0]
cnt1 = 0
cnt2 = 0

while True:
	temp = s[:]
	if cnt2 == len(t):
		print(cnt1)
		break
	if max == 0:
		print("-1")
		break
	while True:
		num = temp.find(now)
		if num != -1:
			cnt2+=1
			cnt1+=num+1
			#print("num={0}, temp={1}, cnt1={2}, cnt2={3}".format(num, temp, cnt1, cnt2))
			if cnt2 < len(t):
				now = t[cnt2]
			else:
				break
			temp = temp[num+1:]
			continue
		else:
			if temp == s:
				print("-1")
				exit(0)
			else:
				cnt1+=len(temp)
			break
	max-=1

Submission status: Accepted

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

Spos = [[] for _ in range(26) ]
ord_a = ord('a')
for i in range(len(S)):
    Spos[ord(S[i])-ord_a].append(i)

for t in set(T):
    if len(Spos[ord(t)-ord_a]) == 0:
        print(-1)
        exit()

copy = 0
pos = -1
for t in T:
    array = Spos[ord(t)-ord_a]
    p = bisect.bisect_right(array, pos)
    if p == len(array):
        copy += 1
        pos = array[0]
    else:
        pos = array[p]

ans = copy * len(S) + (pos + 1)
print(ans)