Talk:String-searching algorithm
Page contents not supported in other languages.
 | This level-5 vital article is ratedStart-class on Wikipedia'scontent assessment scale.It is of interest to the followingWikiProjects: | |||||||||||||||||
| ||||||||||||||||||
Moved from article
These descriptions are insufficient!
Couldm somebody expand this entry ?
The "Finite Automata" link is entirely unhelpful, redirection to a page about finite state machines that has no information on string searching. --Furrykef 05:53, 29 Jun 2004 (UTC)
Some mention should be made of nasty character encodings that require special precautions when searching..........Plugwash11:35, 21 March 2006 (UTC)[reply]
Are the matching times listed in the comparison table factual at all?I see most of them have been marked as Θ(n). Is it just a stub? References?--Bisqwit11:46, 26 May 2006 (UTC)[reply]
Also, Θ() notation is used incorrectly, e.g. naive string searching is O(nm) -- when the two strings are the same, running time is Θ(n).
I've just fixed up the DFA imageImage:DFA search mommy.svg so that it renders again. It should be useful here as a demonstration of the simple DFA-based algorithm, but I'm not sure where to put it. Please assist.Dcoetzee03:57, 2 April 2007 (UTC)[reply]
Hi,
I would like to include the following link which has more algorithms for exact string searchEXACT STRING MATCHING ALGORITHMS.
Any other thoughts also welcome.
Thanksczar— Precedingunsigned comment added byCrxz0193 (talk •contribs)06:37, 23 April 2012 (UTC)[reply]
Alpha Skip Search was published at Combinatorial Pattern Matching 1998. The method appears to be optimal on average, for all alphabet sizes, and large M,N. Keys are sequences of logM letters. Preprocess the pattern into a lookup table with M-logM+1 keys of size logM (log base is alphabet size), encoding the key position in the pattern. Then skip through the text by length M-logM+1, building a logM sized key, and try to match the key in the lookup table. If a match is found, then try naively to match the pattern at the implied start position in the text. The expected run time of the algorithm is O((N/M + M)logM) for all alphabet sizes, including 2! Daniel Pehoushek24.33.70.144 (talk)18:45, 24 August 2014 (UTC)[reply]
This page seems to forget to mention the existence of thetwo-way string-matching algorithm, which provides a worst-case running time of O(n+m). This is the algorithm used by glibc's strstr() function, for example.EdSchouten (talk)10:18, 20 June 2016 (UTC)[reply]
Have just corrected where intro said strings are "formally" "vectors", and linked tovector_space. Perhaps someone merely accidentally linked to the wrong sense of "vector"; but it's incorrect as well as unhelpful. It was never mentioned again in the article, never had a connection described, and was unsourced). I changed it toarray, which is not without problems, but at least a common basic analogy, and I removed the "formal", because it the analogy does not approach formality (nor does it need to).
