A Sub-Problem, A funny Bug

Busy Days! Very little time for solving! :(

Problem (Actually a sub-problem of a problem, that I was working on):
Given a string S of length n. Calculate a boolean array P in O(n) time, where P[k] = true, if the k-length prefix of S is a palindrome, and false otherwise.
I have got an idea using some technique known (not much known) as the Z-algorithm. But I was trying to solve it with KMP (no success with that).

I'll try to write on that Z-algorithm-based solution some other day.

BTW, here is a very nice tutorial of the simple and interesting, Z-algorithm.

And here is a nice(!!) bug, that I made recently. The following function was causing TLE.

// the size of the input vector v is at most 50
int calc(vector<int>& v)
{
 int ret = 0;

 for(int i = 0; i < v.size()-1; ++i)
 {
   // do some constant time work...
 }

 return ret;
}

Why? Because, v.size() returns an unsigned value. So, when the input vector is empty, the expression (v.size()-1) evaluates to 4294967295. So, the loop was never breaking. As the loop counter i was a signed int type variable, it was never reaching this large value.

this blog is inspired by: http://one-problem-a-day.blogspot.com