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:
def is_substring(s_char_map, t):
    for char in t:
        if char not in s_char_map:
            return False
    return True


def get_impurity(s, t):
    s_char_map = {}
    
    s_len = len(s)
    for char_idx in range(s_len):
        if s[char_idx] not in s_char_map:
            s_char_map[s[char_idx]] = [char_idx + 1]
        else:
            s_char_map[s[char_idx]].append(char_idx + 1)
    last_idx = -1
    s_length = len(s)
    full_length = 0
    
    if not is_substring(s_char_map, t):
        return -1
    
    for char in t:
        if s_char_map[char][-1] >= last_idx:
            last_idx = list(filter(lambda i: i > last_idx, s_char_map[char]))[0]
            full_length += last_idx - (full_length % s_length)
        else:
            last_idx = s_char_map[char][0]
            full_length += (s_length - (full_length % s_length)) + last_idx
    return full_length

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

Submission status: Runtime Error

Solution code:
def get_impurity(s, t):
    s_char_map = {}
    s_len = len(s)
    
    for char_idx in range(s_len):
        if s[char_idx] not in s_char_map:
            s_char_map[s[char_idx]] = [char_idx + 1]
        else:
            s_char_map[s[char_idx]].append(char_idx + 1)
    last_idx = -1
    s_length = len(s)
    full_length = 0
    
    for char in t:
        if char not in s_char_map:
            return -1
            break
        elif s_char_map[char][-1] >= last_idx:
            last_idx = list(filter(lambda i: i > last_idx, s_char_map[char]))[0]
            full_length += last_idx - (full_length % s_length)
        else:
            last_idx = s_char_map[char][0]
            full_length += (s_length - (full_length % s_length)) + last_idx
    return full_length

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

Submission status: Runtime Error

Solution code:
from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)

a=len(s)*len(t)
maxcount=len(s)
for i in range(100):
    if maxcount<a
        maxcount**=10
    else:
        break


for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=1
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]
    else:
        prei=dic[t[i]][0]
        count+=N
    if i==len(t)-1:
        count+=prei



if count<=maxcount:
    print(count)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import itertools

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        next_num = next(itertools.ifilter(lambda x: x >= temp_num, obj[char]), None)
        if next_num == None:
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = next_num

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

Submission status: Runtime Error

Solution code:
import bisect


def bisect_search(f, val=0, l=0, r=10**6):

    #is_increase=(f(r)-f(l))>=0

    eps = 10**(-5)
    while True:

        c = (l+r)//2
        print(l, c, r)
        input()
        if f(c) == val and f(c-1) != val:
            return c
        #if f(c)-val < eps:
        #    return c

        if f(c) > val:
            r = c

        else:
            l = c

        if l == r:
            return False



