Re: Re: [Caml-list] [CAML]:: efficient data structure for storing and searching int list list

[沈胜宇 <syshen@nudt.edu.cn>]

Dear Toby:

Thank you for your help.

But my problem is a little more difference from the substring searching problem with suffix tree.

In my problem, a list L1 is another list L2's sublist, is much more general that the substring problem.

For example, bcd is a substring of abcde, because bcd is continuely occur in abcde.

At the same time, bd is not a substring of abcde, because is is not continuesly in abcde.

But in my problem, a list b->d is a sub list of a->b->c->d->e.


So after reading the suffix tree introduction on wiki, I think it may not fit for my problem.

I also find that trie is more general than suffix, and can be used to handle my problem. but it is too general in the sense that it di not effiecently handle the case that two list with multiple(not just one) shared sublist.

For example, I first insert a list a->b->c->d->e->f into trie, and then I insert a->b->d->e into the trie.

the trie can not store the second shared sublist d->e in the same place, it can only store them like 
a->b->c->d->e->f
    ->d->e

So do you have more suggenhion on this ?

Shen

> -----原始邮件-----
> 发件人: "Toby Kelsey" <toby.kelsey@gmail.com>
> 发送时间: 2013-04-13 06:15:25 (星期六)
> 收件人: caml-list@inria.fr
> 抄送: syshen@nudt.edu.cn
> 主题: Re: [Caml-list] [CAML]:: efficient data structure for storing and searching int list list
> 
> On 12/04/13 15:36, 沈胜宇 wrote:
> > Dear all:
> > I have an int list list, whose name is LL
> > and I need to frequently decide whether a particular int list, whose name is L, is a sublist of an element of LL.
> > 
> > Is there any efficent data structure to do this?
> 
> A data structure useful for finding substrings quickly is the "suffix tree",
> this can be built in O(n) - for small alphabets - or O(n log n) time and
> substring searches take O(length substring) time. The suffix tree takes more
> space than the original string though. An int list can take the role of the
> string here.
> 
> Toby