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: Runtime Error

Solution code:
import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l = [G.copy()] + l
  G[s[i]] = i
stG = G.copy()

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind == len(t):
        break   
    if ind == len(t):
      break        
    cnt += 1

###    
if cnt != -1:      
  print(cnt*len(s)+stG[t[-1]]+1)
else:
  print(cnt)

Submission status: Runtime Error

Solution code:
import string
s = input()
t = input()
l = []
alp = string.ascii_lowercase
G = dict([(alp[i],-1) for i in range(len(alp))])
for i in range(len(s)-1,-1,-1):
  l = [G.copy()] + l
  G[s[i]] = i
stG = G

cnt = 0
ind = 0
while ind < len(t): 
  if stG[t[ind]] == -1:
    cnt = -1
    break
  else:
    lind = stG[t[ind]]
    ind += 1
    while l[lind][t[ind]] != -1:   
      lind = l[lind][t[ind]]
      ind += 1
      if ind == len(t):
        break   
    if ind == len(t):
      break        
    cnt += 1

###    
if cnt != -1:      
  print(cnt*len(s)+stG[t[-1]]+1)
else:
  print(cnt)

Submission status: Runtime Error

Solution code:
import copy
from collections import deque
sima = [list(input()) for i in range(10)]
riku = 0
ikisaki = [(1,0),(-1,0),(0,1),(0,-1)]

for i in range(10):
    for j in range(10):
        if sima[i][j] == "o":
            riku += 1

for i in range(10):
    for j in range(10):
        if sima[i][j] == "o":
            continue
        cou = 0
        karisima = copy.deepcopy(sima)
        karisima[i][j] = "o"
        d = deque()
        d.append((i,j))
        tansaku = [[True for p in range(10)] for q in range(10)]
        while d:
            y , x = d.popleft()
            tansaku[y][x] = False
            cou += 1
            for ney , nex in ikisaki:
                if 0 <= x + nex <= 9 and 0 <= y + ney <= 9:
                    if tansaku[y+ney][x+nex] and karisima[y+ney][x+nex] == "o":
                        d.append((y+ney,x+nex))
        if cou == riku + 1:
            print("YES")
            exit()
print("NO")

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ss = s+s
NEXT = [[-1]*(len(s)+1) for _ in range(26)]
cur = [-1]*26
for i in range(len(ss)):
    char = ord(ss[i])-97
    if cur[char] < len(s):
        for j in range(cur[char],min(i,len(s))):
            NEXT[char][j+1] = i
            cur[char] = i
ans = 0
tmp = -1
for i in range(len(t)):
    char = ord(t[i])-97
    if NEXT[char][tmp+1] == -1:
        print(-1)
        exit()
    ans += NEXT[char][tmp+1]-tmp
    tmp = NEXT[char][tmp+1]
    if tmp >= len(s)+1:
        tmp -= len(s)
print(ans)

Submission status: Runtime Error

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
t = ins()
oa = ord('a')
ls = len(s)
nxt = [[-1]*26 for i in range(ls)]
nx = [-1]*26
for i in range(2*ls-1,-1,-1):
    c = ord(s[i%ls])-oa
    for j in range(26):
        if i<ls and nx[j]>=0:
            nxt[i][j] = nx[j]-i
    nx[c] = i
if DBG:
    for i in range(ls):
        printn(f"{i} ")
        print(nxt[i])
cur = 0
for i in range(len(t)):
    c = ord(t[i])-oa
    nx = nxt[cur%ls][c]
    if nx<0:
        print(-1)
        exit()
    cur += nx
print(cur+1)

Submission status: Runtime Error

Solution code:
#138-e
from collections import defaultdict
import bisect

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

ans=0
pos=-1

d = defaultdict(list)
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i)
        
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i+n)
        
for v in t:
    l = d[v]
    ind = bisect.bisect_right(l, pos)
    ans += l[ind]-pos
    if l:
        if l[ind]<n:
            pos = l[ind]
        else:
            pos = l[ind] - n
    else:
        ans = -1
        break
        
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
s = list(input())
t = list(input())
n = len(s)
m = len(t)
alphabet = [[] for _ in range(26)]
for i in range(n):
  alphabet[ord(s[i])-ord('a')+1] += [i] 

loop = 0
pre = -1
for i in range(m):
  c = ord(t[i]) - ord('a') + 1
  if len(alphabet[c]) == 0:
    print(-1)
    exit()
  idx = bisect.bisect_left(alphabet[c], pre+1)
  if idx == len(alphabet[c]):
    loop += 1
    pre = alphabet[c][0]
  else:
    pre = alphabet[c][idx]

