Recursive function to do substring search


Given two strings s1 and s2, write a recursive function that returns TRUE if s2 is present in s1


s1 = “tutorial cup”
s2 = “cup”



1. If current character of s2 is last character of s1, but s2 has more characters then return FALSE

2. If current character of s1 is last character of s2 then return TRUE

3. If the characters match in s1 and s2, then check for the complete s2 in s1

4. If current characters dont match, then do recursive call for the remaining string.

C++ Program

using namespace std;
bool isExactMatch(char *s1, char *s2)
    if (*s1 == '\0' && *s2 != '\0')
        return false;
    // Else If last character of pattern reaches
    if (*s2 == '\0')
        return true;
    if (*s1 == *s2)
        return isExactMatch(s1 + 1, s2 + 1);
    return false;
// This function returns true if 's1' contain 's2'
bool isSubString(char *s1, char *s2)
    // If last character of s1 reaches
    if (*s1 == '\0')
        return false;

    // Else If last character of s2 reaches
    if (*s2 == '\0')
        return true;
    // If current characts of s2 and s1 match
    if (*s1 == *s2)
        return isExactMatch(s1, s2);
    // If current characts of s2 and s1 don't match
    return isSubString(s1 + 1, s2);
int main()
    char s1[] = "tutorial cup";
    char s2[] = "cup";
    if(isSubString(s1, s2))
        cout<<"TRUE"<< endl;
    return 0;

Try It


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions