Geek Answers Handbook

Search Engine Optimization Palindrome C ++

I am writing a palindrome finder in C ++, and I managed to write one that is ... basic, at least.

I just want to increase the speed of the program, now it takes about ~ 1 m 5 seconds to run the test for palindromes / 2 words of the palindromes in the word word word 1500, using the functions that I have. I would like to try running it in a much larger file, but don’t see where I can optimize further?

Any help would be appreciated: PS This is not for school, just for relaxation.

#include <iostream> #include <ostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; bool isPal(string); int main() { vector<string> sVec; vector<string> sWords; vector<string> sTwoWords1; vector<string> sTwoWords2; char myfile[256]="/home/Damien/Test.txt"; ifstream fin; string str; fin.open(myfile); if(!fin){ cout << "fin failed"; return 0; } while(fin){ fin >> str; sWords.push_back(str); if(!fin){ break; } if(isPal(str)){ sVec.push_back(str); } else{ getline(fin, str); } } reverse(sVec.begin(), sVec.end()); for(int i =0; i < sVec.size(); i++){ cout << sVec[i] << " is a Palindrome " <<endl; } // Test 2 for(int i=0; i<sWords.size(); i++){ for(int j=(i+1); j<sWords.size(); j++){ str = sWords[i]+sWords[j]; if(isPal(str)){ sTwoWords1.push_back(sWords[i]); sTwoWords2.push_back(sWords[j]); } } } fin.close(); for(int i=0; i<sTwoWords1.size(); i++){ cout << sTwoWords1[i] << " and " << sTwoWords2[i] << " are palindromic. \n"; } return 0; } bool isPal(string& testing) { return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin()); }
+4
c ++ function
source share
2 answers

You do a lot of extra work to check if it is a palindrome. Just use std::equal :

 #include <algorithm> bool isPal(const string& testing) { return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin()); }

It will iterate from the beginning of the line to the middle and from the end of the line to the middle and compare the characters as it appears. I don’t remember who showed it to me, but I didn’t think about it.

Edit: I learned this from Cubbi in yet another question about palindromes .

+9
source share

So, I did some testing. In your approach, Test2 is time consuming.

Data: 2000 random 20 lines of characters.

Your solution: 2500 ms. Seth Carnegie's: 500 ms.

Although I believe that you need to multiply them by 2, because s + v can be a palindrome, and v + s isnt.

Idea: suppose we have the word ABCD. In other words, then there can be palindromes with this only cba and dcba. Let's check if we have those present.

 ... #include <set> using namespace std; bool isPal(const string&); int main() { ... set<string> rWords; ... while(fin){ fin >> str; sWords.push_back(str); if(!fin){ break; } reverse(str.begin(), str.end());//add reversed str to rWords rWords.insert(str); reverse(str.begin(), str.end()); ... } ... // Test 2 for(int i = 0; i<sWords.size(); ++i) for(int l = 0; l<sWords[i].length(); ++l) if(isPal(sWords[i].substr(sWords[i].length()-l))) { string s = sWords[i].substr(0,sWords[i].length()-l); set<string>::iterator it = rWords.find(sWords[i].substr(0,sWords[i].length()-l)); if(it != rWords.end()) { string s = *it; reverse(s.begin(), s.end()); if(s == sWords[i])//isPoly to itself continue; sTwoWords1.push_back(sWords[i]); sTwoWords2.push_back(s); } } ... return 0; } bool isPal(const string& testing) { return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin()); }

time: 15 ms

+3
source share

More articles:


All Articles