Longest Palindromic Substring in Euphoria

Published on 26 February 2023 (Updated: 26 February 2023)

Welcome to the Longest Palindromic Substring in Euphoria page! Here, you'll find the source code for this program as well as a description of how the program works.

Current Solution

include std/io.e
include std/types.e
include std/text.e

-- Find longest palindromic string using matching array
-- Source: https://www.geeksforgeeks.org/longest-palindromic-substring-using-dynamic-programming/
function longest_palindromic_substring(sequence s)
    -- Initialize array indicating whether there is a character match
    -- between two characters to indicate that nothing matches
    integer n = length(s)
    sequence matches = repeat(repeat(FALSE, n), n)

    -- Indicate all length 1 strings match
    for i = 1 to n
        matches[i][i] = TRUE
    end for

    -- Convert string to lowercase
    sequence t = lower(s)

    -- Find all length 2 matches
    integer start = 1
    integer max_len = 1
    for i = 1 to n - 1
        if t[i] = t[i + 1]
            matches[i][i+1] = TRUE
            if max_len < 2
                start = i
                max_len = 2
            end if
        end if
    end for

    -- Find all length 3 or higher matches
    integer j
    for len = 3 to n
        -- Loop through each starting character
        for i = 1 to n - len + 1
            -- If match for one character in from start and end characters
            -- and start and end characters match, set match for start and
            -- end characters, and update max length
            j = i + len - 1
            if matches[i + 1][j - 1] and t[i] = t[j]
                matches[i][j] = TRUE
                if len > max_len
                    start = i
                    max_len = len
                end if
            end if
        end for
    end for

    return s[start..start + max_len - 1]
end function

procedure usage()
    puts(STDOUT, "Usage: please provide a string that contains at least one palindrome\n")
end procedure

-- Error if 1st command-line argument is missing is empty
sequence argv = command_line()
if length(argv) < 4 or length(argv[4]) = 0
end if

-- Get longest palindromic substring. Error if none found
sequence s = argv[4]
sequence longest = longest_palindromic_substring(s)
if length(longest) < 2
end if

-- Show longest palindromic substring
printf(STDOUT, "%s\n", {longest})

Longest Palindromic Substring in Euphoria was written by:

If you see anything you'd like to change or update, please consider contributing.

How to Implement the Solution

No 'How to Implement the Solution' section available. Please consider contributing.

How to Run the Solution

No 'How to Run the Solution' section available. Please consider contributing.