How to resolve the algorithm Shortest common supersequence step by step in the Racket programming language

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Shortest common supersequence step by step in the Racket programming language

Table of Contents

Problem Statement

The   shortest common supersequence   is a problem closely related to the   longest common subsequence,   which you can use as an external function for this task.

Given two strings

u

{\displaystyle u}

and

v

{\displaystyle v}

, find the shortest possible sequence

s

{\displaystyle s}

, which is the shortest common super-sequence of

u

{\displaystyle u}

and

v

{\displaystyle v}

where both

u

{\displaystyle u}

and

v

{\displaystyle v}

are a subsequence of

s

{\displaystyle s}

. Defined as such,

s

{\displaystyle s}

is not necessarily unique. Demonstrate this by printing

s

{\displaystyle s}

where

u

{\displaystyle u=}

“abcbdab” and

v

{\displaystyle v=}

“bdcaba”.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Shortest common supersequence step by step in the Racket programming language

Source code in the racket programming language

#lang racket

(struct link (len letters))

(define (link-add li n letter)
  (link (+ n (link-len li)) 
        (cons letter (link-letters li))))

(define (memoize f)
  (local ([define table (make-hash)])
    (lambda args
      (dict-ref! table args (λ () (apply f args))))))

(define scs/list
  (memoize 
   (lambda (x y)
     (cond
       [(null? x)
        (link (length y) y)]
       [(null? y)
        (link (length x) x)]
       [(eq? (car x) (car y))
        (link-add (scs/list (cdr x) (cdr y)) 1 (car x))]
       [(<= (link-len (scs/list x (cdr y)))
            (link-len (scs/list (cdr x) y)))
        (link-add (scs/list x (cdr y)) 1 (car y))]
       [else
        (link-add (scs/list (cdr x) y) 1 (car x))]))))

(define (scs x y)
  (list->string (link-letters (scs/list (string->list x) (string->list y)))))

(scs "abcbdab" "bdcaba")

You may also check:How to resolve the algorithm Teacup rim text step by step in the Phix programming language
You may also check:How to resolve the algorithm Luhn test of credit card numbers step by step in the Haskell programming language
You may also check:How to resolve the algorithm Deal cards for FreeCell step by step in the Groovy programming language
You may also check:How to resolve the algorithm Bitmap/Bézier curves/Quadratic step by step in the Action! programming language
You may also check:How to resolve the algorithm Associative array/Creation step by step in the OxygenBasic programming language