From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x142.google.com (mail-lf1-x142.google.com [IPv6:2a00:1450:4864:20::142]) by sourceware.org (Postfix) with ESMTPS id 271EE3938398 for ; Fri, 11 Jun 2021 08:29:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 271EE3938398 Received: by mail-lf1-x142.google.com with SMTP id a1so7351772lfr.12 for ; Fri, 11 Jun 2021 01:29:02 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=3LT+fUmtjxXM8vCHkzEsv05rZmR/x2K878K5lt5T85Q=; b=gNaid4KZzYf937P/xhsqJzYkZDu1+b59F23DHKQMtaLlDuzPRqJx5EblJGXIwvTqGq hn+GHSRRouRfdmKNdTqAze1ZYbOWWEVSNYF4b8LArPa9de2VX7Xi4zhCYk7tVtx1vrAe CslcoJ9AOpszczKA889geiYK33TcE7wuoPKxTl+c2jg5FMROrp7TZcueGbKGJKPeomW9 kUcozfanAX5LKwJN5e+xFz4v0OhGy3RQp+Iz8QHQF1iBIQH9E7YYFwxCqIGQ7SN8hbPh ZljVPNHYqWgDTAkyq/rbWh23VR9UYi4qEY54Jot/DNAxi+IIbzO1xglWWLSRxZsHOqDT s+mw== X-Gm-Message-State: AOAM5305mc1xE0p+hrys9gYXk22WcxN6hTu8oSVg2MC9HU2VggbUVnxm wvrdfydR9AnnCW9k7cWp07GzMJPmUrcGAc5aiffXA6r2 X-Google-Smtp-Source: ABdhPJw0+JM/iSbZd/wMI4OuXOlZgquSIouba6OnkPqUe1YFsCtYX7U/1xv4UzD2oVp61og9MIHoJsp/iYWXJNYo254= X-Received: by 2002:ac2:5d6c:: with SMTP id h12mr2050566lft.354.1623400141011; Fri, 11 Jun 2021 01:29:01 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Amit Choudhary Date: Fri, 11 Jun 2021 13:58:48 +0530 Message-ID: Subject: Re: Fastest String Search Algorithm. To: Wilco Dijkstra Cc: GNU C Library X-Spam-Status: No, score=-0.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_ENVFROM_END_DIGIT, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org Content-Type: text/plain; charset="UTF-8" X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 11 Jun 2021 08:29:04 -0000 On Fri, Jun 11, 2021, 1:34 AM Amit Choudhary wrote: > I have now improved my algorithm by skipping some text based on a > preprocessed array on pattern. > > Now, my algorithm is faster than strstr() for needles of 1 KB and above. > > But I am not sure if you guys are still interested. > > Anyways, I am attaching my program (bzipped2). > > Regards, > Amit > This version of my program has a bug. If needed, I can send the fixed version. Also, as it was pointed out that long needles are not used in real world but this is not the case. Antivirus software compares long needles (may be greater than 4 KB also) to search for virus signature in packets. And this is done everyday, many many times, and that too on millions of computers everyday. Regards, Amit