Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: HenHanna <HenHanna@dev.null>
Newsgroups: comp.lang.lisp
Subject: Re: ( Substring function in Python, Lisp)  --  [Hijack]  contains  [hijk]
Date: Sun, 16 Feb 2025 18:33:58 +0000
Organization: novaBBS
Message-ID: <507d06f8062ea2f4dc1b226979b23021@www.novabbs.com>
References: <7513d4f4cf89bfd31edda3eb5ed84052@www.novabbs.com> <m3o6z2wvuh.fsf@leonis4.robolove.meer.net> <874j0ucpn1.fsf@nightsong.com> <m3r03xvqsn.fsf@leonis4.robolove.meer.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: i2pn2.org;
	logging-data="349056"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="4L8HabKtc1alsSAOmk7EUGDHKRhgGhC+6gJMfTsJB0A";
User-Agent: Rocksolid Light
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Face: P#KeQ)CUdd!==@fw~Ms1=,Hb`IWtb6:Mw)x3B=H1BfNC\lz?Nb&)M9}$>?'X7l;CuB}utlJ=PHsRBSG6X>dYZ$[>P]$~+`>@V6$t}hTLoQ7XC~W\>:`B3ALU]SH;d(\MEc}znW8m}-ma&yPFkJ2@KSQrz=!Y;><;6a>z6N+mt`ClCt.PAE<o+B$qjwejZSZ,w]^;vrdl24z5(pm={l,F10qRDF
X-Rslight-Site: $2y$10$IB1FFtieH9ll6gPohz0mHeZ7CxYGCHb5MY/qBk.fb/14Yd.lRL66y
X-Rslight-Posting-User: abae1fed5a82111a8790dc84735f550edb4392db
Bytes: 3319
Lines: 65

On Sun, 16 Feb 2025 15:43:20 +0000, Madhu wrote:

>
> * Paul Rubin <874j0ucpn1.fsf@nightsong.com> :
> Wrote on Sat, 15 Feb 2025 23:30:58 -0800:
>
>> Madhu <enometh@meer.net> writes:
>>> (intern-runs "hijacks")
>>> ;; => (0 . 3) - longest substr of length 3 at position 0
>>
>> I think that is not the question that was asked.
>
> oops.
>
>>  Although OP used the
>> term "substring", I think what was actually wanted is usually called a
>> subsequence, i.e. the characters in it don't have to be consecutive.  So
>> "hijacks" has HIJK which has length 4.  "firefighting" and
>> "prizefighting" both have EFGHI which has length 5.
>
> This becomes the Longest Increasing Subsequence Problem
>
> https://en.wikipedia.org/wiki/Longest_increasing_subsequence
>
> There are several good writeups about this on the web and lecture notes,
> much better than the implementation I once cobbled up from the wiki
>
> In common lisp:
> https://kaygun.github.io/clean/2014-10-26-longest_increasing_subsequence.html
> https://kaygun.github.io/clean/2015-10-26-longest_increasing_subsequence_revisited.html
>
> Using a suitable implementaion in a stupid way:
>
> (defun lca (string)
>   (map 'string 'code-char (lca::longest-inc-seq (map 'list 'char-code
>   string))))
>
> and running it on to extract into a hashtable with the keys as lcas
>
> (hash-table-count $h2)
> ;; => 20437
>
> (gethash "abcde" $h2)
> ("oxylabracidae" "cerambycidae" "bambocciade" "amoebicide" "ambuscade"
>  "absconded" "aborticide")
>
>
> (sort (mapcar (lambda (x) (cons (car x) (length (cdr x))))
> 	      (group2 (hash-keys $h2) :test #'= :key #'length))
>       #'< :key #'car)
>
> ;; "length of lca . number of words"
> ((2 . 241) (3 . 1596) (4 . 4833) (5 . 7024) (6 . 4961) (7 . 1545) (8 .
> 217)
>  (9 . 19) (10 . 1))



____________

>  (9 . 19) (10 . 1))


        wow....  I'd love to know what these Longest words are!

               who is the  (sole)  Grand winner?