Longest Sub Sequence Algorithm
The Longest Subsequence Algorithm, also known as Longest Common Subsequence (LCS) Algorithm, is an essential method in computer science and bioinformatics, primarily used for comparing sequences. It is a classic dynamic programming algorithm that aims to find the longest possible subsequence present in two given sequences. A subsequence is a sequence of characters or elements that appear in the same order in both sequences, but not necessarily consecutively. The LCS algorithm has numerous applications, such as in file comparison tools (like diff), version control systems (like Git), and DNA sequence alignment in bioinformatics.
The algorithm employs dynamic programming to solve the problem by breaking it down into smaller overlapping subproblems and solving them in a bottom-up manner, reusing the solutions of previously solved subproblems to avoid redundant computation. The central idea is to create a table to store the lengths of the longest common subsequences of prefixes for the given sequences. By filling up this table, the algorithm can find the longest common subsequence of the entire sequences. The complexity of this algorithm is O(mn), where m and n are the lengths of the two input sequences, making it efficient for practical use cases. Additionally, the algorithm can be modified to not only find the length of the LCS but also to reconstruct the actual LCS itself.
#include <stdio.h>
#include <stdlib.h>
void longestSub(int* ARRAY,int ARRAY_LENGTH, int** RESULT,int* RESULT_LENGTH){ //RESULT and RESULT_LENGTH will be modified by their pointers
if(ARRAY_LENGTH <= 1){
*RESULT=ARRAY;
*RESULT_LENGTH = ARRAY_LENGTH;
}
else{
int PIVOT = ARRAY[0];
int *LONGEST_SUB = NULL;
int i, j, LONGEST_SUB_LENGTH = 0;
int TEMPORARY_ARRAY_LENGTH = 0, *TEMPORARY_ARRAY = NULL;
for(i = 1; i < ARRAY_LENGTH; i++){
if (ARRAY[i] < PIVOT){
TEMPORARY_ARRAY_LENGTH = 0;
TEMPORARY_ARRAY = NULL;
for(j = i+1;j < ARRAY_LENGTH; j++){
if(ARRAY[j] >= ARRAY[i]){
TEMPORARY_ARRAY_LENGTH++;
TEMPORARY_ARRAY = (int *)realloc(TEMPORARY_ARRAY, TEMPORARY_ARRAY_LENGTH*sizeof(int));
TEMPORARY_ARRAY[TEMPORARY_ARRAY_LENGTH-1] = ARRAY[j];
}
}
longestSub(TEMPORARY_ARRAY, TEMPORARY_ARRAY_LENGTH, &TEMPORARY_ARRAY, &TEMPORARY_ARRAY_LENGTH);
if(LONGEST_SUB_LENGTH < TEMPORARY_ARRAY_LENGTH + 1){
LONGEST_SUB_LENGTH = TEMPORARY_ARRAY_LENGTH + 1;
LONGEST_SUB = (int *)realloc(LONGEST_SUB, LONGEST_SUB_LENGTH*sizeof(int));
LONGEST_SUB[0] = ARRAY[i];
for(i = 1;i < LONGEST_SUB_LENGTH; i++)
LONGEST_SUB[i] = TEMPORARY_ARRAY[i-1];
}
}
}
TEMPORARY_ARRAY = NULL;
TEMPORARY_ARRAY_LENGTH = 0;
for(i = 1;i < ARRAY_LENGTH; i++){
if(ARRAY[i] >= PIVOT){
TEMPORARY_ARRAY_LENGTH++;
TEMPORARY_ARRAY = (int *)realloc(TEMPORARY_ARRAY, TEMPORARY_ARRAY_LENGTH*sizeof(int));
TEMPORARY_ARRAY[TEMPORARY_ARRAY_LENGTH-1] = ARRAY[i];
}
}
longestSub(TEMPORARY_ARRAY, TEMPORARY_ARRAY_LENGTH, &TEMPORARY_ARRAY, &TEMPORARY_ARRAY_LENGTH);
if(TEMPORARY_ARRAY_LENGTH + 1 > LONGEST_SUB_LENGTH){
LONGEST_SUB_LENGTH = TEMPORARY_ARRAY_LENGTH + 1;
LONGEST_SUB = (int *)realloc(LONGEST_SUB, LONGEST_SUB_LENGTH*sizeof(int));
LONGEST_SUB[0] = PIVOT;
for(i = 1;i < LONGEST_SUB_LENGTH; i++)
LONGEST_SUB[i] = TEMPORARY_ARRAY[i-1];
}
*RESULT = LONGEST_SUB;
*RESULT_LENGTH = LONGEST_SUB_LENGTH;
}
}
int main(){
int EXAMPLE_LENGTH = 8;
int EXAMPLE[] = {18, 2, 15, 4, 30, 0, 11, 12};
int *RESULT = NULL;
int RESULT_LENGTH, i;
longestSub(EXAMPLE, EXAMPLE_LENGTH, &RESULT, &RESULT_LENGTH);
printf("Longest Sub Sequence length: %d and it's:\n", RESULT_LENGTH);
for(i = 0;i < RESULT_LENGTH; i++)
printf("%d ",RESULT[i]);
printf("\n");
return 0;
}
