verify/yosupo/yosupo_longest_common_substring.test.cpp

View this file on GitHub
Last update: 2024-12-02 02:18:27+09:00
Problem: https://judge.yosupo.jp/problem/longest_common_substring

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/longest_common_substring"

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

#include "../../string/suffix_array.hpp"
#include "../../string/lcp_array.hpp"

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string S, T;
    cin >> S >> T;

    int ssz = S.size();

    S += "$";
    S += T;

    auto sa = suffix_array(S);
    auto lcp = lcp_array(S, sa);

    int N = S.size();
    int a = 0, b = 0, c = 0, d = 0;
    for(int i = 0; i < N - 1; i++) {
        int i1 = i, i2 = i + 1;
        if(sa[i1] > sa[i2]) swap(i1, i2);
        if(lcp[i] <= b - a) continue;
        if(sa[i1] < ssz && ssz < sa[i2]) {
            a = sa[i1];
            b = a + lcp[i];
            c = sa[i2] - ssz - 1;
            d = c + lcp[i];
        }
    }

    cout << a << " " << b << " " << c << " " << d << "\n";

    return 0;
}

#line 1 "verify/yosupo/yosupo_longest_common_substring.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_common_substring"

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

#line 1 "string/suffix_array.hpp"
vector<int> suffix_array(const string& S) {
    int N = S.size();
    vector<int> rank(N), sa(N);

    for(int i = 0; i < N; i++) {
        sa[i] = i;
        rank[i] = S[i];
    }

    for(int k = 1; k < N; k *= 2) {
        auto get_rank = [&](int i) -> int { return (i < N) ? rank[i] : 0; };

        auto radix_sort = [&](int k) -> void {
            const int CHAR_SIZE = 130;
            vector<int> backet(max(N + 1, CHAR_SIZE), 0), nsa(N);
            for(int i = 0; i < N; i++) {
                backet[get_rank(i + k)]++;
            }
            for(int i = 1; i < backet.size(); i++) {
                backet[i] += backet[i - 1];
            }
            for(int i = N; i--;) {
                int& x = backet[get_rank(sa[i] + k)];
                nsa[--x] = sa[i];
            }
            swap(sa, nsa);
        };
        radix_sort(k);
        radix_sort(0);

        vector<int> nrank(N);
        nrank[sa[0]] = 1;
        for(int i = 1; i < N; i++) {
            bool is_different = (get_rank(sa[i - 1]) != get_rank(sa[i]) || get_rank(sa[i - 1] + k) != get_rank(sa[i] + k));
            nrank[sa[i]] = nrank[sa[i - 1]] + is_different;
        }
        swap(rank, nrank);
    }

    return sa;
}
#line 1 "string/lcp_array.hpp"
vector<int> lcp_array(const string& S, const vector<int>& sa) {
    int N = S.size();
    vector<int> rank(N);
    for(int i = 0; i < N; i++) {
        rank[sa[i]] = i;
    }
    vector<int> lcp(N - 1);
    int h = 0;
    for(int i = 0; i < N; i++) {
        if(h > 0) h--;
        if(rank[i] == 0) continue;
        int j = sa[rank[i] - 1];
        while(i + h < N && j + h < N && S[i + h] == S[j + h]) h++;
        lcp[rank[i] - 1] = h;
    }
    return lcp;
}
#line 8 "verify/yosupo/yosupo_longest_common_substring.test.cpp"

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string S, T;
    cin >> S >> T;

    int ssz = S.size();

    S += "$";
    S += T;

    auto sa = suffix_array(S);
    auto lcp = lcp_array(S, sa);

    int N = S.size();
    int a = 0, b = 0, c = 0, d = 0;
    for(int i = 0; i < N - 1; i++) {
        int i1 = i, i2 = i + 1;
        if(sa[i1] > sa[i2]) swap(i1, i2);
        if(lcp[i] <= b - a) continue;
        if(sa[i1] < ssz && ssz < sa[i2]) {
            a = sa[i1];
            b = a + lcp[i];
            c = sa[i2] - ssz - 1;
            d = c + lcp[i];
        }
    }

    cout << a << " " << b << " " << c << " " << d << "\n";

    return 0;
}