• Thomas Graf's avatar
    [LIB]: Knuth-Morris-Pratt textsearch algorithm · df3fb93a
    Thomas Graf authored
    
    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: default avatarThomas Graf <tgraf@suug.ch>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    df3fb93a
Kconfig 1.79 KB
#
# Library configuration
#

menu "Library routines"

config CRC_CCITT
	tristate "CRC-CCITT functions"
	help
	  This option is provided for the case where no in-kernel-tree
	  modules require CRC-CCITT functions, but a module built outside
	  the kernel tree does. Such modules that use library CRC-CCITT
	  functions require M here.

config CRC32
	tristate "CRC32 functions"
	default y
	help
	  This option is provided for the case where no in-kernel-tree
	  modules require CRC32 functions, but a module built outside the
	  kernel tree does. Such modules that use library CRC32 functions
	  require M here.

config LIBCRC32C
	tristate "CRC32c (Castagnoli, et al) Cyclic Redundancy-Check"
	help
	  This option is provided for the case where no in-kernel-tree
	  modules require CRC32c functions, but a module built outside the
	  kernel tree does. Such modules that use library CRC32c functions
	  require M here.  See Castagnoli93.
	  Module will be libcrc32c.

#
# compression support is select'ed if needed
#
config ZLIB_INFLATE
	tristate

config ZLIB_DEFLATE
	tristate

#
# Generic allocator support is selected if needed
#
config GENERIC_ALLOCATOR
	boolean

#
# reed solomon support is select'ed if needed
#
config REED_SOLOMON
	tristate
	
config REED_SOLOMON_ENC8
	boolean

config REED_SOLOMON_DEC8
	boolean

config REED_SOLOMON_ENC16
	boolean

config REED_SOLOMON_DEC16
	boolean

config TEXTSEARCH
	boolean "Textsearch infrastructure"
	default y
	help
	  Say Y here if you want to provide a textsearch infrastructure
	  to other subsystems.

config TEXTSEARCH_KMP
	depends on TEXTSEARCH
	tristate "Knuth-Morris-Pratt"
	help
	  Say Y here if you want to be able to search text using the
	  Knuth-Morris-Pratt textsearch algorithm.

	  To compile this code as a module, choose M here: the
	  module will be called ts_kmp.

endmenu