mohammad rahimi
BAN USERhere is my solution:
#include <iostream>
using namespace std;
main()
{
int input[]={12,4,0,343,2,0,323,0,23};
int index=0;
int size= sizeof(input)/sizeof(int);
for(int i=0;i<size;i++) {
if(input[i] != 0){
if(i-index>0) {
input[index]=input[i];
index++;
}
else index++;
}
}
for(;index<size;index++) input[index]=0;
}
This solution works in O(n+p) where n is the length of string and p is the length of palindrom patterns. In worst case it would be O(n^2)
check it:
/a.out "baab check aa abc zxz it adda hhh "
./a.out " baab check aa abc zxz it adda hhh "
./a.out
#include <iostream>
using namespace std;
int palindromesCount(char *input)
{
int countpalindromes=0;
int wordStart=0,wordEnd=0;
int charStart,charEnd;
while(input[wordStart] != '\0') {
if(input[wordStart] != ' ') {
for(wordEnd = wordStart; input[wordEnd] != ' ' & input[wordEnd] != '\0'; wordEnd++); wordEnd--;
charStart = wordStart;
charEnd = wordEnd;
while( ((charEnd-charStart) > 0) & (input[charEnd]==input[charStart]) ) { charStart++; charEnd--;};
if( (charEnd-charStart) <=0 ) countpalindromes ++;
wordStart = wordEnd+1;
}
else wordStart++;
}
return countpalindromes;
};
main(int argc, char *argv[])
{
if(argc>1) cout << palindromesCount(argv[1]) << endl;
}
This will do it in O(n^2) using a hashtable using so called Sieve algorithm
- mohammad rahimi July 22, 2012