Submission #1846715

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s, t;
int n, ans, m;
vector<int> s0, t0;

int main() {
	cin >> n >> s >> t;

	if (s == t) {
		cout << "0\n";
		return 0;
	}

	int ptr = n-1;
	for (int i = n-1; i >= 0; --i) {
		if (i > 0 && t[i] == t[i-1])
			continue;
		t0.push_back(i);
		if (ptr > i)
			ptr = i;
		while (ptr >= 0 && s[ptr] != t[i])
			ptr--;
		if (ptr == -1)
			continue;
		s0.push_back(ptr);
	}

	if (s0.size() != t0.size()) {
		cout << "-1\n";
		return 0;
	}

	reverse(s0.begin(), s0.end());
	reverse(t0.begin(), t0.end());
	m = s0.size();

	for (int i = 0; i < m; ++i) {
		if (s0[i] > t0[i]) {
			cout << "0\n";
			return 0;
		}
	}

	s0.push_back(n);
	ans = 0;

	for (int i = 0; i < m; ++i) {
		int lo = 0, hi = m-i;
		while (lo != hi) {
			int mid = (lo + hi)/2;
			if (s0[mid+i]-mid >= t0[i])
				hi = mid;
			else
				lo = mid+1;
		}

		ans = max(ans, lo);
	}

	cout << ans+1 << endl;
}

Submission Info

Judge Result