From df3fb93ad9ec0b20c785c0ad82d42d159a1af272 Mon Sep 17 00:00:00 2001 From: Thomas Graf Date: Thu, 23 Jun 2005 20:58:37 -0700 Subject: [LIB]: Knuth-Morris-Pratt textsearch algorithm Implements a linear-time string-matching algorithm due to Knuth, Morris, and Pratt [1]. Their algorithm avoids the explicit computation of the transition function DELTA altogether. Its matching time is O(n), for n being length(text), using just an auxiliary function PI[1..m], for m being length(pattern), precomputed from the pattern in time O(m). The array PI allows the transition function DELTA to be computed efficiently "on the fly" as needed. Roughly speaking, for any state "q" = 0,1,...,m and any character "a" in SIGMA, the value PI["q"] contains the information that is independent of "a" and is needed to compute DELTA("q", "a") [2]. Since the array PI has only m entries, whereas DELTA has O(m|SIGMA|) entries, we save a factor of |SIGMA| in the preprocessing time by computing PI rather than DELTA. [1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press [2] See finite automation theory Signed-off-by: Thomas Graf Signed-off-by: David S. Miller --- lib/Makefile | 1 + 1 file changed, 1 insertion(+) (limited to 'lib/Makefile') diff --git a/lib/Makefile b/lib/Makefile index 3e917436ad60..6cdb10f312df 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -37,6 +37,7 @@ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ lib-$(CONFIG_TEXTSEARCH) += textsearch.o +obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o hostprogs-y := gen_crc32table clean-files := crc32table.h -- cgit v1.2.3