**This is an old revision of the document!**

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;
		// 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)
	// 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);
	// Then I printed all susbtrings of input
int main()
	cout << "Word: ";
	string input;
	cin >> input;
	cout << endl;
	if (is_palindrome(input))
		cout << "IT'S A PALINDROME!!!" << endl;
		cout << "not a palindrome" << endl;
	return 0;
cs-142/substrings-and-palindromes.1432844581.txt.gz · Last modified: 2015/05/28 14:23 by cs142ta
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0