diff options
| author | Thomas Graf <tgraf@suug.ch> | 2005-06-23 20:58:37 -0700 |
|---|---|---|
| committer | David S. Miller <davem@davemloft.net> | 2005-06-23 20:58:37 -0700 |
| commit | df3fb93ad9ec0b20c785c0ad82d42d159a1af272 (patch) | |
| tree | e29ba25f55cb77e24310999a949b433e98d7656e /lib/Kconfig | |
| parent | 2de4ff7bd658c97fb357efa3095a509674dacb5a (diff) | |
| download | linux-3.10-df3fb93ad9ec0b20c785c0ad82d42d159a1af272.tar.gz linux-3.10-df3fb93ad9ec0b20c785c0ad82d42d159a1af272.tar.bz2 linux-3.10-df3fb93ad9ec0b20c785c0ad82d42d159a1af272.zip | |
[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 <tgraf@suug.ch>
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'lib/Kconfig')
| -rw-r--r-- | lib/Kconfig | 10 |
1 files changed, 10 insertions, 0 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 5bc2d523e6d..16b8fa2175e 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -70,4 +70,14 @@ config TEXTSEARCH 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 |