Re: [Caml-list] Substring search on an array of strings

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

> If you need to find every substring in every element of the array
> then, yes, you'll have to look at every element of the array to see
> if that substring appears or not in it.

No, or at least only in the worst case.

In the same way the Knuth-Morris-Pratt suffix automaton allows you not
to search for every position in a string if it is not necessary, a
specific procedure for searching in an array of strings could avoid
you searching on every string.

I will try to give some simple examples to get some intuition :

- Suppose there are many strings that only contains a few different
letters. Then you could build first a map from subsets of the alphabet
to string indexes and only search in those strings

- Suppose that the strings have a particular pattern (say
"processortype.memory.operatingsystem"). Then you could build indexes
on every processor type, memory or operating system, and search only
in the corresponding strings


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners