C Program to Find the Length of Longest Repeating Subsequence

This C Program finds the length of longest repeating sequence in a string.

Here is source code of the C Program to find the Length of the longest repeating sequence in a string. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Find the Length of the Longest Repeating Sequence in a String
  3.  */ 
  4. #include <stdio.h>
  5. #include <string.h>
  6. char string[100], words[100][100];
  7. int len = 0, word_cnt = 0;
  8. int main()
  9. {
  10.     int i, j = 0, k, mlen = 0, rlen = 0, s = 0, c = 0, m = 0;
  11.     printf("\nEnter the string:");
  12.     scanf(" %[^\n]s", string);
  13.     for (len = 0;string[len] != '\0';len++);
  14.     /* 
  15.      * Storing the individual words in an array
  16.      */
  17.     for (k = 0;k < len;k++)
  18.     {
  19.         if (string[k] != ' ')
  20.         {
  21.            words[s][j] = string[k];
  22.             j++;
  23.         }
  24.         if (string[k] == ' ')
  25.         {
  26.             words[s][j] = '\0';
  27.             j = 0;
  28.             s++;
  29.             word_cnt++;
  30.         }
  31.     }
  32.     word_cnt++;
  33.     /* 
  34.      * Compare on Word basis if same word is repeated then check next word & so on
  35.      * Increment a counter when consecutive words are repeated
  36.      */
  37.     for (i = 0;i <= word_cnt;i++)
  38.     {
  39.         len = 0;
  40.         for (j = i+1;j <= word_cnt-1;j++)
  41.         {
  42.             if (strcmp(words[i], words[j]) != 0)
  43.             {
  44.                 continue;
  45.             }
  46.             else if (strcmp(words[i], words[j]) == 0)
  47.             {
  48.                 len++;
  49.                 for (k = i+1, m = j+1;k < j;k++, m++)
  50.                 {
  51.                     if (strcmp(words[k], words[m]) == 0)
  52.                     {
  53.                         len++;
  54.                         continue;
  55.                     }
  56.                     else    
  57.                     {    
  58.                         break;
  59.                     }
  60.                 }
  61.                 if (rlen < len)
  62.                 {
  63.                     rlen = len;
  64.                     len = 0;
  65.                 }
  66.                 len = 0;
  67.             }
  68.             /*
  69.              * Finding length of Longest Repeated Sequence
  70.              */
  71.             if (mlen < rlen)
  72.             {
  73.                 s = i;
  74.                 mlen = rlen;
  75.             }
  76.         }
  77.     }
  78.     printf("\nLength of Longest Repeating Sequence:%d\n", mlen);
  79.     printf ("\nTotal number of words : %d", mlen);
  80.     printf ("\n The subsequence is : ");
  81.     for (i = s, j = 0;j < mlen;i++, j++)
  82.     printf(" %s", words[i]);
  83.     char subseq[100];
  84.     // concat all the words
  85.     for (i = s, j = 0; j < mlen; i++, j++)
  86.       strcat (subseq, words[i]);
  87.     printf ("\nThe length of longest common subsequence is: %d", strlen(subseq)+1);
  88.     printf("\n");
  89. }

Enter the string:
Welcome to C Programming Class, Welcome Again to C Programming Class!
 
Length of Longest Repeating Sequence:3
 
Total number of words : 3
 The subsequence is :  to C Programming
The length of longest common subsequence is : 19

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.