linux-toradex.git/lib/ts_kmp.c, branch v5.4

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 152

2019-05-30T18:26:32+00:00

Based on 1 normalized pattern(s):

  this program is free software you can redistribute it and or modify
  it under the terms of the gnu general public license as published by
  the free software foundation either version 2 of the license or at
  your option any later version

extracted by the scancode license scanner the SPDX license identifier

  GPL-2.0-or-later

has been chosen to replace the boilerplate/reference in 3029 file(s).

Signed-off-by: Thomas Gleixner 
Reviewed-by: Allison Randal 
Cc: linux-spdx@vger.kernel.org
Link: https://lkml.kernel.org/r/20190527070032.746973796@linutronix.de
Signed-off-by: Greg Kroah-Hartman

textsearch: fix typos in library helpers

2017-10-22T02:14:07+00:00

Fix spellos (typos) in textsearch library helpers.

Signed-off-by: Randy Dunlap 
Signed-off-by: David S. Miller

textsearch: ts_kmp: support case insensitive searching in Knuth-Morris-Pratt algorithm

2008-07-08T09:38:09+00:00

Add support for case insensitive search to Knuth-Morris-Pratt algorithm.

Signed-off-by: Joonwoo Park 
Signed-off-by: Patrick McHardy 
Signed-off-by: David S. Miller

Remove obsolete #include

2006-06-30T17:25:36+00:00

Signed-off-by: Jörn Engel 
Signed-off-by: Adrian Bunk

[PATCH] gfp flags annotations - part 1

2005-10-08T22:00:57+00:00

 - added typedef unsigned int __nocast gfp_t;

 - replaced __nocast uses for gfp flags with gfp_t - it gives exactly
   the same warnings as far as sparse is concerned, doesn't change
   generated code (from gcc point of view we replaced unsigned int with
   typedef) and documents what's going on far better.

Signed-off-by: Al Viro 
Signed-off-by: Linus Torvalds

[TEXTSEARCH]: fix sparse gfp nocast warnings

2005-10-05T05:45:14+00:00

Fix nocast sparse warnings:
include/linux/textsearch.h:165:57: warning: implicit cast to nocast type

Signed-off-by: Randy Dunlap 
Signed-off-by: David S. Miller

[LIB]: Knuth-Morris-Pratt textsearch algorithm

2005-06-24T03:58:37+00:00

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