Recursive function to do substring search


StringViews 3849

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

Example

INPUT
s1 = “tutorial cup”
s2 = “cup”

OUTPUT
TRUE

Algorithm

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

#include<iostream>
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;
    }
    else
    {
        cout<<"FALSE"<<endl;
    }
    return 0;
}

Try It

 

Translate ยป