complexity?
Posted: Tue Apr 17, 2007 3:51 am
Whats the complexity of accepted code?
my code is O(n^2) which for the life of me i cant find anything faster and yet i get TLE... any suggestions?
my code is O(n^2) which for the life of me i cant find anything faster and yet i get TLE... any suggestions?
Code: Select all
#include<iostream>
#include<string>
using namespace std;
bool pallenword(const string& t) {
if(t.length() <= 4)
return false;
string otherp = "";
for(int i=1;i<t.length()-1;++i) {
int l = 1;
bool even,odd;
odd = (t[i+1] == t[i-1]);
even = (i < t.length() - 2) && (t[i+1] == t[i]) && (t[i-1] == t[i+2]);
while(even || odd) {
if(odd && l <= i && i+l < t.length() && t[i-l] == t[i+l]) {
if((otherp.length() > (l*2) + 1 ) &&
otherp.find(t.substr(i-l,(l*2)+1)) != string::npos)
;
else if(otherp == "" ||
t.substr(i-l,(l*2)+1).find(otherp) != string::npos)
otherp = t.substr(i-l,(l*2)+1);
else
return true;
} else
odd = false;
if(even && l <= i && i+l+1 < t.length() && t[i-l] == t[i+l+1]) {
if((otherp.length() > (l+1) * 2) &&
otherp.find(t.substr(i-l,(l+1)*2)) != string::npos)
;
else if(otherp == "" ||
t.substr(i-l,(l+1)*2).find(otherp) != string::npos)
otherp = t.substr(i-l,(l+1)*2);
else
return true;
} else
even = false;
++l;
}
}
return false;
}
int main()
{
string t;
while(cin >> t)
if(pallenword(t))
cout << t << '\n';
}