poj1458

题目

Common Subsequence

题面

Cry对于泡妹子十分不熟练，在见到小姐姐后十分紧张，这时，他想起了czh对他的教诲，于是他决定尽可能找到自己与小姐姐的共同点。Cry靠他强大的人格魅力获取了小姐姐的基因片段，同时他也提供了自己的基因片段，现在我们假定，他们的公共点个数为两个片段的最长公共子序列中元素个数，cry有点方因为他完全不会做，他的幸福生活只能靠在座的各位了！

Input

多组输入，每行有两个字符串，根据本czh的经验，如果对小姐姐问来问去是很失礼的一件事，因此每个基因片段长度最好不超过1000吧

Output

每行一个答案，表示每组数据中他们的公共点个数

Examples

Input

abcfbc         abfcab
programming    contest
abcd           mnp

Output

4
2
0

思路

这个题于poj1887有相似之处，寻找最长序列数因为这个题目有2个序列所以以一个为模板，逐个变化另一个字符串的开头字母，不断更新最后输出答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<string.h>
int len;
char s1[1010],s2[1010];
int num[1010];
int solve(int k)
{
    int l=1,r=len;
    while(l<r)
    {
       int mid=(l+r)/2;
       if(num[mid]>=k)
       {
           r=mid;
       }
       else
       l=mid+1;
    }
    return r;
}
int main()
{
    //freopen("F:/y.txt","r",stdin);
    while(~scanf("%s %s",s1,s2))
    {
       len=0;
       num[len]=-1;
       int k1=strlen(s1),k2=strlen(s2);
       for(int i=0;i<k1;i++)
       {
           for(int j=0;j<k2;j++)
           {
              if(s1[i]==s2[j])
              {
                  if(j>num[len])
                  {
                     num[++len]=j;
                     break;
                  }
                  else
                  {
                     num[solve(j)]=j; 
                  }
              }
           }
       }
       printf("%d\n",len);
    }
    return 0;
}