Linear Nondeterministic Dawg String Matching Algorithm

摘要

The exact string matching problem is to find all the occurrences of a given pattern x = x_1 x_2 ··· x_m in a large text y = y_1 y_2 ··· y_n, where both x and y are sequences of symbols drawn from a finite character set Σ of size σ. Various good solutions have been presented during years. Among them, BNDM is a very efficient and flexible algorithm. It simulates the BDM algorithm using bit-parallelism. BNDM first builds a mask table B for each symbol c. The mask in B[c] has the i-th bit set if and only if x_i = c. The search state is kept in a computer word L = L_m ··· L_1, where the bit L_i at iteration l is set if and only if x_i ··· x_(i+l-1) = y_(j-l+1) ··· y_j, where j is the end position of the current window. Each time we position the window in the text we initialize L = 1~m and scan the window backward.