You are here

C program to check subsequence

Subsequence examples

C program to check Subsequence; don't confuse it with substring. In our program, we check if a string is a subsequence of another.

A user will input two strings, and we test if one of them is a subsequence of the other. The 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 subsequence program

#include <stdio.h>
#include <string.h>

int check_subsequence (char [], char[]);

int main () {
  int t;
  char s1[1000], s2[1000];

  printf("Input first string\n");
  gets(s1);

  printf("Input second string\n");
  gets(s2);

  /** Passing smaller length string first */

  if (strlen(s1) < strlen(s2))
    t = check_subsequence(s1, s2);
  else
    t = check_subsequence(s2, s1);

  if (t)
    printf("YES\n");
  else
    printf("NO\n");

  return 0;
}

int check_subsequence (char a[], char b[]) {
  int c, d;

  c = d = 0;

  while (a[c] != '\0') {
    while ((a[c] != b[d]) && b[d] != '\0') {
      d++;
    }
    if (b[d] == '\0')
      break;
    d++;
    c++;
  }
  if (a[c] == '\0')
    return 1;
  else
    return 0;
}

An output of the program:

Input first string
tree
Input second string
Computer science is awesome
YES

The 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 they match, indexes of both of them are increased by one, and we repeat the process. If the first string ends, then it's a subsequence, otherwise not.