### 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 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Pages | 270-278 |

Number of pages | 9 |

Volume | 6393 LNCS |

DOIs | |

Publication status | Published - 2010 |

Externally published | Yes |

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) | 03029743 |

ISSN (Electronic) | 16113349 |

### 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

- Computer Science(all)
- Theoretical Computer Science

### Cite this

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(Vol. 6393 LNCS, 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

**On shortest common superstring and swap permutations.** / Gotthilf, Zvi; Lewenstein, Moshe; Popa, Alexandru.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

}

TY - GEN

T1 - On shortest common superstring and swap permutations

AU - Gotthilf, Zvi

AU - Lewenstein, Moshe

AU - Popa, Alexandru

PY - 2010

Y1 - 2010

N2 - 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, s1, s2, ..., sn , and a text T=t1 t2 ...tm , 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 si as a substring of tπ(1) t π(2)...tπ(m) more than once). For this problem, we present a polynomial time exact algorithm.

AB - 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, s1, s2, ..., sn , and a text T=t1 t2 ...tm , 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 si as a substring of tπ(1) t π(2)...tπ(m) more than once). For this problem, we present a polynomial time exact algorithm.

UR - http://www.scopus.com/inward/record.url?scp=78449306564&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78449306564&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-16321-0_28

DO - 10.1007/978-3-642-16321-0_28

M3 - Conference contribution

SN - 3642163203

SN - 9783642163203

VL - 6393 LNCS

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

SP - 270

EP - 278

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

ER -