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)]
66#[serde(try_from = "ShortestCommonSuperstringData")]
67pub struct ShortestCommonSuperstring {
68    alphabet_size: usize,
69    strings: Vec<Vec<usize>>,
70    max_length: usize,
71}
72
73#[derive(Deserialize)]
74struct ShortestCommonSuperstringData {
75    alphabet_size: usize,
76    strings: Vec<Vec<usize>>,
77}
78
79impl TryFrom<ShortestCommonSuperstringData> for ShortestCommonSuperstring {
80    type Error = crate::registry::ConstructionError;
81
82    fn try_from(data: ShortestCommonSuperstringData) -> Result<Self, Self::Error> {
83        Self::try_new(data.alphabet_size, data.strings)
84    }
85}
86
87impl ShortestCommonSuperstring {
88    /// Create a new ShortestCommonSuperstring instance.
89    ///
90    /// `max_length` is computed automatically as the sum of all input string
91    /// lengths (the trivial upper bound: concatenation with no overlap).
92    ///
93    /// # Panics
94    ///
95    /// Panics if `strings` is empty, or if `alphabet_size` is 0 and any input
96    /// string is non-empty.
97    pub fn new(alphabet_size: usize, strings: Vec<Vec<usize>>) -> Self {
98        Self::try_new(alphabet_size, strings).unwrap_or_else(|error| panic!("{error}"))
99    }
100
101    fn try_new(
102        alphabet_size: usize,
103        strings: Vec<Vec<usize>>,
104    ) -> Result<Self, crate::registry::ConstructionError> {
105        if strings.is_empty() {
106            return Err("must have at least one string".into());
107        }
108        let max_length = strings.iter().try_fold(0usize, |total, string| {
109            total
110                .checked_add(string.len())
111                .ok_or("maximum string length overflows usize")
112        })?;
113        if !(alphabet_size > 0 || strings.iter().all(|s| s.is_empty())) {
114            return Err("alphabet_size must be > 0 when any input string is non-empty".into());
115        }
116        Ok(Self {
117            alphabet_size,
118            strings,
119            max_length,
120        })
121    }
122
123    /// Returns the alphabet size.
124    pub fn alphabet_size(&self) -> usize {
125        self.alphabet_size
126    }
127
128    /// Returns the input strings.
129    pub fn strings(&self) -> &[Vec<usize>] {
130        &self.strings
131    }
132
133    /// Returns the maximum possible superstring length.
134    pub fn max_length(&self) -> usize {
135        self.max_length
136    }
137
138    /// Returns the number of input strings.
139    pub fn num_strings(&self) -> usize {
140        self.strings.len()
141    }
142
143    /// Returns the total length of all input strings.
144    pub fn total_length(&self) -> usize {
145        self.strings.iter().map(|s| s.len()).sum()
146    }
147}
148
149/// Check whether `needle` appears as a contiguous substring of `haystack`.
150fn is_substring(needle: &[usize], haystack: &[usize]) -> bool {
151    if needle.is_empty() {
152        return true;
153    }
154    if needle.len() > haystack.len() {
155        return false;
156    }
157    haystack
158        .windows(needle.len())
159        .any(|window| window == needle)
160}
161
162impl Problem for ShortestCommonSuperstring {
163    const NAME: &'static str = "ShortestCommonSuperstring";
164    type Solution = Vec<Option<usize>>;
165    type Value = Min<i64>;
166
167    crate::problem_parameters![
168        ("alphabet_size", alphabet_size),
169        ("num_strings", num_strings),
170        ("max_length", max_length),
171        ("total_length", total_length),
172    ];
173
174    fn variant() -> Vec<(&'static str, &'static str)> {
175        crate::variant_params![]
176    }
177
178    fn evaluate(
179        &self,
180        config: &Self::Solution,
181    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
182        if config.len() != self.max_length {
183            return Err(crate::traits::EvaluationError::InvalidConfiguration(
184                "superstring representation length does not match the bound".into(),
185            ));
186        }
187        if config
188            .iter()
189            .any(|symbol| symbol.is_some_and(|value| value >= self.alphabet_size))
190        {
191            return Err(crate::traits::EvaluationError::InvalidConfiguration(
192                "superstring contains an out-of-range symbol".into(),
193            ));
194        }
195        let config = config
196            .iter()
197            .map(|symbol| symbol.unwrap_or(self.alphabet_size))
198            .collect::<Vec<_>>();
199        Ok({
200            let pad = self.alphabet_size;
201
202            // Find effective length = index of first padding symbol
203            let effective_length = config
204                .iter()
205                .position(|&v| v == pad)
206                .unwrap_or(self.max_length);
207
208            // Verify all positions after first padding are also padding (no interleaved padding)
209            for &v in &config[effective_length..] {
210                if v != pad {
211                    return Ok(Min(None));
212                }
213            }
214
215            let prefix = &config[..effective_length];
216
217            // Check every input string appears as a contiguous substring of the prefix
218            if !self.strings.iter().all(|s| is_substring(s, prefix)) {
219                return Ok(Min(None));
220            }
221
222            Min(Some(i64::try_from(effective_length).map_err(|_| {
223                crate::traits::EvaluationError::IntegerOverflow(
224                    "converting superstring length to i64".into(),
225                )
226            })?))
227        })
228    }
229}
230
231impl crate::solvers::BruteForceProblem for ShortestCommonSuperstring {
232    fn dimensions(&self) -> Vec<usize> {
233        vec![self.alphabet_size + 1; self.max_length]
234    }
235}
236
237crate::declare_variants! {
238    default ShortestCommonSuperstring => "num_strings ^ 2 * 2 ^ num_strings",
239}
240
241crate::register_brute_force! {
242    ShortestCommonSuperstring decode |problem: &ShortestCommonSuperstring, indices: Vec<usize>| indices.into_iter().map(|value| (value != problem.alphabet_size()).then_some(value)).collect(),
243}
244
245#[cfg(feature = "example-db")]
246pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
247    // Alphabet {0, 1}, strings [0,1] and [1,0].
248    // max_length = 2 + 2 = 4, search space = 3^4 = 81.
249    // Optimal SCSS length = 3, e.g. [0,1,0] padded to [0,1,0,2] ("010" contains
250    // both "01" and "10" as contiguous substrings).
251    vec![crate::example_db::specs::ModelExampleSpec {
252        id: "shortest_common_superstring",
253        instance: Box::new(ShortestCommonSuperstring::new(
254            2,
255            vec![vec![0, 1], vec![1, 0]],
256        )),
257        optimal_config: serde_json::json!(vec![Some(0), Some(1), Some(0), None]),
258        optimal_value: serde_json::json!(3),
259    }]
260}
261
262#[cfg(test)]
263#[path = "../../unit_tests/models/misc/shortest_common_superstring.rs"]
264mod tests;
problemreductions/models/misc/shortest_common_superstring.rs

problemreductions/models/misc/
shortest_common_superstring.rs
