This is a very nice tutorial (for me at least). I started reading it because I had no idea how to solve this problem. It's been bugging me for a while now... well, not anymore :)

[EDIT] Link to the lecture notes ( http://www.ews.uiuc.edu/~kumar/lectures/lecture.10.3.pdf ) is dead.

[EDIT 4 years later] UVa link was dead.]]>

I guess below code shows what you and I think.

for(int i=0; i < N; i++)

{

p1F[i] = (p1a[i] >= 'a') ? 0 : 1;

p1S[i] = (p1b[i] >= 'a') ? 0 : 1;

p2F[i] = (p2a[i] >= 'a') ? 0 : 1;

p2S[i] = (p2b[i] >= 'a') ? 0 : 1;

int p1_temp = p1F[i] + p1S[i];

int p2_temp = p2F[i] + p2S[i];

//Dom V dom , Dom V rec , rec V Dom

if(p1_temp == 2 || p2_temp == 2)

child[i] = 1.0;

//(Dom, rec) V (Dom, rec)

if(p1_temp == 1 && p2_temp == 1)

child[i] = 0.75;

//Rec V (dom, rec)

if(p1_temp + p2_temp == 1)

child[i] = 0.5;

//rec V rec

if(p1_temp + p2_temp == 0)

child[i] = 0.0;

}]]>