Submission #978970

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <queue>
#include <stack>
#include <bitset>
#define y1 y11
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define NAME ""

using namespace std;
	
typedef long long ll;
typedef long double ld;

const ld PI = acos(-1.0);

const int MAXN = 1000001;
string s;
string t;
int a[MAXN];

int main()
{
	int n;
	cin >> n;
	cin >> s >> t;
	if (s == t)
	{
		cout << 0 << endl;
		return 0;
	}
	int p = n;
	int ans = 0;
	int k = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		p = min(p, i);
		if ((i != 0) && (t[i] == t[i  - 1])) continue;
		while ((p >= 0) && (s[p] != t[i])) p--;
		if (p < 0)
		{
			cout << -1 << endl;
			return 0;
		}
		a[k] = p;
		int lg = 0, rg = k + 1;
		while (lg < rg)
		{
			int md  = (lg + rg) / 2;
			if (a[k - md] - md >= i) rg = md;
			else lg = md + 1;
		}
		ans = max(ans, lg);
		k++;
	}
	cout << ans + 1 << endl;
	return 0;
}

Submission Info

Judge Result