# Substrings and Palindromes

## Problem

• Write a program that prompts for an input string and then uses two recursive functions to successively
• generate all substrings of the input and
• check if the input is a palindrome

## Problem-Solving

• Note that if we assume we've generated all substrings for the input without its first letter, then all we need to add are substrings that include the first letter
• Note that if a palindrome is a word where the first and last letters are the same and the rest is also a palindrome
• Consider what is the base case for each problem?

## Solution

#include <iostream>
#include <string>

using namespace std;

/*
Recursive function to find palindrome
@input string to test if it's a palindrome
@return true if string is a palindrome, false otherwise
*/
bool is_palindrome(string str)
{
// base case
if (str.length() <= 1)
{
return true;
}

// if first and last letter are the same
if (str.substr(0, 1) != str.substr(str.length() - 1))
{
return false;
}
else{
// and the rest of me is a palindrome
return is_palindrome(str.substr(1, str.length() - 2));
}
}

/*
Recursive function to generate all substrings
Bottom line: to generate all substrings,
* generate substrings that include the first letter
* then generate all substrings for the input string WITHOUT the first letter
@param input word to generate substrings for
*/
void print_all_substrings(string input)
{
// base case
if (input.length() == 0)
{
return;
}

// If I generate substrings of the input string that include the input string's first letter
cout << input << endl;

for (int i = input.length() - 1; i > 0; i--)
{
cout << input.substr(0, i) << endl;
}

// And then generate all substrings for the input string WITHOUT its first letter
string input_wo_first_letter = input.substr(1, input.length() - 1);
print_all_substrings(input_wo_first_letter);

// Then I printed all susbtrings of input
}

int main()
{
cout << "Word: ";
string input;
cin >> input;

print_all_substrings(input);
cout << endl;

if (is_palindrome(input))
{
cout << "IT'S A PALINDROME!!!" << endl;
}
else
{
cout << "not a palindrome" << endl;
}

system("pause");
return 0;
}