String Overlap

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const long long INF = 1e17; //❄️
    5int main() {
    6    ios::sync_with_stdio(0); cin.tie(0); 
    7    string s, ss; cin >> s >> ss;
    8    int ans = 0;
    9    // for (int i = 0; i < min(s.size(), ss.size()); i++) {
    10    //     if (s.substr(s.size() - i - 1, i + 1) == ss.substr(0, i + 1) || ss.substr(ss.size() - i - 1, i + 1) == s.substr(0, i + 1)) ans = max(ans, i + 1);
    11    // }
    12    auto prefix_function = [&] (string a) {
    13        vector<int> pi(a.size());
    14        for (int i = 1; i < a.size(); i++) {
    15            int j = pi[i-1];
    16            while (j > 0 && a[i] != a[j]) {
    17                j = pi[j-1];
    18            }
    19            if (a[i] == a[j]) j++;
    20            pi[i] = j;
    21        }
    22        return pi;
    23    };
    24    vector<int> pi = prefix_function(s + "#" + ss);
    25    ans = max(ans, pi.back());
    26    pi = prefix_function(ss + "#" + s);
    27    ans = max(ans, pi.back());
    28    cout << ans << '\n';
    29    return 0;
    30}