【題解】Codeforces 1492C. Maximum width

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int maxn = 200005;
int n, m, l[maxn], r[maxn], ans;
string s, t;
vector <int> v[26];
 
int main() {
    cin >> n >> m;
    cin >> s >> t;
    for (int i = 1; i <= n; i++){
        v[s[i-1]-'a'].push_back(i);
    }
    l[1] = *v[t[0]-'a'].begin();
    for (int i = 2; i <= m; i++){
        int c = t[i-1]-'a';
        l[i] = *upper_bound(v[c].begin(), v[c].end(), l[i-1]);
    }
    r[m] = v[t[m-1]-'a'].back();
    for (int i = m-1; i >= 1; i--){
        int c = t[i-1]-'a';
        r[i] = v[c][lower_bound(v[c].begin(), v[c].end(), r[i+1])-v[c].begin()-1];
    }
    for (int i = 1; i < m; i++){
        if (!r[i+1] || !l[i]) continue;
        ans = max(ans, r[i+1]-l[i]);
    }
    cout << ans << "\n";
}