Struct LongestCommonSubsequence 

pub struct LongestCommonSubsequence { /* private fields */ }

The Longest Common Subsequence problem.

Given an alphabet of size k and a set of strings over {0, ..., k-1}, find a longest string w that is a subsequence of every input string.

Representation

The configuration is a vector of length max_length, where each entry is either a symbol in {0, ..., alphabet_size - 1} or None as padding. Padding must be contiguous at the end of the vector. The effective subsequence consists of the symbols before padding starts. The objective is to maximize the effective length.

Implementations

impl LongestCommonSubsequence

pub fn new(alphabet_size: usize, strings: Vec<Vec<usize>>) -> Self

Create a new LongestCommonSubsequence instance.

The max_length is computed automatically as the minimum of all string lengths (the maximum possible common subsequence length).

Panics

Panics if alphabet_size == 0 and any input string is non-empty, or if an input symbol is outside the declared alphabet, or if all strings are empty (max_length would be 0, requiring at least one non-empty string).

pub fn alphabet_size(&self) -> usize

Returns the alphabet size.

pub fn strings(&self) -> &[Vec<usize>]

Returns the input strings.

pub fn max_length(&self) -> usize

Returns the max_length field.

pub fn num_strings(&self) -> usize

Returns the number of input strings.

pub fn total_length(&self) -> usize

Returns the total input length across all strings.

pub fn sum_squared_lengths(&self) -> usize

Returns the sum of squared string lengths.

pub fn sum_triangular_lengths(&self) -> usize

Returns the sum of triangular numbers len * (len + 1) / 2 across strings.

pub fn num_transitions(&self) -> usize

Returns the number of adjacent position transitions.

pub fn cross_frequency_product(&self) -> usize

Returns the cross-frequency product: the sum over each alphabet symbol of the product of that symbol’s frequency across all input strings.

Formally: Σ_{c ∈ 0..alphabet_size} Π_{i=1..k} count(c, strings[i]) where count(c, s) is the number of occurrences of symbol c in string s.

This equals the exact number of match-node vertices in the LCS → MaxIS reduction graph.

Trait Implementations

impl BruteForceProblem for LongestCommonSubsequence

fn dimensions(&self) -> Vec<usize>

Cardinality of each coordinate in the brute-force search space.

fn num_variables(&self) -> usize

Number of coordinates in the brute-force search space.

impl Clone for LongestCommonSubsequence

fn clone(&self) -> LongestCommonSubsequence

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for LongestCommonSubsequence

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DeclaredVariant for LongestCommonSubsequence

impl<'de> Deserialize<'de> for LongestCommonSubsequence

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for LongestCommonSubsequence

const NAME: &'static str = "LongestCommonSubsequence"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Solution = Vec<Option<usize>>

Mathematical witness type for this problem.

type Value = Max<i64>

The evaluation value type.

fn parameter_names() -> &'static [&'static str]

Canonical parameter names for this problem model.

fn parameters(&self) -> ProblemParameters

Measure the complete canonical parameters of this concrete instance.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn evaluate(&self, config: &Self::Solution) -> Result<Max<i64>, EvaluationError>

Evaluate the problem on a solution.

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP> for LongestCommonSubsequence

type Result = ReductionLCSToILP

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<LongestCommonSubsequence> for MinimumVertexCover<SimpleGraph, One>

type Result = ReductionVCToLCS

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, One>> for LongestCommonSubsequence

type Result = ReductionLCSToIS

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl Serialize for LongestCommonSubsequence

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.