print(pre + loop * n + 1)

Submission status: Runtime Error

Solution code:
import bisect
s = list(input())
t = list(input())
n = len(s)
m = len(t)
alphabet = [[] for _ in range(26)]
for i in range(n):
  alphabet[ord(s[i])-ord('a')+1] += [i] 

loop = 0
pre = -1
for i in range(m):
  c = ord(t[i]) - ord('a') + 1
  idx = bisect.bisect_left(alphabet[c], pre+1)
  if idx == len(alphabet[c]):
    loop += 1
    pre = alphabet[c][0]
  else:
    pre = alphabet[c][idx]

print(pre + loop * n + 1)

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

vector<int> E[26];
ll N,M;
map<int,vector<int>> m;
string s,t;
bool found = true;
ll ans = 0;


 
 
int main(){
    cin >> s >> t;
    N = s.size();
    M = t.size();
    for(int i=0;i<N;i++){
        int a = s[i] -'a';
        E[a].push_back(i);
    }
    ll j=-1;
    for(int i=0;i<M;i++){
        int b = t[i] -'a';
        vector<int> e = E[b];
        
        if(e.empty()){
            found = false;
            break;
        }
        if(e.size()>N){
            break;
        }
        decltype(e)::iterator it = upper_bound(e.begin(), e.end(), j);
        ll k = *upper_bound(e.begin(),e.end(),j);
        if(it == e.end()){
            k = e[0];
            ans+=1;
        }
        j = k;
    }
    ans = ans*N + j+1;
    if(found){
      cout << ans << endl;
    }else{
        cout << -1 << endl;
    }
    
}

