License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2021.9
URN: urn:nbn:de:0030-drops-139604
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13960/
Bernardini, Giulia ;
Marchetti-Spaccamela, Alberto ;
Pissis, Solon P. ;
Stougie, Leen ;
Sweering, Michelle
Constructing Strings Avoiding Forbidden Substrings
Abstract
We consider the problem of constructing strings over an alphabet Σ that start with a given prefix u, end with a given suffix v, and avoid occurrences of a given set of forbidden substrings. In the decision version of the problem, given a set S_k of forbidden substrings, each of length k, over Σ, we are asked to decide whether there exists a string x over Σ such that u is a prefix of x, v is a suffix of x, and no s ∈ S_k occurs in x. Our first result is an ?(|u|+|v|+k|S_k|)-time algorithm to decide this problem. In the more general optimization version of the problem, given a set S of forbidden arbitrary-length substrings over Σ, we are asked to construct a shortest string x over Σ such that u is a prefix of x, v is a suffix of x, and no s ∈ S occurs in x. Our second result is an ?(|u|+|v|+||S||⋅|Σ|)-time algorithm to solve this problem, where ||S|| denotes the total length of the elements of S.
Interestingly, our results can be directly applied to solve the reachability and shortest path problems in complete de Bruijn graphs in the presence of forbidden edges or of forbidden paths.
Our algorithms are motivated by data privacy, and in particular, by the data sanitization process. In the context of strings, sanitization consists in hiding forbidden substrings from a given string by introducing the least amount of spurious information. We consider the following problem. Given a string w of length n over Σ, an integer k, and a set S_k of forbidden substrings, each of length k, over Σ, construct a shortest string y over Σ such that no s ∈ S_k occurs in y and the sequence of all other length-k fragments occurring in w is a subsequence of the sequence of the length-k fragments occurring in y. Our third result is an ?(nk|S_k|⋅|Σ|)-time algorithm to solve this problem.
BibTeX - Entry
@InProceedings{bernardini_et_al:LIPIcs.CPM.2021.9,
author = {Bernardini, Giulia and Marchetti-Spaccamela, Alberto and Pissis, Solon P. and Stougie, Leen and Sweering, Michelle},
title = {{Constructing Strings Avoiding Forbidden Substrings}},
booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
pages = {9:1--9:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-186-3},
ISSN = {1868-8969},
year = {2021},
volume = {191},
editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13960},
URN = {urn:nbn:de:0030-drops-139604},
doi = {10.4230/LIPIcs.CPM.2021.9},
annote = {Keywords: string algorithms, forbidden strings, de Bruijn graphs, data sanitization}
}
|
Keywords: |
|
string algorithms, forbidden strings, de Bruijn graphs, data sanitization |
|
Collection: |
|
32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.06.2021 |
