problemreductions/models/misc/
shortest_common_superstring.rs

1//! Shortest Common Superstring problem implementation.
2//!
3//! Given a set of strings over an alphabet, find the shortest common
4//! superstring. A string `w` is a superstring of `s` if `s` appears as a
5//! _contiguous substring_ of `w` (i.e., there exist `w_0, w_1` in `Sigma^*`
6//! with `w = w_0 s w_1`). This is stricter than the subsequence-based
7//! `ShortestCommonSupersequence`.
8//!
9//! The configuration uses a fixed-length representation of `max_length`
10//! optional symbols. `None` serves as padding/end marker, and the effective
11//! superstring is the prefix before the first `None`. `max_length` equals the
12//! sum of all input string lengths (the worst case where no overlap exists).
13//! This problem is NP-complete (Maier and Storer, 1977).
14//!
15//! Reference: Garey & Johnson, *Computers and Intractability*, problem SR9
16//! (P157).
17
18use crate::registry::{FieldInfo, ProblemSchemaEntry};
19use crate::traits::Problem;
20use crate::types::Min;
21use serde::{Deserialize, Serialize};
22
23inventory::submit! {
24    ProblemSchemaEntry {
25        name: "ShortestCommonSuperstring",
26        display_name: "Shortest Common Superstring",
27        aliases: &["SCSS"],
28        dimensions: &[],
29        category: crate::registry::ProblemCategory::Misc,
30        module_path: module_path!(),
31        description: "Find a shortest string that contains every input string as a contiguous substring",
32        fields: &[
33            FieldInfo { name: "alphabet_size", type_name: "usize", description: "Size of the alphabet" },
34            FieldInfo { name: "strings", type_name: "Vec<Vec<usize>>", description: "Input strings over the alphabet {0, ..., alphabet_size-1}" },
35            FieldInfo { name: "max_length", type_name: "usize", description: "Maximum possible superstring length (sum of all string lengths)" },
36        ],
37    }
38}
39
40/// The Shortest Common Superstring problem.
41///
42/// Given an alphabet of size `k` and a set of strings over `{0, ..., k-1}`,
43/// find the shortest string `w` such that every input string appears as a
44/// contiguous substring of `w`.
45///
46/// # Representation
47///
48/// The configuration is a vector of length `max_length`, where each entry is
49/// either a symbol in `{0, ..., alphabet_size - 1}` or `None` as padding. The
50/// effective superstring is the prefix of symbols before the first padding
51/// value. Padding must be contiguous at the end.
52///
53/// # Example
54///
55/// ```
56/// use problemreductions::models::misc::ShortestCommonSuperstring;
57/// use problemreductions::{Problem, BruteForce};
58///
59/// // Alphabet {0, 1}, strings [0,1] and [1,0]
60/// let problem = ShortestCommonSuperstring::new(2, vec![vec![0, 1], vec![1, 0]]);
61/// let solver = BruteForce::new();
62/// let solution = solver.solve(&problem).unwrap();
63/// assert!(solution.is_some());
64/// ```
65#[derive(Debug, Clone, Serialize, Deserialize)]
66pub struct ShortestCommonSuperstring {
67    alphabet_size: usize,
68    strings: Vec<Vec<usize>>,
69    max_length: usize,
70}
71
72impl ShortestCommonSuperstring {
73    /// Create a new ShortestCommonSuperstring instance.
74    ///
75    /// `max_length` is computed automatically as the sum of all input string
76    /// lengths (the trivial upper bound: concatenation with no overlap).
77    ///
78    /// # Panics
79    ///
80    /// Panics if `strings` is empty, or if `alphabet_size` is 0 and any input
81    /// string is non-empty.
82    pub fn new(alphabet_size: usize, strings: Vec<Vec<usize>>) -> Self {
83        assert!(!strings.is_empty(), "must have at least one string");
84        let max_length: usize = strings.iter().map(|s| s.len()).sum();
85        assert!(
86            alphabet_size > 0 || strings.iter().all(|s| s.is_empty()),
87            "alphabet_size must be > 0 when any input string is non-empty"
88        );
89        Self {
90            alphabet_size,
91            strings,
92            max_length,
93        }
94    }
95
96    /// Returns the alphabet size.
97    pub fn alphabet_size(&self) -> usize {
98        self.alphabet_size
99    }
100
101    /// Returns the input strings.
102    pub fn strings(&self) -> &[Vec<usize>] {
103        &self.strings
104    }
105
106    /// Returns the maximum possible superstring length.
107    pub fn max_length(&self) -> usize {
108        self.max_length
109    }
110
111    /// Returns the number of input strings.
112    pub fn num_strings(&self) -> usize {
113        self.strings.len()
114    }
115
116    /// Returns the total length of all input strings.
117    pub fn total_length(&self) -> usize {
118        self.strings.iter().map(|s| s.len()).sum()
119    }
120}
121
122/// Check whether `needle` appears as a contiguous substring of `haystack`.
123fn is_substring(needle: &[usize], haystack: &[usize]) -> bool {
124    if needle.is_empty() {
125        return true;
126    }
127    if needle.len() > haystack.len() {
128        return false;
129    }
130    haystack
131        .windows(needle.len())
132        .any(|window| window == needle)
133}
134
135impl Problem for ShortestCommonSuperstring {
136    const NAME: &'static str = "ShortestCommonSuperstring";
137    type Solution = Vec<Option<usize>>;
138    type Value = Min<i64>;
139
140    crate::problem_parameters![
141        ("alphabet_size", alphabet_size),
142        ("num_strings", num_strings),
143        ("max_length", max_length),
144        ("total_length", total_length),
145    ];
146
147    fn variant() -> Vec<(&'static str, &'static str)> {
148        crate::variant_params![]
149    }
150
151    fn evaluate(
152        &self,
153        config: &Self::Solution,
154    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
155        if config.len() != self.max_length {
156            return Err(crate::traits::EvaluationError::InvalidConfiguration(
157                "superstring representation length does not match the bound".into(),
158            ));
159        }
160        if config
161            .iter()
162            .any(|symbol| symbol.is_some_and(|value| value >= self.alphabet_size))
163        {
164            return Err(crate::traits::EvaluationError::InvalidConfiguration(
165                "superstring contains an out-of-range symbol".into(),
166            ));
167        }
168        let config = config
169            .iter()
170            .map(|symbol| symbol.unwrap_or(self.alphabet_size))
171            .collect::<Vec<_>>();
172        Ok({
173            let pad = self.alphabet_size;
174
175            // Find effective length = index of first padding symbol
176            let effective_length = config
177                .iter()
178                .position(|&v| v == pad)
179                .unwrap_or(self.max_length);
180
181            // Verify all positions after first padding are also padding (no interleaved padding)
182            for &v in &config[effective_length..] {
183                if v != pad {
184                    return Ok(Min(None));
185                }
186            }
187
188            let prefix = &config[..effective_length];
189
190            // Check every input string appears as a contiguous substring of the prefix
191            if !self.strings.iter().all(|s| is_substring(s, prefix)) {
192                return Ok(Min(None));
193            }
194
195            Min(Some(i64::try_from(effective_length).map_err(|_| {
196                crate::traits::EvaluationError::IntegerOverflow(
197                    "converting superstring length to i64".into(),
198                )
199            })?))
200        })
201    }
202}
203
204impl crate::solvers::BruteForceProblem for ShortestCommonSuperstring {
205    fn dimensions(&self) -> Vec<usize> {
206        vec![self.alphabet_size + 1; self.max_length]
207    }
208}
209
210crate::declare_variants! {
211    default ShortestCommonSuperstring => "num_strings ^ 2 * 2 ^ num_strings",
212}
213
214crate::register_brute_force! {
215    ShortestCommonSuperstring decode |problem: &ShortestCommonSuperstring, indices: Vec<usize>| indices.into_iter().map(|value| (value != problem.alphabet_size()).then_some(value)).collect(),
216}
217
218#[cfg(feature = "example-db")]
219pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
220    // Alphabet {0, 1}, strings [0,1] and [1,0].
221    // max_length = 2 + 2 = 4, search space = 3^4 = 81.
222    // Optimal SCSS length = 3, e.g. [0,1,0] padded to [0,1,0,2] ("010" contains
223    // both "01" and "10" as contiguous substrings).
224    vec![crate::example_db::specs::ModelExampleSpec {
225        id: "shortest_common_superstring",
226        instance: Box::new(ShortestCommonSuperstring::new(
227            2,
228            vec![vec![0, 1], vec![1, 0]],
229        )),
230        optimal_config: serde_json::json!(vec![Some(0), Some(1), Some(0), None]),
231        optimal_value: serde_json::json!(3),
232    }]
233}
234
235#[cfg(test)]
236#[path = "../../unit_tests/models/misc/shortest_common_superstring.rs"]
237mod tests;
problemreductions/models/misc/shortest_common_superstring.rs

problemreductions/models/misc/
shortest_common_superstring.rs