Submission status: Runtime Error

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    t = input()

    # 構成不可能な場合
    set_s = set(s)
    for char_t in t:
        if char_t not in set_s:
            print(-1)
            exit()

    # 構成可能な場合    
    # 前処理 O(n)
    s_table = [[] for _ in range(ord('z') - ord('a'))]
    for i, s_char in enumerate(s):
        s_table[ord(s_char) - ord('a')].append(i)
    # print(s_table)
    # O(nlgn)
    loop_count = 0
    prev = -1
    for t_char in t:
        candidate = s_table[ord(t_char) - ord('a')]
        j = bisect_left(candidate, prev+1)    # prev より大きくないとだめ
        if j == len(candidate):
            loop_count += 1
            prev = candidate[0]
        else:
            prev = candidate[j]        
    print(prev + loop_count * len(s) + 1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    t = input()

    # 構成不可能な場合
    set_s = set(s)
    for char_t in t:
        if char_t not in set_s:
            print(-1)
            break
    # 構成可能な場合
    else:    
        # 前処理 O(n)
        s_table = [[] for _ in range(ord('z') - ord('a'))]
        for i, s_char in enumerate(s):
            s_table[ord(s_char) - ord('a')].append(i)
        # print(s_table)
        # O(nlgn)
        loop_count = 0
        prev = -1
        for t_char in t:
            candidate = s_table[ord(t_char) - ord('a')]
            j = bisect_left(candidate, prev)
            if j == len(candidate):
                loop_count += 1
                prev = candidate[0]
            else:
                prev = candidate[j]        
        print(prev + loop_count * len(s) + 1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

    #ABC138-E Strings of Impurity
"""
sの好きなだけのループに対する部分文字列tを求める
tにあってsにない文字がある時点でno
そうでないならば必ず達成可能で、
tに対してループを回し(i)、
sのj文字目に関して、それより後に初めて出てくるt[i+1]の場所をindexで返し,i+=1,j=そのindex
にする。
そのようなindexがないならば、j=0とし、またはじめから回す。
"""
import sys
import bisect
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

s = readline().rstrip().decode('utf-8')
t = readline().rstrip().decode('utf-8')
s_s = set(list(s))
t_s = set(list(t))
flag = 1 if s_s & t_s == t_s else 0

if not flag:
    raise Exception
"""    print(-1)
    exit()
"""
#2進数で、
lst1 = [[] for _ in range(26)]
kijun = ord("a")
for idx,i in enumerate(s):
    lst1[ord(i)-kijun].append(idx)

i = 0
roop = 0
count = 0
while True:
    if i >= len(t):
        print(roop*len(s)+count+1) #countは0-indexedの為
        break
    now = ord(t[i])-kijun
    res = bisect.bisect_left(lst1[now],count)
    if res == len(lst1[now]):
        roop += 1
        count = 0
        res = bisect.bisect_left(lst1[now],count)
        count = lst1[now][res]
    else:
        count = lst1[now][res]
    i += 1

Submission status: Runtime Error

Solution code:
from collections import defaultdict
c = defaultdict(list)
s = input()
n = len(s)
for i, ch in enumerate(s):
    c[ch].append(i + 1)
cnt1 = 0
cnt2 = 0
judge = True
for ch in input():
    if not c[ch]:
        judge = False
        break
    if cnt2 >= c[ch][-1]:
        cnt2 = c[ch][0]
        cnt1 += 1
        continue
    l = 0
    r = len(c[ch])
    for i in range(len(c[ch])):
        ce = l + r // 2
        if cnt2 >= c[ch][ce]:
            l = ce + 1
        else:
            r = ce
        if l == r:
            cnt2 = c[ch][l]
if judge:
    print(n * cnt1 + cnt2)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
counter = 0
idx = -1
if set(t) <= set(s):
  for i in range(len(t)):
    idx = s.find(t[i],idx+1)
    if idx == -1:
      counter += 1
      idx = s.find(t[i],idx+1)
  print(counter * len(s) +idx +1)
elsse:
  print(-1)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    s = input()
    s = [ord(i) - ord("a") for i in s]
    N = len(s)
    t = input()
    t = [ord(i) - ord("a") for i in t]

    posit = {}
    for i in range(0, ord("z")-ord("a")+1):
        posit[i] = []

    for i, c in enumerate(s):
        posit[c].append(i)

    ans = 0
    cur = -1
    for src_target in t:
        if not posit[src_target]:
            return -1
        if posit[src_target][-1] <= cur: # 使い捨て処理
            ans += (N-cur)
            cur = 0
            #print("a", ans)
        idx = bisect_left(posit[src_target], cur+1) # 次のがあるindexを探す
        next = posit[src_target][idx]
        ans += next - cur
        cur = next
        #print(ans, src_target)

    return ans



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    s = input()
    s = [ord(i) - ord("a") for i in s]
    N = len(s)
    t = input()
    t = [ord(i) - ord("a") for i in t]

    posit = {}
    for i in range(0, ord("z")-ord("a")):
        posit[i] = []

    for i, c in enumerate(s):
        posit[c].append(i)

    ans = 0
    cur = -1
    for src_target in t:
        if not posit[src_target]:
            return -1
        if posit[src_target][-1] < cur: # 使い捨て処理
            ans += (N-cur)
            cur = 0
            #print("a", ans)
        idx = bisect_left(posit[src_target], cur) # 次のがあるindexを探す
        next = posit[src_target][idx]
        ans += next - cur
        cur = next
        #print(ans, src_target)

    return ans



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
s = input()
n = len(s)
l = [[]for i in range(26)]

for i, c in enumerate(s * 2):
    l[ord(c) - ord('a')].append(i)


from bisect import *

shukai = 0
now = 0

t = input()
for c in t:
    x = ord(c) - ord('a')
    if len(l[x]) == 0:
        print(-1)
        exit()
    i = bisect(l[x], now)
    now = l[x][i] + 1
    if now >= n:
        now -= n
        shukai += 1


print(shukai * n + now)

Submission status: Runtime Error

Solution code:
import bisect
from collections import defaultdict

S=list(input().strip())
T=list(input().strip())
L=len(S)

if set(T)>set(S):
  print(-1)
  exit()

d=defaultdict(list)
for i,s in enumerate(S):
  d[s].append(i)
start=-1
ans=0
for i in T:
  p=bisect.bisect_right(d[i],start)
  le=len(d[i])
  if p==le:
    ans+=(L-start-1)+(d[i][0]+1)
    start=d[i][0]    
  else:
    ans+=d[i][p]-start
    start=d[i][p]
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: UTF-8 -*-
import math
# f=open("test.txt")
# line=f.readline()
# lists=[]
# while line:
#     lists.append("".join(list(line)[:-1]))
#     line=f.readline()
# 
# f.close()
# 
# s=lists[0]
# t=lists[1]

s=input()
t=input()

alpha=list("abcdefghijklmnopqrstuvwxyz")

dic_s={alpha[i]:0 for i in range(26)}
dic_t={alpha[i]:0 for i in range(26)}

a={alpha[i]:[] for i in range(26)}
b={alpha[i]:[] for i in range(26)}


for i in range(len(s)-1):
    if dic_s[s[i]]==0:
        dic_s[s[i]]=+1
        a[s[i]].append(i+1)


for j in range(len(t)-1):
    if dic_t[t[j]]==0:
        dic_t[t[j]]=+1
        b[t[j]].append(j+1)

flag=True

for i in range(26):
    if dic_t[alpha[i]]>0 and dic_s[alpha[i]]==0:
        flag=False

place=[0,0]

def binary(now,string):
    left=a[string][0]
    right=a[string][-1]
    #sのなかでstringがあり得る最大の位置
    #左のインデックスと右のインデックスを決める
    #now=現在いるindex
    flag=True
    if now>right:
        place[0]=left
        place[1]+=1

    elif now<left:
        place[0]=left
    else:
        indexl=0
        indexr=dic_s[string]-1
        for _ in range(20):
            c=math.floor((indexl+indexr)/2)
            if a[string][c]<=now:
                indexl=c
                indexr=indexr
            elif a[string][c]>now:
                indexl=indexl
                indexr=c
        place[0]=a[string][indexr]

if flag:
    #文字を構成できる場合
    for i in range(len(t)):
        string=t[i]
        now=place[0]
        binary(now,string)

    print(place[0]+place[1]*len(s))

else:
    #構成できない場合
    print(-1)

Submission status: Runtime Error

Solution code:
import bisect
s = input()
t = input()
sub = s+s
dp = []
for i in range(len(s)):
    d = [10**15]*26
    dp.append(d)
index = [[] for i in range(26)]
for i in range(len(sub)):
    index[ord(sub[i])-97].append(i)
for i in range(len(s)):
    cur = s[i]
    for j in range(26):
        if len(index[j]) != 0:
            k = bisect.bisect_left(index[j], i)
            dp[i][j] = index[j][k]-i
ans = dp[0][ord(t[0])-97]+1
next = dp[0][ord(t[0])-97]
flag = True
for i in range(1,len(t)):
    cur = next
    if dp[cur][ord(t[i])-97] == 10**15:
        flag = False
        break
    else:
        ans += dp[cur][ord(t[i])-97]
        if cur + dp[cur][ord(t[i])-97] >= len(s):
            next = cur + dp[cur][ord(t[i])-97] - len(s)
        else:
            next = cur + dp[cur][ord(t[i])-97]
if flag:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  for i in range(n):
    if len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
  cnt=0
  for i in range(n-1):
    l=len(lindex[ord(t[i+1])-97])
    idx=bisect_right(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0])
    if l==idx:
      cnt+=1
      inde=lindex[ord(t[i+1])-97][0]+1
    else:
      inde=lindex[ord(t[i+1])-97][idx]+1
  return print(m*cnt+inde)
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  for i in range(n):
    if len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
  cnt=0
  for i in range(n-1):
    l=len(lindex[ord(t[i+1])-97])
    if l==bisect_right(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0]):
      cnt+=1
    if i==n-2:
      if l>bisect_right(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0]):
        k=lindex[ord(t[n-1])-97][0]
      else:
        k=bisect_right(lindex[ord(t[n-1])-97],lindex[ord(t[i])-97][0])
  return print(m*cnt+k+1)
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  for i in range(n):
    if len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
  cnt=0
  for i in range(n-1):
    if l==bisect_left(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0]):
      cnt+=1
  k=lindex[ord(t[n-1])-97][0]
  return print(m*cnt+k+1)
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  cnt=0
  for i in range(n-1):
    l=len(lindex[ord(t[i+1])-97])
    if l==0 or len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
    if l==bisect_left(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0]):
      cnt+=1
  k=lindex[ord(t[-1])-97][0]
  return print(m*cnt+k+1)
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  cnt=0
  for i in range(n-1):
    l=len(lindex[ord(t[i+1])-97])
    if l==0:
      print(-1)
      exit()
    if l==bisect_left(lindex[ord(t[i+1])-97],lindex[ord(t[i])-97][0]):
      cnt+=1
  k=lindex[ord(t[-1])-97][0]
  return print(m*cnt+k+1)
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import bisect

S = input()
T = input()

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

ans = 0
i = 0

for t in T:
    if not d[t]:
        print(-1)
        exit()

    if i > d[t][-1]:
        ans += len(S)
        i = 0
    pos = bisect.bisect_right(d[t], i)
    i = d[t][pos]

ans += i
print(ans)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	t = input()
	if len(set(s)&set(t)) != len(set(t)):
		print(-1)
		exit()

	dic = defaultdict(int)
	for i, char in enumerate(s):
		if not dic[char]:
			dic[char] = i+1

	t_num = list(t)
	for i in range(len(t)):
		t_num[i] = dic[t[i]]
	
	loop = 0
	tmp = t_num[0]
	t_num = t_num[1:]
	for n in t_num:
		if n <= tmp:
			loop += 1
		tmp = n

	print(len(s)*loop+t_num[-1])

if __name__ == '__main__':
	main()