2013
12-23

# Two Brothers

Though Yueyue and Lele are brothers , they are very different.
For example, Yueyue is very hard in study, especially in writing compositions. To make the composition looks nice , he will not use the same word twice. While Lele is very lazy, and he sometimes copys his brother’s homework.Last week, their teacher asked them to write a composition named “My Mother”, they handed the same composition. The teacher was very angry , but Lele just answered “We have the same mother , why should our compositions be different ?”

Now,the teacher is asking Yueyue and Lele to write the compositions again, and he wants to calculate the length of longest common subsequence of words occuring in the two compositions. Can you help him ?

There will be many test cases in the problem.Please process to the end of file.
Each case contains two lines.
The first line means Yueyue’s composition and the second line means Lele’s composition.
Each composition will contains no more than 10^4 words . And each word will contains less than 40 characters.Each character will only be in a~z or A~Z.
Two words will be separated by a blank.To make the problem easier, there will be a “#” at the end of each composition.

For each case , output a integer in a line represents the length of longest common subsequence of words occuring in the their compositions.

aa bb cc #
aa cc bb #

2
Hint

Huge input,the C function scanf() will work better than cin

int LIS(int str[],int len)
{
int max,left,right,i,mid;
lis[1] = str[0];
max = 1;
for(i=1; i<len; i++)
{
if(str[i] > lis[max])
{
lis[++max] = str[i];
}
else
{
left = 1;
right = max;
while(left <= right)
{
mid = (left+right)/2;
if(str[i] > lis[mid])
left = mid + 1;
else if(str[i] < lis[mid])
right = mid - 1;
else
break;
}
lis[left] = str[i];
}
}
return max;
}

#include <iostream>
using namespace std;

#define  MAX_INPUT_NUM 10000
int limit[MAX_INPUT_NUM];

int main()
{
int inputNum;
int curNum;
int tempBegin;
int tempEnd;
int tempMiddle;
int len;

while(cin>>inputNum){
len=0;//the count
for(int i=0;i<inputNum;i++){
cin>>curNum;

tempEnd=len;
tempBegin=1;
tempMiddle=0;

while(tempBegin<=tempEnd){
tempMiddle=(tempBegin+tempEnd)>>1;
limit[tempMiddle] >=curNum ? tempEnd=tempMiddle-1 : tempBegin=tempMiddle+1;
}
limit[tempBegin]=curNum;//first position whose value >=curNum ,if no existed ,is end+1
tempBegin >len ? len++ :NULL;

}//end for ..
cout<<len<<endl;
}//end while

return 0;
}