How to resolve the algorithm Longest common substring step by step in the Racket programming language

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Longest common substring step by step in the Racket programming language

Table of Contents

Problem Statement

Write a function that returns the longest common substring of two strings. Use it within a program that demonstrates sample output from the function, which will consist of the longest common substring between "thisisatest" and "testing123testing". Note that substrings are consecutive characters within a string.   This distinguishes them from subsequences, which is any sequence of characters within a string, even if there are extraneous characters in between them. Hence, the longest common subsequence between "thisisatest" and "testing123testing" is "tsitest", whereas the longest common substring is just "test".

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Longest common substring step by step in the Racket programming language

Source code in the racket programming language

#lang typed/racket
(: lcs (String String -> String))
(define (lcs a b)
  (: all-substrings# (String -> (HashTable String Boolean)))
  (define (all-substrings# str)
    (define l (string-length str))
    (for*/hash : (HashTable String Boolean)
      ((s (in-range 0 l)) (e (in-range (add1 s) (add1 l))))
      (values (substring str s e) #t)))
  
  (define a# (all-substrings# a))
  
  (define b# (all-substrings# b))
  
  (define-values (s l)
    (for/fold : (Values String Nonnegative-Integer)
    ((s "") (l : Nonnegative-Integer 0))
    ((a_ (in-hash-keys a#))
     #:when (and (> (string-length a_) l) (hash-ref b# a_ #f)))
    (values a_ (string-length a_))))
  
  s)

(module+ test
  ("thisisatest" . lcs . "testing123testing"))

You may also check:How to resolve the algorithm Reverse a string step by step in the Nemerle programming language
You may also check:How to resolve the algorithm Null object step by step in the Perl programming language
You may also check:How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the zkl programming language
You may also check:How to resolve the algorithm Arrays step by step in the C programming language
You may also check:How to resolve the algorithm Grayscale image step by step in the Factor programming language