# 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

### Example

INPUT
s1 = "tutorial cup"
s2 = "cup"

## OUTPUTTRUEAlgorithm

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;
}``````

Scroll to Top