From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 428D07EE51 for ; Sat, 13 Apr 2013 00:15:32 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of toby.kelsey@gmail.com) identity=pra; client-ip=209.85.214.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="toby.kelsey@gmail.com"; x-sender="toby.kelsey@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of toby.kelsey@gmail.com designates 209.85.214.50 as permitted sender) identity=mailfrom; client-ip=209.85.214.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="toby.kelsey@gmail.com"; x-sender="toby.kelsey@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-bk0-f50.google.com) identity=helo; client-ip=209.85.214.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="toby.kelsey@gmail.com"; x-sender="postmaster@mail-bk0-f50.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aj4CABKHaFHRVdYyk2dsb2JhbABQhiNHvjaBDBYOAQEBAQcLCwkUBCSCHwEBBTIBDQEbHAEBAwwGAwILDQQFFg0CCQMCAQIBEREBBQEcEwEHAQGHfQEDDwSPEo8ki1oITYJ7hE4KGScNWYh+AQUMgRONeAcWghSBFwOXAoYFiSo/gniBNw X-IPAS-Result: Aj4CABKHaFHRVdYyk2dsb2JhbABQhiNHvjaBDBYOAQEBAQcLCwkUBCSCHwEBBTIBDQEbHAEBAwwGAwILDQQFFg0CCQMCAQIBEREBBQEcEwEHAQGHfQEDDwSPEo8ki1oITYJ7hE4KGScNWYh+AQUMgRONeAcWghSBFwOXAoYFiSo/gniBNw X-IronPort-AV: E=Sophos;i="4.87,465,1363129200"; d="scan'208";a="10798786" Received: from mail-bk0-f50.google.com ([209.85.214.50]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 13 Apr 2013 00:15:30 +0200 Received: by mail-bk0-f50.google.com with SMTP id jg1so1570366bkc.23 for ; Fri, 12 Apr 2013 15:15:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:message-id:date:from:user-agent:mime-version:to:cc :subject:references:in-reply-to:content-type :content-transfer-encoding; bh=sslo1kjeWrbRDu+QJL8Fc56h0s7/a1im/ZoktNF1g5E=; b=G7cImh0urBJIUECdWfklQFFB2m8NabeNql/1sNoXXjwXB2BVGuo1kW7M+sqo/t7gyQ lvblB5/VNYMBnQW+DEEo7yHSZTzav7PIc4EIH5R9kuULcQjhJSUP6WLm9wiJ352it7g+ DLiO4OUoUZ31SlNCVsUI9qs/1GtdAqnQ1SZ4EzpoL53IriNqaJxIY2h6jVmKRVhQ7Vof fF0Msmq1Yd4Ooy2BgfERcILx3nvupn5UVlSUJ5gRjaENkZTM0QOEON4kXFFnJgSbPJb3 Aqdi0lLsPiOwOd641dZ+X40VGYyJW1n/7e83svpR7UV03h+H1wMxxeL82gowh+GK/wZb D1rg== X-Received: by 10.205.33.81 with SMTP id sn17mr4812823bkb.53.1365804929683; Fri, 12 Apr 2013 15:15:29 -0700 (PDT) Received: from [192.168.1.65] (94-193-173-247.zone7.bethere.co.uk. [94.193.173.247]) by mx.google.com with ESMTPS id fy17sm4609417bkc.6.2013.04.12.15.15.27 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 12 Apr 2013 15:15:28 -0700 (PDT) Message-ID: <5168877D.1090103@gmail.com> Date: Fri, 12 Apr 2013 23:15:25 +0100 From: Toby Kelsey User-Agent: Mozilla/5.0 (X11; Linux i686; rv:17.0) Gecko/20130330 Thunderbird/17.0.5 MIME-Version: 1.0 To: caml-list@inria.fr CC: syshen@nudt.edu.cn References: <58e60ce1.4599.13dfeacfdb3.Coremail.syshen@nudt.edu.cn> In-Reply-To: <58e60ce1.4599.13dfeacfdb3.Coremail.syshen@nudt.edu.cn> Content-Type: text/plain; charset=gbk Content-Transfer-Encoding: 8bit Subject: 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