<p>Searching in a string that changes often, and looking for a set of words, I would use <a href="http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm" rel="nofollow">Aho-Corasick</a>, an extension of KMP that builds a tree (based on the set of words) and looks for the words in parallel. </p>

CC BY-SA 3.0
2012-11-29T23:03:58.043Z
2012-11-29T23:03:58.043Z
Hendrik Jan
<p>A convenient way would be to use the KMP algorithm with hash filtering.
I understand that your list of string can change anytime so preprocessing may be irrelevant. (although there exist dynamic preprocessing methods).</p>

<p>I would suggest to assign each string from your list an hash number (if it is integer it is a number between 0 to 2^32) and when you got a query for some string s, you will calculate h=hash(s) [hash(x) could be a function that summarize the values of the characters in string x]. Now you can search for matches only on the strings in the list that their hash value = hash(s).</p>

<p>Clearly the number of required search will reduced.</p>

<p>Now for each string in the list such that it's hash = hash(s) make a search using KMP which give you a result in time O(n+m) [n is the text and m is the pattern lengthes] so if there k texts remained after the filtering you will get the result in time O(k(n+m)).</p>

CC BY-SA 3.0
2012-11-27T04:33:10.200Z
sorry. it is 'hash'
Bush
CC BY-SA 3.0
2012-11-26T18:10:14.183Z
2012-11-27T04:32:49.497Z
2012-11-27T04:32:49.497Z
Bush
<p>Well the scenario is clear now.</p>

<p>My solution is Generalized Suffix tree. You will need to learn a bit about it before implementation. (I didn't find full 'plug-n-play' implementation in the internet but maybe you'll find).</p>

<p>Let's say that the length of all the strings in the list together is N and the pattern you are searching is of length M, the solution will require a processing time of O(N) and query time of O(M + #occ). #occ is the number of occurences found by the query.</p>

<p>There are many references in the interner so I will not copy all of them.
You can see what's GST in <a href="http://en.wikipedia.org/wiki/Generalized_suffix_tree" rel="nofollow">http://en.wikipedia.org/wiki/Generalized_suffix_tree</a>
And some article of how to build it in linear time in <a href="http://www.drdobbs.com/database/a-practical-suffix-tree-implementation/184404184" rel="nofollow">http://www.drdobbs.com/database/a-practical-suffix-tree-implementation/184404184</a></p>

CC BY-SA 3.0
2012-11-27T04:54:21.810Z
2012-11-27T05:28:32.850Z
2012-11-27T05:28:32.850Z
Bush
<p>I have  a large number of long strings, and I need to search them for a given list of words  as fast as reasonably possible. (Neither the strings nor the words are constants)
I learned that I can preprocess the strings that I'm going to be searching for my words by building a suffix array and  an lcp array, and that I should be able to make the searches faster by doing so.
I was wondering, however, if I could preprocess the wordlist in some way as well. It is quite possible that the words will have common parts. I would like to build something like a "word genealogy tree" (or another structure that would achieve the same effect ) where the  substring that can be found in a family of words would be at the top and which would then branch down (for both the prefixes and the suffixes of the ancestor) as the descendants would go. 
I imagine that this would allow me to discard whole branches or trees quickly if an ancestral node failed to match.
Could you please direct me to a suitable strategy that would help me achieve my goal (in this or any other reasonably efficient way)?
Note: I can't really make use of much existing code (can make use of ideas, though). I'm pretty much limited to the standard c library.</p>

CC BY-SA 3.0
2012-11-26T19:01:37.063Z
Note 2: I wrote that neither the strings nor the words are constants. This is inaccurate, I'm sorry for not putting it better.

Both the strings and the words are supplied from outside for each run of the program. After that they remain constant.

Each run of the program should go as follows:
1) read strings
2) read words
3) preprocess strings
4) (?) preprocess words
5) a) find all occurences of each word in each string and b) delete them (or achieve the same thing that a) & b) do without actually doing it separately)
Petr Skocik
<string-search>
Search a string for a list of words
Petr Skocik
# Search a string for a list of words

(Asked by: username_0 on 2012-11-26)

I have a large number of long strings, and I need to search them for a given list of words as fast as reasonably possible. (Neither the strings nor the words are constants)
I learned that I can preprocess the strings that I'm going to be searching for my words by building a suffix array and an lcp array, and that I should be able to make the searches faster by doing so.
I was wondering, however, if I could preprocess the wordlist in some way as well. It is quite possible that the words will have common parts. I would like to build something like a "word genealogy tree" (or another structure that would achieve the same effect ) where the substring that can be found in a family of words would be at the top and which would then branch down (for both the prefixes and the suffixes of the ancestor) as the descendants would go.
I imagine that this would allow me to discard whole branches or trees quickly if an ancestral node failed to match.
Could you please direct me to a suitable strategy that would help me achieve my goal (in this or any other reasonably efficient way)?
Note: I can't really make use of much existing code (can make use of ideas, though). I'm pretty much limited to the standard c library.

**Tags:** string-search
> **Comments:**
> **username_0**: Note 2: I wrote that neither the strings nor the words are constants. This is inaccurate, I'm sorry for not putting it better.  Both the strings and the words are supplied from outside for each run of the program. After that they remain constant.  Each run of the program should go as follows: 1) read strings 2) read words 3) preprocess strings 4) (?) preprocess words 5) a) find all occurences of each word in each string and b) delete them (or achieve the same thing that a) & b) do without actually doing it separately)  

---

## 3 answers

### Answer by username_1 on 2012-11-29. Score: 2

Searching in a string that changes often, and looking for a set of words, I would use [Aho-Corasick](http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm), an extension of KMP that builds a tree (based on the set of words) and looks for the words in parallel.


---

### Answer by username_2 on 2012-11-26. Score: 1

A convenient way would be to use the KMP algorithm with hash filtering.
I understand that your list of string can change anytime so preprocessing may be irrelevant. (although there exist dynamic preprocessing methods).

I would suggest to assign each string from your list an hash number (if it is integer it is a number between 0 to 2^32) and when you got a query for some string s, you will calculate h=hash(s) [hash(x) could be a function that summarize the values of the characters in string x]. Now you can search for matches only on the strings in the list that their hash value = hash(s).

Clearly the number of required search will reduced.

Now for each string in the list such that it's hash = hash(s) make a search using KMP which give you a result in time O(n+m) [n is the text and m is the pattern lengthes] so if there k texts remained after the filtering you will get the result in time O(k(n+m)).

> **Comments:**
> **username_2**: sorry. it is 'hash'  

---

### Answer by username_2 on 2012-11-27. Score: 0

Well the scenario is clear now.

My solution is Generalized Suffix tree. You will need to learn a bit about it before implementation. (I didn't find full 'plug-n-play' implementation in the internet but maybe you'll find).

Let's say that the length of all the strings in the list together is N and the pattern you are searching is of length M, the solution will require a processing time of O(N) and query time of O(M + #occ). #occ is the number of occurences found by the query.

There are many references in the interner so I will not copy all of them.
You can see what's GST in <http://en.wikipedia.org/wiki/Generalized_suffix_tree>
And some article of how to build it in linear time in <http://www.drdobbs.com/database/a-practical-suffix-tree-implementation/184404184>


---

