Inverse Pattern Matching |
| |
| Authors: | Amihood Amir Alberto Apostolico Moshe Lewenstein |
| |
| Institution: | aGeorgia Institute of Technology, Atlanta, Georgia, 30332;bDepartment of Mathematics and Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel;cPurdue University, West Lafayette, Indiana, 47907;dDipartimento di Elettronica e Informatica, Università di Padova, Via Gradenigo 6/A, 35131, Padua, Italy |
| |
| Abstract: | Let a textstringTofnsymbols from some alphabet Σ and an integerm < nbe given. A patternPof lengthmover Σ is sought such thatPminimizes (alternatively, maximizes) the total number of pairwise character mismatches generated whenPis compared with allm-character substrings ofT. Two additional variants of the problem are obtained by adding the constraint thatPbe (respectively, not be) a substring ofT. Efficient sequential algorithms are proposed in this paper for the problem and its variants. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
