Longest Common Substring (verify/string/longest_common_substring.test.cpp)

View this file on GitHub
Last update: 2026-09-10 02:45:56+02:00
Problem: https://judge.yosupo.jp/problem/longest_common_substring

Depends on

Code

// @brief Longest Common Substring
#define PROBLEM "https://judge.yosupo.jp/problem/longest_common_substring"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define CP_ALGO_CHECKPOINT
#include "cp-algo/util/checkpoint.hpp"
#include "cp-algo/util/big_alloc.hpp"
#include <iostream>
#include "blazingio/blazingio.min.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string s, t;
    std::cin >> s >> t;
    bool swapped = s.size() > t.size();
    if(swapped) std::swap(s, t);
    std::array<int, 26> code;
    code.fill(-1);
    int alphabet = 0;
    for(auto str: {&s, &t}) {
        for(char &c: *str) {
            int &rank = code[c - 'a'];
            if(rank < 0) rank = alphabet++;
            c = char(rank);
        }
    }
    cp_algo::big_vector<int> len(2 * s.size() + 1), link(len.size()), pos(len.size());
    cp_algo::big_vector<int> transitions(len.size() * alphabet);
    auto edge = [&](int v, int c) -> int& { return transitions[size_t(v) * alphabet + c]; };
    cp_algo::checkpoint("init");
    int last = 0, size = 1;
    for(char c: s) {
        int x = c, p = last;
        last = size++;
        len[last] = pos[last] = len[p] + 1;
        for(; !edge(p, x); p = link[p]) {
            edge(p, x) = last;
        }
        int q = edge(p, x);
        if(q != last) {
            if(len[q] == len[p] + 1) {
                link[last] = q;
            } else {
                int clone = size++;
                link[clone] = link[q];
                pos[clone] = pos[q];
                std::copy_n(&edge(q, 0), alphabet, &edge(clone, 0));
                len[clone] = len[p] + 1;
                link[last] = link[q] = clone;
                for(; edge(p, x) == q; p = link[p]) {
                    edge(p, x) = clone;
                }
            }
        }
    }
    cp_algo::checkpoint("build");
    int v = 0, length = 0, best = 0, end_s = 0, end_t = 0;
    for(int i = 0; i < (int)t.size(); i++) {
        int x = t[i];
        while(v && !edge(v, x)) {
            v = link[v];
            length = len[v];
        }
        v = edge(v, x);
        length = v ? length + 1 : 0;
        if(length > best) {
            best = length;
            end_s = pos[v];
            end_t = i + 1;
        }
    }
    cp_algo::checkpoint("query");
    cp_algo::checkpoint<1>();
    if(swapped) std::swap(end_s, end_t);
    std::cout << end_s - best << ' ' << end_s << ' '
              << end_t - best << ' ' << end_t << '\n';
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 290, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/languages/cplusplus.py", line 243, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/languages/cplusplus_bundle.py", line 322, in update
    assert len(lines) == len(uncommented_lines)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	12 ms	23 MB
g++	all_same_01	AC	11 ms	23 MB
g++	all_same_02	AC	10 ms	23 MB
g++	all_same_03	AC	12 ms	23 MB
g++	example_00	AC	2 ms	6 MB
g++	example_01	AC	2 ms	6 MB
g++	example_02	AC	2 ms	6 MB
g++	example_03	AC	2 ms	6 MB
g++	max_large_ans_00	AC	25 ms	27 MB
g++	max_large_ans_01	AC	33 ms	31 MB
g++	max_large_ans_02	AC	32 ms	59 MB
g++	max_large_ans_03	AC	46 ms	121 MB
g++	max_random_00	AC	34 ms	27 MB
g++	max_random_01	AC	39 ms	31 MB
g++	max_random_02	AC	46 ms	59 MB
g++	max_random_03	AC	54 ms	121 MB
g++	random_00	AC	28 ms	23 MB
g++	random_01	AC	36 ms	27 MB
g++	random_02	AC	14 ms	12 MB
g++	random_03	AC	12 ms	13 MB
g++	small_00	AC	2 ms	6 MB
g++	small_01	AC	2 ms	6 MB
g++	small_02	AC	2 ms	6 MB
g++	small_03	AC	2 ms	6 MB
g++	small_04	AC	2 ms	6 MB
g++	small_05	AC	2 ms	6 MB
g++	small_06	AC	2 ms	6 MB
g++	small_07	AC	2 ms	6 MB