Submission #980116

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
string s,t;
VI ced,gled;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  cin>>s>>t;
  in mx=0;
  in ns=n;
  in pns=n;
  for(in nt=n-1;nt>=0;--nt){
    while(ns>=0 && (ns==n || s[ns]!=t[nt] || ns>nt)){
      --ns;
    }
    if(ns<0){
      cout<<-1<<endl;
      return 0;
    }
    if(ns==pns)
      continue;
    pns=ns;
    ced.PB(ns);
    gled.PB(nt);
  }
  reverse(all(ced));
  reverse(all(gled));
  forv(i,ced){
    while(i+mx<sz(ced) && ced[i+mx]-mx<gled[i])
      ++mx;
  }
  cout<<mx<<endl;
  return 0;
}

Submission Info

Judge Result