accelerated C++ to find longest of palindrome

Question

I am practising Koeing accelerated C++ , and want to verify my answer. Since there are no solutions available on net , I thought to post it here and ask experts view about my solution. I am not sure if people will like me to post it here. if not , please let me know and i will not do it in future. Also to mention, its not homework , its purely my desire to take my C++ skills to next level.

Question: Write a program to find all the palindromes in a dictionary. Next, find the longest palindrome.

What I have done so far -> I have defined function to test palindrome , also stored all words in a list. I have posted my code below.

Where I am stuck: I need advice , whether my choice of using list data structure over vector is good or not? Secondly, I am stuck how to display longest word. I can display longest length but not longest word.

my attempt below

    bool palindromeTest( const std::string& input )
{
   typedef std::string::size_type strSize;
    strSize i = 0;
    strSize j = input.size() - 1  ;
    while( i < input.size() )
    {
        if ( input[i] != input[j])
        {
            return false;
        }
        i++;
        j--;
    }

    return true;
}



int main()
{

    // stores all words in a list or vector
    std::list< string> listDict;
    std::string readWord;
    std::ifstream readFile( "/Users/apple/palidndrome-ch5-10/dict.txt" );
    if( ! readFile )
    {
        std::cout <<" failed to open file" << std::endl;
        return 0;
    }
    while( readFile >> readWord )
    {
        listDict.push_back( readWord );
    }

     std::string::size_type maxLen = 0 ;
     std::string longestWord = " "; // to store longest palindrome


     // print all the palindrome words and also which is longest palindrome.

    for( std::list<std::string>::const_iterator it = listDict.begin(); it != listDict.end(); ++it )
    {

        if( palindromeTest( *it )  )
        {
            std::cout <<" the word -> " << *it << " is palindrome" << std::endl;
            // find max len of palindrome;
            maxLen = max( maxLen, it->size() );
            longestWord = *it ;// need to change code here ?? no idea how

        }

    }

    std::cout <<" the maximum len is = " << maxLen << std::endl;
    std::cout << " the word with maximum length is  " << longestWord ; // something is wrong here


    return 0;
}

Answer 1

Vectors and lists both work equally well here, though a vector is more efficient.

You can find the longest word by changing

maxLen = max( maxLen, it->size() );
            longestWord = *it ;// need to change code here ?? no idea how

to

if (it->size() >= longestWord.size()) {longestWord = *it;}

(You don't actually need to keep track of maxlen since you can just call longestWord.size().)

Answer 2

First the palindrome test. You are checking every character in the string twice which is unneeded. While in this particular case it will not matter, as it just doubles the time for that particular operation, for some similar operations it will change the semantics (consider reverse --conceptually very similar to the test for palindrome). To improve the check you can either use a loop counter from 0 to input.size()/2 or use two pointers/iterators and run until they meet in the middle. Also note that iterating up to input.size()/2 will leave a character that it never tested for strings with odd sizes, but that is fine.

When in need for a sequential container, you should always default to std::vector<>, rather than std::list<>. To manually find the maximum, you should change the call to max for a test that checks whether this element is larger than the previous max and then updates both the value of max and the location of the string (or the string itself). In this particular case, and if the number of repetitions is high, you could also consider not using a sequential container, but rather an associative one (std::set<std::string>) to avoid repetitions. But it is better not to store the words in memory altogether.

You should learn to use iterators, and the iterator's header in the standard library. For example, the reading loop can be converted to:

std::vector<std::string> words;
std::copy( std::istream_iterator<std::string>( readFile ),
           std::istream_iterator<std::string>(),
           std::back_inserter( words );

The check for a palindrome can be a call to the std::equal algorithm:

bool isPalindrome( std::string const & str ) {
   return std::equal( str.begin(), str.begin()+str.size()/2,
                      str.rbegin() );
}

Finding the longest palindrome can also be done with an algorithm, by providing the appropriate functor:

std::vector::const_iterator max = std::max_element( words.begin(), words.end(), []( std::string const & lhs, std::string const & rhs ) { return lhs.size() < rhs.size(); });

(Using lambdas from C++11, in C++03 you would need to create a functor that performs the same comparison, which takes some more boilerplate code, but should not be much more complex)

As Antimony points out, if you only need this result, you don't need to keep all of the words in memory, in that case you could just test each word as is read and only store it if it is the longest palindrome up till now. This is not so easily implementable with standard algorithms, and it will be simpler to just roll your own loop.

While for learning purposes you probably want to follow the book (that targets C++03), a simple solution in C++11 could be:

std::string longestPalindrome( std::istream& stream ) {
   std::string longest;
   std::for_each( std::istream_iterator<std::string>(stream),
                  std::istream_iterator<std::string>(),
                  [&longest]( std::string const & word ) {
                      // if is longest palindrome so far
                      if (std::equal( word.begin(),
                                      word.begin()+word.size()/2,
                                      word.rbegin() 
                          && word.size() > longest.size())) 
                      {
                         longest = word;
                      }
                  });
   return longest;
}
int main() {
   std::ifstream readFile( "/Users/apple/palidndrome-ch5-10/dict.txt" );
   if ( !readFile ) {
      std::cerr << "failed to open file\n";      // [*]
      exit(1);
   }
   std::string longest = longestPalindrome( readFile );
   std::cout << "The longest palindrome is: '" << longest << "'\n";
}

[*]: Note, unless you really need it, it is better to just output "\n" than std::endl. The difference between the two is that std::endl will also flush the stream (force write), which will impact performance for no particular reason. As to when do you need to flush, basically when you need to ensure that the output is generated now, for example when querying a user:

std::cout << "Enter a number: " << std::flush; // Ensure that the user gets the message
                                               // before we lock waiting for an answer:
std::cin >> number;

And even in this case, it is clearer (if you need a newline) to dump "\n" and std::flush than std::endl (where it is not so clear that the flush is intentional, as there is way too much code that uses std::endl unendingly...