String Finding

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    // z algorithm 
    9    ios::sync_with_stdio(0); cin.tie(0);
    10    string s, a; cin >> s >> a;
    11    string t = a + "#" + s;
    12    vector<int> z(t.size());
    13    int l = 0, r = 0;
    14    for (int i = 1; i < t.size(); i++) {
    15        if (i <= r) {
    16            z[i] = min(r - i + 1, z[i - l]);
    17        }
    18        while (i + z[i] < t.size() && t[z[i]] == t[i + z[i]]) {
    19            z[i]++;
    20        }
    21        if (i + z[i] - 1 > r) {
    22            l = i;
    23            r = i + z[i] - 1;
    24        }
    25    }
    26    for (int i = a.size() + 1; i < t.size(); i++) {
    27        if (z[i] >= a.size()) {
    28            cout << i - a.size() - 1 << '\n';
    29            return 0;
    30        }
    31    }
    32    cout << -1 << '\n';
    33    return 0;
    34}