Searching for a set of correlated patterns |
| |
Authors: | Shmuel T Klein Riva Shalom Yair Kaufman |
| |
Institution: | aDepartment of Computer Science, Bar Ilan University, Ramat-Gan 52900, Israel |
| |
Abstract: | New algorithms for searching simultaneously for a set of patterns in a text are suggested, for the special case where these patterns are correlated and have a common substring. This is then extended to the case where it could be more profitable to look for more than a single overlap, and a problem related to the generalization of this idea is shown to be NP-complete. Experimental results suggest that for this particular application, the suggested algorithm yields significant improvements over previous methods. |
| |
Keywords: | Pattern matching Multiple patterns Overlaps NP-completeness |
本文献已被 ScienceDirect 等数据库收录! |