def next(ch,k):
    global N,dcs
    k_=k%N
    #print(ch,ch_,k)
    #print(dcs[ch][ch_]+1)
    #print(dcs[ch])
    #print(dcs[ch][ch_]+1)
    #print(N)
    val = dcs[ch][k_-1]+1
    if k_==0:
        val=1

    A=bisect.bisect_left(dcs[ch],val,k_,min(k_+N,2*N-1))
    B = N*((k//N))
    #print(A,B,k//N,k,N)

    return A+B#+A//N


import numpy as np

s=input()
t=input()

td=list(set(t))

N=len(s)
d={}

import sys

R = set(list(s))
L = set(list(t))

if not(L <= R):
    print(-1)
    sys.exit(2)

for std in td:
    d[std] =[0]*(2*N)



for i in range(len(s)*2):
    #nd[s[i]]

    for std in td:            
        if s[i%N]==std:
            d[std][i]=1



dcs={}
for std in td:
    dcs[std]=np.cumsum(d[std])


last=-1
for ts in t:
    #print(last)
    last=next(ts,last+1)


print(last+1)


#print(dcs)

Submission status: Runtime Error

Solution code:
import bisect


def bisect_search(f, val=0, l=0, r=10**6):

    #is_increase=(f(r)-f(l))>=0

    eps = 10**(-5)
    while True:

        c = (l+r)//2
        print(l, c, r)
        input()
        if f(c) == val and f(c-1) != val:
            return c
        #if f(c)-val < eps:
        #    return c

        if f(c) > val:
            r = c

        else:
            l = c

        if l == r:
            return False



def next(ch,k):
    global N,dcs
    k_=k%N
    #print(ch,ch_,k)
    #print(dcs[ch][ch_]+1)
    #print(dcs[ch])
    #print(dcs[ch][ch_]+1)
    #print(N)
    val = dcs[ch][k_-1]+1
    if k_==0:
        val=1

    A=bisect.bisect_left(dcs[ch],val,k_,k_+N)
    B = N*((k//N))
    #print(A,B,k//N,k,N)

    return A+B#+A//N


import numpy as np

s=input()
t=input()

td=list(set(t))

N=len(s)
d={}

import sys

R = set(list(s))
L = set(list(t))

if not(L <= R):
    print(-1)
    sys.exit(2)

for std in td:
    d[std] =[0]*(2*N)



for i in range(len(s)*2):
    #nd[s[i]]

    for std in td:            
        if s[i%N]==std:
            d[std][i]=1



dcs={}
for std in td:
    dcs[std]=np.cumsum(d[std])


last=-1
for ts in t:
    #print(last)
    last=next(ts,last+1)


print(last+1)


#print(dcs)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
T = sr()
len_S = len(S)
indexes_S = defaultdict(list)
for i, s in enumerate(S):
    indexes_S[s].append(i)

x = -1 # 今いるところ、次はx+1から探索
for t in T:
    if indexes_S[t] == 0:
        print(-1); exit()
    arr = indexes_S[t]
    y = (x+1) % len_S
    next_i = bisect.bisect_left(arr, y) # tの同じ文字がある次のindex
    if next_i < len(arr):
        x = (x+1) + arr[next_i] - y
    else:
        x = (x+1) + arr[0] + len_S - y # 1周して次のarr

print(x+1)

Submission status: Runtime Error

Solution code:
import bisect


def next(ch,k):
    global N,dcs
    ch_=k%N
    #print(ch,ch_,k)
    #print(dcs[ch][ch_]+1)
    #print(dcs[ch])
    #print(dcs[ch][ch_]+1)
    #print(N)
    A=bisect.bisect_left(dcs[ch],dcs[ch][max(0,ch_-1)]+1,ch_,2*N-1)
    B = N*((k//N))
    #print(A,B,k//N,k,N)

    return A+B#+A//N


import numpy as np

s=input()
t=input()

td=list(set(t))

N=len(s)
d={}

import sys

R = set(list(s))
L = set(list(t))

if not(L <= R):
    print(-1)
    sys.exit(2)

for std in td:
    d[std] =[]


for i in range(len(s)*2+1):
    #nd[s[i]]

    for std in td:            
        if s[i%N]==std:
            d[std].append(1)
        else:
            d[std].append(0)


dcs={}
for std in td:
    dcs[std]=np.cumsum(d[std])


last=-1
for ts in t:
    #print(last)
    last=next(ts,last+1)


print(last+1)

Submission status: Runtime Error

Solution code:
// {{{ by unolight
#include <bits/stdc++.h>
#include <unistd.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define RALL(x) rbegin(x),rend(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef pair<int,int> PII;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;

template<class T> void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( int64_t &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }
void R() {}
template<class T, class... U> void R( T& head, U&... tail ) { _R(head); R(tail...); }

template<class T> void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
void _W( const int64_t &x ) { printf("%" PRId64,x); }
void _W( const double &x ) { printf("%.16f\n",x); }
void _W( const char &x ) { putchar(x); }
void _W( const char *x ) { printf("%s",x); }
template<class T> void _W( const vector<T> &x ) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W( const T& head, const U&... tail ) { _W(head); putchar(sizeof...(tail)?' ':'\n'); W(tail...); }

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

#ifdef UNO
template<class T> void _dump(const char *s, T &&head) { cerr << s << "=" << head << endl; }
template<class T, class... Args> void _dump(const char *s, T &&head, Args &&... tail) {
    for (int c = 0; *s != ',' || c != 0; cerr << *s++) {
        if (*s == '(' || *s == '[' || *s == '{') c++;
        if (*s == ')' || *s == ']' || *s == '}') c--;
    }
    cerr << "=" << head << ", ";
    _dump(s + 1, tail...);
}
#define dump(...) do { fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); _dump(#__VA_ARGS__, __VA_ARGS__); } while (0)

template<class Iter> ostream &_out(ostream &s, Iter b, Iter e) {
    s << "[";
    for (auto it = b; it != e; it++) s << (it == b ? "" : " ") << *it;
    return s << "]";
}

template<class A, class B> ostream &operator<<(ostream &s, const pair<A, B> &p) { return s << "(" << p.first << "," << p.second << ")"; }
template<class T> ostream &operator<<(ostream &s, const vector<T> &c) { return _out(s, ALL(c)); }
template<class T, size_t N> ostream &operator<<(ostream &s, const array<T, N> &c) { return _out(s, ALL(c)); }
template<class T> ostream &operator<<(ostream &s, const set<T> &c) { return _out(s, ALL(c)); }
template<class A, class B> ostream &operator<<(ostream &s, const map<A, B> &c) { return _out(s, ALL(c)); }
#else
#define dump(...)
#endif
// }}}

const int MAX_N=1e5+10;
int n, m, nxt[MAX_N*2][26];

int main() {
    string s, t;
    R(s, t);
    n = s.length(); m = t.length();
    REP(i, 26) nxt[2*n][i]=2*n;
    for(int i=2*n-1; i>=0; i--) {
        REP(j, 26) nxt[i][j]=nxt[i+1][j];
        nxt[i][s[i%n]-'a']=i+1;
    }

    LL ans=0;
    for(int c:t) {
        c-='a';
        LL x=ans%n;
        if(nxt[x][c]==2*n) {
            W(-1);
            return 0;
        }
        ans += nxt[x][c]-x;
    }
    W(ans);
    return 0;
}

Submission status: Runtime Error

Solution code:
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    m = 0
    j = 0
    for i in t:
        ind = bisect.bisect_left(d[i], j)
        m += d[i][ind] - j + 1
        if d[i][ind] > n:
            j = d[i][ind] - n + 1
        else:
            j = d[i][ind] + 1
    return m
print(main())

Submission status: Runtime Error

Solution code:
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    m = 1
    j = 0
    for i in t:
        ind = bisect.bisect_right(d[i], j)
        m += d[i][ind] - j
        if d[i][ind] > n:
            j = d[i][ind] - n
        else:
            j = d[i][ind]
    return m
print(main())

Submission status: Runtime Error

Solution code:
import bisect
INF = 10 ** 10
s = input()
t = input()
moji = [[] for _ in range(26)]

for i, m in enumerate(s):
    moji[ord(m) - ord("a")].append(i)

for i in range(26):
    moji[i].sort()

moji_o = [0 for _ in range(len(t))]

cnt = 0
ans = 1
# print(moji)
for i, m in enumerate(t):
    if len(moji[ord(m) - ord("a")]) == 0:
        ans = -1
        break
    if i == 0:
        moji_o[i] = moji[ord(m) - ord("a")][0]
    else:
        if moji_o[i - 1] > moji[ord(m) - ord("a")][-1]:
            moji_o[i] =  moji[ord(m) - ord("a")][0]
        else:
            tmp = bisect.bisect_right(moji[ord(m) - ord("a")], moji_o[i - 1])
            if tmp == 0:
                moji_o[i] = moji[ord(m) - ord("a")][0]
            else:
                moji_o[i] = moji[ord(m) - ord("a")][tmp]
# print(moji_o)
for i in range(1, len(moji_o)):
    if ans == -1:
        break
    if moji_o[i - 1] >= moji_o[i]:
        cnt += 1

if ans == -1:
    print(-1)
else:
    print(cnt * len(s) + moji_o[-1] + 1)

Submission status: Runtime Error

Solution code:
import bisect
INF = 10 ** 10
s = input()
t = input()
moji = [[] for _ in range(26)]

for i, m in enumerate(s):
    moji[ord(m) - ord("a")].append(i)

for i in range(len(s)):
    moji[i].sort()

moji_o = [0 for _ in range(len(t))]

cnt = 0
ans = 1
for i, m in enumerate(t):
    if len(moji[ord(m) - ord("a")]) == 0:
        ans = -1
        break
    if i == 0:
        moji_o[i] = moji[ord(m) - ord("a")][0]
    else:
        if moji_o[i - 1] > moji[ord(m) - ord("a")][-1]:
            moji_o[i] =  moji[ord(m) - ord("a")][0]
        else:
            tmp = bisect.bisect_left(moji[ord(m) - ord("a")], moji_o[i - 1])
            if tmp == 0:
                moji_o[i] = moji[ord(m) - ord("a")][0]
            else:
                moji_o[i] = moji[ord(m) - ord("a")][tmp]

for i in range(1, len(moji_o)):
    if ans == -1:
        break
    if moji_o[i - 1] >= moji_o[i]:
        cnt += 1

if ans == -1:
    print(-1)
else:
    print(cnt * len(s) + moji_o[-1] + 1)

Submission status: Runtime Error

Solution code:
import bisect
INF = 10 ** 10
s = input()
t = input()
moji = [[] for _ in range(26)]

for i, m in enumerate(s):
    moji[ord(m) - ord("a")].append(i)

for i in range(len(s)):
    moji[i].sort()

moji_o = [0 for _ in range(len(t))]

cnt = 0
ans = 1
for i, m in enumerate(t):
    if len(moji[ord(m) - ord("a")]) == 0:
        ans = -1
        break
    if i == 0:
        moji_o[i] = moji[ord(m) - ord("a")][0]
    else:
        tmp = bisect.bisect_right(moji[ord(m) - ord("a")], moji_o[i - 1])
        if tmp == 0:
            moji_o[i] = moji[ord(m) - ord("a")][0]
        else:
            moji_o[i] = moji[ord(m) - ord("a")][tmp - 1]

# print(moji_o, moji)

for i in range(1, len(moji_o)):
    if ans == -1:
        break
    if moji_o[i - 1] >= moji_o[i]:
        cnt += 1

if ans == -1:
    print(-1)
else:
    print(cnt * len(s) + moji_o[-1] + 1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
d = {i:[] for i in "abcdefghijklmnopqrstuvwxyz"}
for i in range(len(s)):
    d[s[i]].append(i)
for i in t:
    if len(d[i]) == 0:
        print(-1)

def binary_search(arr, k):
    l, r = 0, len(arr)-1
    while l <= r:
        m = l+r >> 1
        if arr[m] < k:
            l = m+1
        else:
            r = m-1
    return l

a, b = 0, 0
for i in t:
    j = binary_search(d[i], a)
    if len(d[i]) <= j:
        a = 0
        b += 1
        j = binary_search(d[i], 0)
    a = d[i][j] + 1
print(b * len(s) + a)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
for i in t:
    if i not in s:
        print(-1)
        exit()
s *= len(t)
i, j = 0, 0
while i < len(s) and j < len(t):
    if s[i] == t[j]:
       j += 1
    i += 1
print(i)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
while True:
    snow = s.index(t[tcount])
    tcount += 1
    if tcount == lent:
        break
    if t[tcount] not in s:
        flag = False
        break
    if t[tcount] in s[snow+1:]:
        snow = s[snow+1:].index(t[tcount])
    else:
        snow = s.index(t[tcount])
        count += 1
if flag:
    print(count*len(s) + s.index(t[-1])+1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
while True:
    if tcount == lent:
        break
    if t[tcount] not in s:
        flag = False
        break
    snow = s.index(t[tcount])
    tcount += 1
    if t[tcount] in s[snow+1:]:
        snow = s[snow+1:].index(t[tcount])
    else:
        snow = s.index(t[tcount])
        count += 1
if flag:
    print(count*len(s) + s.index(t[-1])+1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
lent = len(t)
tcount = 0
snow = 0
count = 0
flag = True
while True:
    if t[tcount] not in s:
        flag = False
        break
    snow = s.index(t[tcount])
    tcount += 1
    if tcount == lent:
        break
    if t[tcount] in s[snow+1:]:
        snow = s[snow+1:].index(t[tcount])
    else:
        snow = s.index(t[tcount])
        count += 1
if flag:
    print(count*len(s) + s.index(t[-1])+1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
s = input().strip()
t = input().strip()
A = sorted(list(set(list(s))))
B = sorted(list(set(list(t))))
D = {}
for i in range(len(s)):
    a = s[i]
    if a not in D:
        D[a] = []
    D[a].append(i+1)
cur = 0
for i in range(len(B)):
    flag = 0
    while cur<len(A):
        if A[cur]<B[i]:
            cur += 1
        elif A[cur]==B[i]:
            break
        else:
            flag = 1
            break
    if flag==1:break
if flag==1:
    print(-1)
else:
    C = []
    cur = -1
    for i in range(len(t)):
        b = t[i]
        ind = bisect_right(D[b],cur)%len(D[b])
        C.append(D[b][ind])
        cur = D[b][ind]
    cnt = 0
    for j in range(1,len(C)):
        if C[j]<=C[j-1]:
            cnt += 1
    print(len(s)*cnt+C[-1])

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
s = input().strip()
t = input().strip()
A = sorted(list(set(list(s))))
B = sorted(list(set(list(t))))
D = {}
for i in range(len(s)):
    a = s[i]
    if a not in D:
        D[a] = []
    D[a].append(i+1)
cur = 0
for i in range(len(B)):
    flag = 0
    while cur<len(A):
        if A[cur]<B[i]:
            cur += 1
        elif A[cur]==B[i]:
            break
        else:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    C = []
    cur = -1
    for i in range(len(t)):
        b = t[i]
        ind = bisect_right(D[b],cur)%len(D[b])
        C.append(D[b][ind])
        cur = D[b][ind]
    cnt = 0
    for j in range(1,len(C)):
        if C[j]<=C[j-1]:
            cnt += 1
    print(len(s)*cnt+C[-1])

Submission status: Runtime Error

Solution code:
import bisect

MAX_VALUE = 10**100
S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  Si[s].append(i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    if ans<=max(Si[t]):
      idx = Si[t][bisect.bisect(Si[t],ans)]
    else:
      factor = (ans-min(Si[t]))//lenS + 1
      idx = Si[t][max(min(bisect.bisect(Si[t],ans%lenS),len(Si[t])-1),0)] + factor*lenS
    ans = idx
    if MAX_VALUE<ans:
      print(-1)
      exit()
print(ans+1)

Submission status: Runtime Error

Solution code:
import bisect

MAX_VALUE = 10**100
S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  Si[s].append(i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    if ans<=max(Si[t]):
      idx = Si[t][bisect.bisect(Si[t],ans)]
    else:
      factor = (ans-min(Si[t]))//lenS + 1
      idx = Si[t][min(bisect.bisect(Si[t],ans%lenS),len(Si[t])-1,0)] + factor*lenS
    ans = idx
    if MAX_VALUE<ans:
      print(-1)
      exit()
print(ans+1)

Submission status: Runtime Error

Solution code:
import bisect

MAX_VALUE = 10**100
S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  Si[s].append(i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    if ans<=max(Si[t]):
      idx = Si[t][bisect.bisect(Si[t],ans)]
    else:
      factor = (ans-min(Si[t]))//lenS + 1
      idx = Si[t][min(bisect.bisect(Si[t],ans%lenS),len(Si[t])-1)] + factor*lenS
    ans = idx
    if MAX_VALUE<ans:
      print(-1)
      exit()
print(ans+1)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
d = {}
a = [None]*len(s)
for i in range(len(s))[::-1]:
    d[s[i]] = i
    a[i] = d.copy()
i = n = 0
for c in t:
    if c in a[i]:
        i = a[i][c]
    elif c in a[0]:
        i = a[0][c]
        n += 1
    else:
        print(-1)
        exit()
    i += 1
print(n*len(s)+i)

Submission status: Runtime Error

Solution code:
# Library
import bisect

alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = -1
cir = 0
letter = []
res = 0

for i in range(len(ss)):
    letter.append([ss[i], i])

# Sort出来る.
letter.sort()

for i in range(len(t)):
    search = [t[i], index]
    tmp_ind = bisect.bisect(letter, search)
    # print("now searching " + str(search))
    # print("find: " + str(tmp_ind))
    # print("found: " + str(letter[tmp_ind]))
    if t[i] != letter[tmp_ind][0]:
        # Not exist
        res = -1
        break
    index += (letter[tmp_ind][1] - index)
    if index >= len(s):
        cir += 1
        index -= len(s)
    # print("cir,index : " + str(cir) + " " + str(index))
    res = cir * len(s) + index + 1

print(res)

Submission status: Runtime Error

Solution code:
# Library
import bisect

alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = 0
cir = 0
letter = []
res = 0

for i in range(len(ss)):
    letter.append([ss[i], i])

# Sort出来る.
letter.sort()

for i in range(len(t)):
    search = [t[i], index]
    tmp_ind = bisect.bisect(letter, search)
    # print("now searching " + str(search))
    # print("find: " + str(tmp_ind))
    # print("found: " + str(letter[tmp_ind]))
    if t[i] != letter[tmp_ind][0]:
        # Not exist
        res = -1
        break
    index += (letter[tmp_ind][1] - index)
    if index >= len(s):
        cir += 1
        index -= len(s)
    # print("cir,index : " + str(cir) + " " + str(index))
    res = cir * len(s) + index + 1

print(res)

Submission status: Runtime Error

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

s = [None] + list(input().rstrip("\n"))
len_s = len(s[1:])
t = list(input().rstrip("\n"))
len_t = len(t)

# s'からtが作れない場合
if (set(s[1:]) & set(t)) != set(t):
    print(-1)
    exit()

for i,x in enumerate(t):
    if i == len_t-1:
        tmp = [j for j,y in enumerate(s) if y == t[-1] and j > t[-2]]
        if tmp:
            t[i] = tmp[0]
        else:
            t[i] = s.index(x)
        break
    else:
        t[i] = s.index(x)

answer = 0
for i in range(len_t):
    if i == len_t-1:
        answer += t[-1]
        break
    if t[i] < t[i+1]:
        continue
    else:
        answer += len_s
    if answer > 10**100 * len_s:
        print(-1)
        exit()

if 1 <= answer <= 10**100 * len_s:
    print(answer)
else:
    print(-1)

Submission status: Runtime Error

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

s = [None] + list(input().rstrip("\n"))
len_s = len(s[1:])
t = list(input().rstrip("\n"))

if (set(s[1:]) & set(t)) != set(t):
    print(-1)
    exit()

for i,x in enumerate(t):
    if i == len(t)-1:
        last = [i for i,x in enumerate(s) if x == t[-1] and i > t[-2]]
        if last:
            t[-1] = last[-1]
        else:
            t[i] = s.index(x)
        break

    t[i] = s.index(x)

answer = 0
for i in range(len(t)):
    if i == len(t)-1:
        answer += t[-1]
        break

    if t[i] < t[i+1]:
        continue
    else:
        answer += len_s

print(answer)

Submission status: Runtime Error

Solution code:
import bisect
S = input()
T = input()
OUT = 10**5

N = len(S)
M = len(T)
indice = [0]*M
# 素直にやるとO(NM)かかるので工夫が必要
A = [[] for _ in range(26)]
for i in range(N):
    A[ord(S[i]) - ord('a')].append(i + 1)

res = 0
b = 0
for j in range(M):
    tj = ord(T[j]) - ord('a')
    if len(A[tj]) == 0:
        print(-1)
        exit()
    r = bisect.bisect_right(A[tj], b)
    if len(A[tj]) > r:
        res += A[tj][r] - b
        b = A{tj}[r]
    else:
        res += N - b + A[tj][0]
        b = A[tj][0]

print(res)

Submission status: Runtime Error

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

if len(set(t)-set(s))>0:
  print(-1)
else:
  s2=s*2
  s2pos={}
  for i in range(len(s2)):
    if s2[i] in s2pos:
      s2pos[s2[i]].append(i)
    else:
      s2pos[s2[i]]=[i]

  cur=-1
  import bisect
  rev=0
  for c in t:
    cur+=1
    pos=s2pos[c]
    p=bisect.bisect_left(pos,cur)
    cur=pos[p]
    if cur>len(s):
      cur-=len(s)
      rev+=1
    if rev>=100:
      print(-1)
      break
  else:
    print(rev*len(s)+cur+1)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_right

def main():
    s = input()
    t = input()
    
    table = {a : [] for a in 'abcdefghijklmnopqrstuvwxyz'}
    N = len(s)
    
    for idx, a in enumerate(s): table[a].append(idx+1)
    
    length = {a : len(table[a]) for a in 'abcdeghijklmnopqrstuvwxyz'}
    
    loop, idx = 0, 0
    for a in t:
        if not table[a]: 
            print(-1)
            sys.exit()
        
        i = bisect_right(table[a], idx)
        
        if i != length[a]:
            idx = table[a][i]
            if idx == N:
                loop += 1
                idx = 0
        else:
            loop += 1
            idx = table[a][0]
            
    print(loop * len(s) + idx)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left

def main():
    s = input()
    t = input()
    
    table = {a : [] for a in 'abcdefghijklmnopqrstuvwxyz'}
    
    for idx, a in enumerate(s): table[a].append(idx+1)
    
    length = {a : len(table[a]) for a in 'abcdeghijklmnopqrstuvwxyz'}
    
    loop, idx = 0, 1
    for a in t:
        if not table[a]: 
            print(-1)
            sys.exit()
            
        i = bisect_left(table[a], idx)
    
        if i == length[a]:
            loop += 1
            idx = table[a][0]
        else:
            idx = table[a][i]
            
    print(loop * len(s) + idx)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

check = [False]*30
for c in s:
    i = ord(c) - ord("a")
    check[i] = True

for c in t:
    i = ord(c) - ord("a")
    if not check[i]:
        print(-1)
        sys.exit()

dp = [[0 for i in range(26)] for j in range(len(s))]

s = s + s

#
def ser(string :str,target :str,s :int):
    for i in range(s,len(string)):
        if string[i] == target:
            return i % (len(string)//2),i-1

# 指定した範囲に数字を埋める
def dig(ls,c,v,s,t):
    for i in range(s,t+1):
        ls[i][c] = v

for c in range(len(dp[0])):
    i = 0
    while i < len(dp):
        start = i
        print(i)
        v,i = ser(s,chr(c+ord("a")),i+1)
        dig(dp,c,v,start,min(i,len(dp)-1))
        i += 1

print(dp)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: set())
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].append(i)
    min_D[s] = min(i, min_D[s])

for s in D.keys():
  D[s]=sorted(D[s])
cur_pos = 0
repeat = 0
for t in T:
    for next_cand in D[t]:
        if next_cand >= cur_pos:
            cur_pos = next_cand+1
            break
    else:
        repeat += 1
        cur_pos = min_D[t]
print(len(S)*repeat+cur_pos)

Submission status: Runtime Error

Solution code:
import bisect

S = input()
T = input()


n = len(S)
m = len(T)
c = [[] for _ in range(26)]
for i in range(n):
    idx = ord(S[i]) - ord('a')
    c[idx].append(i)
for i in range(n):
    idx = ord(S[i]) - ord('a')
    c[idx].append(i+n)

print(c)
ans = 0
now = 0
for i in range(m):
    id = ord(T[i]) - ord('a')
    if len(c[id]) == 0:
        print("-1")
        exit()
    now = c[id][bisect.bisect(c[id], now)]
    if now >= n:
        tmp = now-n
        now = n+tmp
ans += now
print(ans+1)