### Abstract

The Shortest Common Superstring (SCS) is a well studied problem, having a wide range of applications. In this paper we consider two problems closely related to it. First we define the Swapped Restricted Superstring(SRS) problem, where we are given a set S of n strings, s_{1}, s_{2}, ..., s_{n} , and a text T=t_{1} t_{2} ...t_{m} , and our goal is to find a swap permutation π: {1, ..., m} →{1, ..., m} to maximize the number of strings in S that are substrings of t_{π(1)} t_{π(2)}...t_{π(m)}. We then show that the SRS problem is NP-Complete. Afterwards, we consider a similar variant denoted SRSR, where our goal is to find a swap permutation π: {1, ..., m} →{1, ..., m} to maximize the total number of times that the strings of S appear in t _{π(1)} t_{π(2)}...t_{π(m)} (we can count the same string s_{i} as a substring of t_{π(1)} t _{π(2)}...t_{π(m)} more than once). For this problem, we present a polynomial time exact algorithm.

Original language | English |
---|---|

Title of host publication | String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Proceedings |

Pages | 270-278 |

Number of pages | 9 |

DOIs | |

Publication status | Published - Nov 24 2010 |

Event | 17th International Symposium on String Processing and Information Retrieval, SPIRE 2010 - Los Cabos, Mexico Duration: Oct 11 2010 → Oct 13 2010 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 6393 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 17th International Symposium on String Processing and Information Retrieval, SPIRE 2010 |
---|---|

Country | Mexico |

City | Los Cabos |

Period | 10/11/10 → 10/13/10 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Proceedings*(pp. 270-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6393 LNCS). https://doi.org/10.1007/978-3-642-16321-0_28