English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: [Caml-list] Substring search on an array of strings
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-06-25 (17:07)
From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...>
Subject: Re: [Caml-list] Substring search on an array of strings

> 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