You are here

C program to check subsequence

C program to check Subsequence, don't confuse subsequence with substring. In our program, we check if a string is a subsequence of another string. A user will input two strings, and we find if one of the strings is a subsequence of the other. Program prints yes if either the first string is a subsequence of the second string or the second string is a subsequence of the first string. We pass smaller length string first because our function assumes the first string is of smaller or equal length than the second string.

C programming code

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int check_subsequence (char [], char[]);
  5.  
  6. int main () {
  7.   int flag;
  8.   char s1[1000], s2[1000];
  9.  
  10.   printf("Input first string\n");
  11.   gets(s1);
  12.  
  13.   printf("Input second string\n");
  14.   gets(s2);
  15.  
  16.   /** Passing smaller length string first */
  17.  
  18.   if (strlen(s1) < strlen(s2))
  19.     flag = check_subsequence(s1, s2);
  20.   else
  21.     flag = check_subsequence(s2, s1);
  22.  
  23.   if (flag)
  24.     printf("YES\n");
  25.   else
  26.     printf("NO\n");
  27.  
  28.   return 0;
  29. }
  30.  
  31. int check_subsequence (char a[], char b[]) {
  32.   int c, d;
  33.  
  34.   c = d = 0;
  35.  
  36.   while (a[c] != '\0') {
  37.     while ((a[c] != b[d]) && b[d] != '\0') {
  38.       d++;
  39.     }
  40.     if (b[d] == '\0')
  41.       break;
  42.     d++;
  43.     c++;
  44.   }
  45.   if (a[c] == '\0')
  46.     return 1;
  47.   else
  48.     return 0;
  49. }

An output of the program:

  1. Input first string
  2. tree
  3. Input second string
  4. Computer science is awesome
  5. YES

Logic of the function is simple; we keep on comparing characters of two strings, if a mismatch occurs then we move to the next character of the second string and if characters match, indexes of both the strings are increased by one and so on. If the first string ends then it is a subsequence otherwise not.