Question

C - programming problem:

Let T be a sequence of an even length 2k, for some non-negative integer k. If its prefix of k symbols (or, the first k symbols in T) are the same as its suffix of k symbols (respectively, the last k symbols in T), then T is called a tandem sequence. For example, T[8] = 31103110 is a tandem sequence. Given a sequence S, if T is a subsequence of S and T is tandem, then T is called a tandem subsequence of S. One can then similarly define what a longest tandem subsequence (LTS for short) of S is.

Write a program that reads in two sequences with max length: 10,000, which computes, and prints the longest-tandem subsequence or LTS, and its length.

Sample program run:

Enter a sequence: 3110283025318292818318143

# an LTS (length = 10) for the sequence is:

1283312833

Answer 1

Complete Program:

Sample Output:

CODE TO COPY:

// Header files section
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// constant declaration
#define MAX 10000

// getLCS function returns the
// longest common subsequence of two sequences
char* getLCS(char* s1, char* s2, int m, int n)
{
    int** L = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i < (m + 1); i++)
    {
        L[i] = (int*)malloc((n + 1) * sizeof(int));
    }

    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
            {
                L[i][j] = 0;
            }
            else if (s1[i - 1] == s2[j - 1])
            {
                L[i][j] = L[i - 1][j - 1] + 1;
            }
            else
            {
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
            }
        }
    }

    int p = m;
    int q = n;
    int r = L[m][n];
    char* lcs = (char*)malloc(sizeof(char) * (r + 1));
    lcs[r] = '\0';
  
    while (p > 0 && q > 0)
    {
        if (s1[p - 1] == s2[q - 1])
        {
            lcs[r - 1] = s1[p - 1];
            p--;
            q--;
            r--;
        }
        else if (L[p - 1][q] > L[p][q - 1])
        {
            p--;
        }
        else
        {
            q--;
        }
    }

    return lcs;
} // end of getLCS function

// findLTS function returns the
// longest tandem subsequence of a sequence
char* findLTS(char* S)
{
    int m = 1;
    int n = strlen(S) - 1;
    int len = 0;
    char term[MAX] = "";

    do
    {
        char s1[MAX];
        char s2[MAX];
        int i, j;

        for (i = 0; i < m; i++)
        {
            s1[i] = S[i];
        }
        s1[i] = '\0';

        for (j = 0; j < n; j++, i++)
        {
            s2[j] = S[i];
        }
        s2[j] = '\0';

        // call the getLCS function
        char* temp = getLCS(s1, s2, m, n);
        int rec = strlen(temp);

        if (rec >= len)
        {
            len = rec;
            strcpy(term, temp);
        }

        m++;
        n--;
    } while (m < n);

    char T[MAX] = "";  
    strcat(T, term);
    strcat(T, term);

    return T;
} // end of findLTS function

// start main function
int main()
{
    // prompt the user for a sequence
    char S[MAX];
    printf("Enter a sequence: ");
    scanf("%s", S);  

    // call the findLTS function
    char* T = findLTS(S);
  
    // print the LTS and its size
    printf("\n# an LTS (length = %d) for the sequence is:\n", strlen(T));
    printf("%s\n", T);

    return 0;
} // end of main function