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

Published on 12 May 2024 09:40 PM
#Algol 68

How to resolve the algorithm Shortest common supersequence step by step in the ALGOL 68 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 ALGOL 68 programming language

Source code in the algol programming language

BEGIN
    PRIO SCS = 1;
    # returns the shortest common supersequence of x and y #
    OP   SCS = ( STRING x, y )STRING:
         IF   x = "" THEN y
         ELIF y = "" THEN x
         ELIF x[ LWB x ] = y[ LWB y ]
         THEN x[ LWB x ] + ( x[ LWB x + 1 : ] SCS y[ LWB y + 1 : ] )
         ELIF STRING x y sub = x SCS y[ LWB y + 1 : ];
              STRING x sub y = x[ LWB x + 1 : ] SCS y;
              INT x y sub size = ( UPB x y sub - LWB x y sub ) + 1;
              INT x sub y size = ( UPB x sub y - LWB x sub y ) + 1;
              x y sub size <= x sub y size
         THEN y[ LWB y ] + x y sub
         ELSE x[ LWB x ] + x sub y
         FI # SCS # ;
 
    print( ( "abcbdab" SCS "bdcaba", newline ) )
END

You may also check:How to resolve the algorithm Infinity step by step in the FutureBasic programming language
You may also check:How to resolve the algorithm Digital root step by step in the Sidef programming language
You may also check:How to resolve the algorithm Brazilian numbers step by step in the AWK programming language
You may also check:How to resolve the algorithm Compound data type step by step in the Maple programming language
You may also check:How to resolve the algorithm Pseudo-random numbers/Splitmix64 step by step in the Quackery programming language