Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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: -- (:)
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 Archives:
Bug reports: FAQ:
Beginner's list: