Pesky Palindromes uva Solution 353

This is an easy problem from uva judge http://uva.onlinejudge.org/external/3/353.html

How I did it

• Read the string.
• I generate all the possible words for the string.
• Check word by word if they are palindromes.
• If the word is a palindrome insert into a STL set. (We need to filter all diferet palindromes).
• Print the size of the STL set

Hints

• Find all the different subset. For example for “aba”, the diferent subset are a,b,ab,ba. And the output is 2. We only count the letter ‘a’ one time.
• The max input size need 3204 combinations. Really small
• This is general for all inputs. Check this example. Input : “Fabian”

f, a, b, i, a, n           Size 6

fa, ab, bi, ia, an     Size 5

fab, abi, bia, ian    Size 4

fabi, abia, bian      Size 3

fabia, abian           Size 2

fabian                     Size 1

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
string cad;
set<string>mySet;

bool isPalindrome(string str){
string tmp = str;
reverse(tmp.begin(),tmp.end());
if(str == tmp)
   return true;
return false;
}

void generateCombination(int strWord, int index){
string strTmp = ""; //cout<<index<<endl;
   for(int x=index; x<cad.size(); x++)
   {
        strTmp += cad[x];
        if(strTmp.size() == strWord)
        {
            if(isPalindrome(strTmp))
               mySet.insert(strTmp);
            strTmp = "";
            if(index<cad.size()-1)
               generateCombination(strWord,++index);

            return;

        }
        if(index == cad.size()-1 || x == cad.size()-1)
           return;
   }
}

void getLetter(){
string letter = "";
    for(int x=0; x<cad.size(); x++)
    {
        letter += cad[x];
        mySet.insert(letter);
        letter = "";
    }
}

int main(){
int wordSize;
int initPos;

while(cin>>cad){

    if(cad.size() == 1)
       printf("The string \'%s\' contains 1 palindromes.\n",cad.c_str());
    else{
         wordSize = 2;
         initPos = 0;         while(wordSize<=cad.size()){
            generateCombination(wordSize, initPos);
            wordSize++;
         }
         getLetter();
         printf("The string \'%s\' contains %d palindromes.\n",cad.c_str(), mySet.size());
         mySet.clear();
        }
}
return 0;
}