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

Published on 12 May 2024 09:40 PM
#Lobster

How to resolve the algorithm Longest common substring step by step in the Lobster 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 Lobster programming language

Source code in the lobster programming language

import std
def lcs(a, b) -> string:
    var out = ""
    let lengths = map(a.length * b.length): 0
    var greatestLength = 0
    for(a) x, i:
        for(b) y, j:
            if x == y:
                if i == 0 or j == 0:
                    lengths[i * b.length + j] = 1
                else:
                    lengths[i * b.length + j] = lengths[(i-1) * b.length + j - 1] + 1
                if lengths[i * b.length + j] > greatestLength:
                    greatestLength = lengths[i * b.length + j]
                    out = a.substring(i - greatestLength + 1, greatestLength)
    return out

import std
def lcs2(a, b) -> string:
    var out = ""
    let lengths = map(b.length): map(a.length): 0
    var greatestLength = 0
    for(a) x, i:
        for(b) y, j:
            if x == y:
                if i == 0 or j == 0:
                    lengths[j][i] = 1
                else:
                    lengths[j][i] = lengths[j-1][i-1] + 1
                if lengths[j][i] > greatestLength:
                    greatestLength = lengths[j][i]
                    out = a.substring(i - greatestLength + 1, greatestLength)
    return out

You may also check:How to resolve the algorithm Here document step by step in the F# programming language
You may also check:How to resolve the algorithm Bulls and cows step by step in the Quackery programming language
You may also check:How to resolve the algorithm Price fraction step by step in the Elixir programming language
You may also check:How to resolve the algorithm Fusc sequence step by step in the Wren programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the K programming language