HIGH-SPEED STRING PATTERN MATCHING METHOD USING LAYERED SHIFT TABLES

摘要

PURPOSE: A high-speed string pattern matching method using layered shift tables is provided to shift a search location by a maximum movable length in a text, thereby improving pattern detecting speed. CONSTITUTION: The length of the shortest pattern is saved as an LSP(Length of Shortest Pattern). Values corresponding to each index are initialized as LSPs. A hash table and a prefix table are generated. One pattern among N patterns is selected. Values of B shift tables are updated. The value of the hash table is saved as a pointer about the selected pattern.