Prefix-Substring LCS
(string/prefix_substring_lcs.hpp)
- View this file on GitHub
- Last update: 2026-07-16 21:38:59+09:00
- Include:
#include "string/prefix_substring_lcs.hpp"
Overview
PrefixSubstringLcs records queries for the length of a longest common
subsequence of first[0..a) and second[b..c), then evaluates the complete
batch efficiently. Answers are returned in query insertion order.
The structure uses a seaweed permutation for semi-local LCS and processes the
queries offline. It stores copies of both input sequences. Each sequence must
provide size() and operator[], and first[i] == second[j] must be valid.
Let N = first.size(), M = second.size(), Q be the number of queries, and
A be the number of distinct positive prefix lengths that have a nonempty
substring query.
Methods
| Method | Description | Complexity |
|---|---|---|
PrefixSubstringLcs(FirstSequence first, SecondSequence second) |
Copies or moves the two sequences. | O(N + M) |
int first_size() const |
Returns N. |
O(1) |
int second_size() const |
Returns M. |
O(1) |
int query_count() const |
Returns the number of recorded queries. | O(1) |
bool empty() const |
Returns whether no queries are recorded. | O(1) |
void reserve(int query_capacity) |
Reserves storage for queries. |
O(Q) worst case |
void clear() |
Removes all queries while preserving the two sequences. | O(Q) |
int add_query(int a, int b, int c) |
Records LCS(first[0..a), second[b..c)) and returns its insertion-order ID. |
Amortized O(1)
|
vector<int> calculate() const |
Returns all recorded answers in insertion order. | O(NM + (AM + Q) log(M + 1)) |
calculate() uses O(N + M + Q) auxiliary memory. Its worst-case time is
O((NM + Q) log(M + 1)). It does not mutate the object, so it may be called more
than once. An empty prefix or empty substring has answer zero.
Indices are zero-based and substring ranges are half-open. A query must satisfy
0 <= a <= N and 0 <= b <= c <= M.
Example
#include "string/prefix_substring_lcs.hpp"
#include <iostream>
#include <string>
int main() {
std::string first = "abac";
std::string second = "cababa";
m1une::string::PrefixSubstringLcs solver(first, second);
solver.add_query(3, 1, 5);
solver.add_query(4, 0, 3);
for (int answer : solver.calculate()) {
std::cout << answer << "\n";
}
}
Required by
Verified with
Code
#ifndef M1UNE_STRING_PREFIX_SUBSTRING_LCS_HPP
#define M1UNE_STRING_PREFIX_SUBSTRING_LCS_HPP 1
#include <algorithm>
#include <cassert>
#include <type_traits>
#include <utility>
#include <vector>
namespace m1une {
namespace string {
// Answers LCS-length queries between a prefix of the first sequence and a
// substring of the second sequence. Queries are evaluated as one offline batch.
template <class FirstSequence, class SecondSequence>
class PrefixSubstringLcs {
private:
struct Query {
int first_prefix;
int second_left;
int second_right;
};
FirstSequence _first;
SecondSequence _second;
std::vector<Query> _queries;
public:
PrefixSubstringLcs(FirstSequence first, SecondSequence second)
: _first(std::move(first)), _second(std::move(second)) {}
int first_size() const {
return int(_first.size());
}
int second_size() const {
return int(_second.size());
}
int query_count() const {
return int(_queries.size());
}
bool empty() const {
return _queries.empty();
}
void reserve(int query_capacity) {
assert(0 <= query_capacity);
_queries.reserve(query_capacity);
}
void clear() {
_queries.clear();
}
// Adds LCS(first[0..first_prefix), second[second_left..second_right)) and
// returns its insertion-order ID.
int add_query(int first_prefix, int second_left, int second_right) {
assert(0 <= first_prefix && first_prefix <= first_size());
assert(0 <= second_left && second_left <= second_right);
assert(second_right <= second_size());
const int id = query_count();
_queries.push_back(Query{first_prefix, second_left, second_right});
return id;
}
std::vector<int> calculate() const {
const int first_length = first_size();
const int second_length = second_size();
const int count = query_count();
std::vector<int> answers(count, 0);
if (count == 0 || first_length == 0 || second_length == 0) {
return answers;
}
std::vector<std::vector<int>> queries_by_prefix(first_length + 1);
for (int id = 0; id < count; id++) {
const Query& query = _queries[id];
if (query.first_prefix > 0 &&
query.second_left < query.second_right) {
queries_by_prefix[query.first_prefix].push_back(id);
}
}
// seaweed[j] is the bottom endpoint of the seaweed entering at j for
// the current prefix of the first sequence. -1 denotes the left edge.
std::vector<int> seaweed(second_length);
for (int j = 0; j < second_length; j++) seaweed[j] = j;
std::vector<int> heads(second_length + 1, -1);
std::vector<int> next(count, -1);
std::vector<int> fenwick(second_length + 1, 0);
for (int i = 0; i < first_length; i++) {
int displaced = -1;
for (int j = 0; j < second_length; j++) {
if (_first[i] == _second[j] || seaweed[j] < displaced) {
std::swap(seaweed[j], displaced);
}
}
const std::vector<int>& prefix_queries = queries_by_prefix[i + 1];
if (prefix_queries.empty()) continue;
std::fill(heads.begin(), heads.end(), -1);
for (int id : prefix_queries) {
const int right = _queries[id].second_right;
next[id] = heads[right];
heads[right] = id;
}
std::fill(fenwick.begin(), fenwick.end(), 0);
int inserted = 0;
for (int right = 1; right <= second_length; right++) {
const int endpoint = seaweed[right - 1];
if (endpoint >= 0) {
inserted++;
for (int position = endpoint + 1;
position <= second_length;
position += position & -position) {
fenwick[position]++;
}
}
for (int id = heads[right]; id != -1; id = next[id]) {
const int left = _queries[id].second_left;
int below_left = 0;
for (int position = left; position > 0;
position -= position & -position) {
below_left += fenwick[position];
}
const int crossing = inserted - below_left;
answers[id] = (right - left) - crossing;
}
}
}
return answers;
}
};
template <class FirstSequence, class SecondSequence>
PrefixSubstringLcs(FirstSequence&&, SecondSequence&&)
-> PrefixSubstringLcs<
std::decay_t<FirstSequence>,
std::decay_t<SecondSequence>
>;
} // namespace string
} // namespace m1une
#endif // M1UNE_STRING_PREFIX_SUBSTRING_LCS_HPP#line 1 "string/prefix_substring_lcs.hpp"
#include <algorithm>
#include <cassert>
#include <type_traits>
#include <utility>
#include <vector>
namespace m1une {
namespace string {
// Answers LCS-length queries between a prefix of the first sequence and a
// substring of the second sequence. Queries are evaluated as one offline batch.
template <class FirstSequence, class SecondSequence>
class PrefixSubstringLcs {
private:
struct Query {
int first_prefix;
int second_left;
int second_right;
};
FirstSequence _first;
SecondSequence _second;
std::vector<Query> _queries;
public:
PrefixSubstringLcs(FirstSequence first, SecondSequence second)
: _first(std::move(first)), _second(std::move(second)) {}
int first_size() const {
return int(_first.size());
}
int second_size() const {
return int(_second.size());
}
int query_count() const {
return int(_queries.size());
}
bool empty() const {
return _queries.empty();
}
void reserve(int query_capacity) {
assert(0 <= query_capacity);
_queries.reserve(query_capacity);
}
void clear() {
_queries.clear();
}
// Adds LCS(first[0..first_prefix), second[second_left..second_right)) and
// returns its insertion-order ID.
int add_query(int first_prefix, int second_left, int second_right) {
assert(0 <= first_prefix && first_prefix <= first_size());
assert(0 <= second_left && second_left <= second_right);
assert(second_right <= second_size());
const int id = query_count();
_queries.push_back(Query{first_prefix, second_left, second_right});
return id;
}
std::vector<int> calculate() const {
const int first_length = first_size();
const int second_length = second_size();
const int count = query_count();
std::vector<int> answers(count, 0);
if (count == 0 || first_length == 0 || second_length == 0) {
return answers;
}
std::vector<std::vector<int>> queries_by_prefix(first_length + 1);
for (int id = 0; id < count; id++) {
const Query& query = _queries[id];
if (query.first_prefix > 0 &&
query.second_left < query.second_right) {
queries_by_prefix[query.first_prefix].push_back(id);
}
}
// seaweed[j] is the bottom endpoint of the seaweed entering at j for
// the current prefix of the first sequence. -1 denotes the left edge.
std::vector<int> seaweed(second_length);
for (int j = 0; j < second_length; j++) seaweed[j] = j;
std::vector<int> heads(second_length + 1, -1);
std::vector<int> next(count, -1);
std::vector<int> fenwick(second_length + 1, 0);
for (int i = 0; i < first_length; i++) {
int displaced = -1;
for (int j = 0; j < second_length; j++) {
if (_first[i] == _second[j] || seaweed[j] < displaced) {
std::swap(seaweed[j], displaced);
}
}
const std::vector<int>& prefix_queries = queries_by_prefix[i + 1];
if (prefix_queries.empty()) continue;
std::fill(heads.begin(), heads.end(), -1);
for (int id : prefix_queries) {
const int right = _queries[id].second_right;
next[id] = heads[right];
heads[right] = id;
}
std::fill(fenwick.begin(), fenwick.end(), 0);
int inserted = 0;
for (int right = 1; right <= second_length; right++) {
const int endpoint = seaweed[right - 1];
if (endpoint >= 0) {
inserted++;
for (int position = endpoint + 1;
position <= second_length;
position += position & -position) {
fenwick[position]++;
}
}
for (int id = heads[right]; id != -1; id = next[id]) {
const int left = _queries[id].second_left;
int below_left = 0;
for (int position = left; position > 0;
position -= position & -position) {
below_left += fenwick[position];
}
const int crossing = inserted - below_left;
answers[id] = (right - left) - crossing;
}
}
}
return answers;
}
};
template <class FirstSequence, class SecondSequence>
PrefixSubstringLcs(FirstSequence&&, SecondSequence&&)
-> PrefixSubstringLcs<
std::decay_t<FirstSequence>,
std::decay_t<SecondSequence>
>;
} // namespace string
} // namespace m1une