Character Sequence in a String : Sub-sequence using C

Sub-sequence is another finding the needle in a haystack problem. The difference is that the characters must be in sequence. That’s the whole point , we have to find the sub-sequence(needle) in the string(hay).

This is a problem which can be faced with much efficiency if you know the concept of pointers and recursion. You must be wondering why something as confusing as pointers are so commonly used in C is rarely mentioned. And why C has pointers.

Why C has Pointers?

C was developed when computers were much less powerful than they are today. And being very efficient with speed and memory usage was often not just desirable but vital. The raw ability to work with particular memory locations was obviously a useful option to have. A few tasks these days, such as programming micro-controllers, still need this. Most modern programmers do not need such fine control. The complications of using pointers make programs less clear to understand and add to the ways in which they can be go wrong. So why are pointers still used so much in C & its successor, C++?

The reason is that pointers are used to bodge into C’s some vital features which are missing from the original language: arrays, strings, & writable function parameters. They can also be used to optimize a program to run faster or use less memory than it would otherwise.

A pointer could be used for any, several or all these different reasons with little or no distinction in the language. So, if a programmer has not put in helpful comments, it will be difficult for others to follow through the program to see what each pointer is used for in order to work out why it is there instead of a plain simple variable.

So if you are satisfied with my answer…..

let’s move on to the coding

Problem: There are two strings needle and haystack (or hay). You need to check if all the characters in needle are present in hay in a sequence i.e. if needle is a sub-sequence of the string. If yes then return True (1) or False (0)

We can solve this problem in two ways:

1. Non-Recursive method
2. Recursive method

1.Non-Recursive method:

The Non-recursive method has a simple code with a do-while loop.

• Let’s start by creating a function which takes two strings as parameter. Let’s call it as subseq. Let the return type be int as we will be returning in binary.

int subseq(const char *needle, const char *hay){
    return 1;
}

• Next with a do-while loop till hay is not empty, we will check if needle is not null and present in hay then increment needle to the next character.

int subseq(const char *needle, const char *hay){
    do {
        if (*needle && tolower(*needle) == tolower(*hay))
          needle++;
    } while (*hay++);
    return !*needle;
}

• The loop will run till the end the string hay and if all the characters of needle are present in hay in a sequence then the function will return True(1) or else False(0).

Image of code without comment

• Let’s visualize the code using python tutor

Python Tutor visualization of the code

2. Recursive method:

The recursive method is very short code but a little complex.

• Let’s start by creating the function which takes two strings as parameters. Let’s call it as subseq_rec.

int subseq_rec(const char *needle, const char *hay){
    return 1;
}

• Next is the one line code which checks for the needle sequence in hay and returns True if the needle is sub-sequence and otherwise False

const char* strichr(const char *hay, const char needle){
    const char needlei = tolower(needle);
    do{
        if (tolower(*hay) == needlei){
            return hay;
        }
    }while(*hay++);
return NULL;
}
int subseq_rec(const char *needle, const char *hay) {
    return (*needle == 0 ? 1 : (strichr(hay, *needle) ) ?
    subseq(++needle,++hay) : 0 );
}

• The code first checks for if there is any character is present in needle or not and then returns True if NULL.
• If needle is not NULL then the code checks for if the first character of needle is present in hay or not using the function strichr then returns the function in a recursion by pointing the pointers to the next characters.
• Strichr is similar to strchr function but unlike strchr it is case insensitive.
• Here both hay and needle are incremented so that there is no repetition of character in hay and sequence is maintained.
• If the sequence is broken then immediately the function returns False(0)

Full Image of code

• Let’s visualize the code using python tutor

Python Tutor visualization of the code

Lastly, I would like to thank my programming mentors at KGiSL Institute of Technology (KiTE) who supported me and encouraged me to put out this successful attempt at solving this problem and also for teaching me the fundamentals that were required to solve this problem.

And if you’ve understood the strichr then try this striRchr by Pragadesh Mahalingam