Substrings and Palindromes

• 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

• 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?

#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)
{
	bool this_is_palindrome = true;
 
	// 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;
}