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:
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
using ll = long long; using ld = long double; const char nl = '\n';
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */

#include <bits/extc++.h>
namespace pbds =  __gnu_pbds;
template <typename key, typename val=pbds::null_type, typename comp=less<key>>
using ostree=pbds::tree<key,val,comp,pbds::rb_tree_tag,pbds::tree_order_statistics_node_update>;
using vi = vector< int >; using vll = vector< ll >;
#define all(x) std::begin(x), std::end(x)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename...Args, template<typename...> typename T> string to_string(T<Args...> const&);
string to_string(string const&s){return '"'+s+'"';}
string to_string(char const &c) {return to_string(string(1,c));}
string to_string(char const *c) {return to_string(string(c));}
string to_string(bool const &b) {return (b ? "T" : "F");}
template<typename... Args> string to_string(pair<Args...> const&p)
{return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template <typename...Args, template<typename...> typename T> string to_string(T<Args...> const&S)
{string s = "{"; for(auto const& e: S)s+=" "+to_string(e);s+=" }"; return s;}
template<typename Tail> void debug_out(Tail t) {cerr<<" "<<to_string(t)<<" ]"<<endl;}
template<typename Head, typename... Tail> void debug_out(Head h, Tail... t)
{cerr << " " << to_string(h) << ","; debug_out(t...);}
#define pr(...) cerr<<"["<<(#__VA_ARGS__)<<"] : [", debug_out(__VA_ARGS__)
template <typename T> void dbr(T lb, T ub)
{cerr<<'{';for(auto it=lb; it!=ub; it++)cerr<<' '<<to_string(*it); cerr<<" }"<<endl;}
template<typename T, typename Comp=less<T>> bool smin(T &mem, T const&v, Comp const&cmp=Comp())
{return cmp(v, mem) ? mem = v, true : false;}
template<typename T, typename Comp=less<T>> bool smax(T &mem, T const&v, Comp const&cmp=Comp())
{return cmp(mem, v) ? mem = v, true : false;}
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */

int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  string s, t; cin >> s >> t;
  {
    set<char> S, T;
    for(char c: s) S.emplace(c);
    for(char c: t) T.emplace(c);
    for(char c: T) if( S.find(c) == S.end() ) return cout << -1 << nl, 0;
  }

  int n = s.length();
  int nxt[256][n];

  for(char c='a'; c<='z'; c++) {
    vi pos;
    fill(nxt[c], nxt[c]+n, n);
    for(int zz=0; zz<2; zz++) {
      for(int i=n-1; i>=0; i--) {
	nxt[c][i] = nxt[c][ (i+1) % n ];
	if( s[ (i+1) % n ] == c ) nxt[c][i] = (i+1) % n;
      }
    }
  }

  int pos = 0, i = 0;
  for(; i<(int)t.length(); i++) {
    for(; i<(int)t.length() and t[i] == s[pos % n]; pos++, i++);
    int npos = nxt[ t[i] ][pos % n];
    // pr(i, t[i], pos % n, npos);
    if( npos > (pos % n) ) pos += npos - (pos % n);
    else pos += n - (pos%n) + npos;
    // pr(pos);
  }
  cout << pos+1 << endl;

}

Submission status: Runtime Error

Solution code:
s = list(input())
t = list(input())
c = 0
for i in t:
    if i in s:
        c += 1
        
if c != len(t):
    print(-1)
else:
    for k in range(30):
        j = 0
        for i in s:
            if i == t[j]:
                j += 1
        if j == len(t):
            print(len(s))
            break
        else:
            s.append(s[k])

Submission status: Runtime Error

Solution code:
import sys

s=input()
t=input()

orig_s=s

def search(s,t,ans):
    if len(t)==0:
        return ans
    index=s.find(t[0])
    if index==-1:
        print('-1')
        sys.exit()
    else:
        return search(s[index+1:]+orig_s,t[1:],ans+index+1)

print(search(s,t,0))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000000)


class Graph:

  def __init__(self, N):
    self.V = {}
    self.E = {}

    for i in range(N):
      self.V[i + 1] = 0
      self.E[i + 1] = {}

  def add_edge(self, u, v, w):
    self.E[u][v] = w


def calc(N, G):
  result = [0] * N

  def walk(u, current_value=0):
    current_value = G.V[u] + current_value
    result[u - 1] = current_value
    for v in G.E[u]:
      walk(v, current_value)

  walk(1, 0)

  return result


N, Q = map(int, input().strip().split())

G = Graph(N)

for _ in range(N - 1):
  a, b = map(int, input().strip().split())
  G.add_edge(a, b, 0)

for _ in range(Q):
  p, x = map(int, input().strip().split())
  G.V[p] += x

result = calc(N, G)

print(' '.join(map(str, result)))