moghun / lcs_scs

LCS and SCS finder with Trie Support

Overview

This project provides robust implementations for calculating the Longest Common Subsequence (LCS) and the Shortest Common Supersequence (SCS) between two sequences. It also includes a custom Trie data structure to enhance certain operations, such as efficiently managing and retrieving subsequences (trie is added for the sake of practice :P).

Project Structure

The source code is organized into separate directories for each component:

• main.cpp
• lcs/: lcs.cpp and lcs.h
• scs/: scs.cpp and scs.h
• trie/: trie.cpp and trie.h

Building the Project

Prerequisites

• Ensure you have a modern C++ compiler that supports C++17 or later. This project is developed with g++ as the primary compiler.

Compilation with Makefile

A Makefile is provided for easy compilation of the project. Use the following commands in your terminal:

make        # Compiles the project and creates the executable
make clean  # Cleans up all compiled files, ensuring a fresh build