From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 661367EE51 for ; Sat, 13 Apr 2013 09:00:26 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of syshen@nudt.edu.cn) identity=pra; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of syshen@nudt.edu.cn) identity=mailfrom; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@nudt.edu.cn) identity=helo; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="postmaster@nudt.edu.cn"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsIIAA4BaVE9uzYLdGdsb2JhbABQhmy+ESiBGw4BDBUIPIIfAQEFJ1IQBQQCGAQoAiE2BhMRh3EDDo8Jmn4IiEMNTIkRgR+LJYIgMweCKoEXA4kBjB6BY4t1hnGBQ4Ib X-IPAS-Result: AsIIAA4BaVE9uzYLdGdsb2JhbABQhmy+ESiBGw4BDBUIPIIfAQEFJ1IQBQQCGAQoAiE2BhMRh3EDDo8Jmn4IiEMNTIkRgR+LJYIgMweCKoEXA4kBjB6BY4t1hnGBQ4Ib X-IronPort-AV: E=Sophos;i="4.87,466,1363129200"; d="scan'208";a="13093278" Received: from mail.nudt.edu.cn (HELO nudt.edu.cn) ([61.187.54.11]) by mail2-smtp-roc.national.inria.fr with ESMTP; 13 Apr 2013 09:00:23 +0200 Received: by ajax-webmail-coremail.nudt.edu.cn (Coremail) ; Sat, 13 Apr 2013 14:57:11 +0800 (GMT+08:00) Date: Sat, 13 Apr 2013 14:57:11 +0800 (GMT+08:00) From: =?gbk?B?yfLKpNPu?= To: "Toby Kelsey" Cc: caml-list@inria.fr Message-ID: <3cfc99b5.468b.13e022ef3e8.Coremail.syshen@nudt.edu.cn> In-Reply-To: <5168877D.1090103@gmail.com> References: <58e60ce1.4599.13dfeacfdb3.Coremail.syshen@nudt.edu.cn> <5168877D.1090103@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=gbk Content-Transfer-Encoding: quoted-printable X-Originating-IP: [113.246.242.103] X-Priority: 3 X-Mailer: Coremail Webmail Server Version 4.0.5a build 20121109(20529.5019.5013) Copyright (c) 2002-2013 www.mailtech.cn nudt-out X-SendMailWithSms: false X-CM-TRANSID:AQAAf0CZ3kPJAWlRE6weAA--.4889W X-CM-SenderInfo: xv1vxvnq6q3vvwohv3gofq/1tbiAQAIE1C8Ui+78QABsA X-Coremail-Antispam: 1Ur529EdanIXcx71UUUUU7IcSsGvfJ3iIAIbVAYjsxI4VWxJw CS07vEb4IE77IF4wCS07vE1I0E4x80FVAKz4kxMIAIbVAFxVCaYxvI4VCIwcAKzIAtYxBI daVFxhVjvjDU= Subject: Re: Re: [Caml-list] [CAML]:: efficient data structure for storing and searching int list list Dear Toby: Thank you for your help. But my problem is a little more difference from the substring searching pro= blem 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 i= n abcde. At the same time, bd is not a substring of abcde, because is is not continu= esly 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 f= it for my problem. I also find that trie is more general than suffix, and can be used to handl= e 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 i= nsert 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=20 a->b->c->d->e->f ->d->e So do you have more suggenhion on this ? Shen > -----=D4=AD=CA=BC=D3=CA=BC=FE----- > =B7=A2=BC=FE=C8=CB: "Toby Kelsey" > =B7=A2=CB=CD=CA=B1=BC=E4: 2013-04-13 06:15:25 (=D0=C7=C6=DA=C1=F9) > =CA=D5=BC=FE=C8=CB: caml-list@inria.fr > =B3=AD=CB=CD: syshen@nudt.edu.cn > =D6=F7=CC=E2: Re: [Caml-list] [CAML]:: efficient data structure for stori= ng and searching int list list >=20 > On 12/04/13 15:36, =C9=F2=CA=A4=D3=EE 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 na= me is L, is a sublist of an element of LL. > >=20 > > Is there any efficent data structure to do this? >=20 > A data structure useful for finding substrings quickly is the "suffix tre= e", > 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 m= ore > space than the original string though. An int list can take the role of t= he > string here. >=20 > Toby