POJ 1458 最长公共子列

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 //================================================
 5 string str1,str2;
 6 int c[1000][1000];//c[i][j]表示到x中的第i个和y中的第j个的已有最长字串的长度
 7 int max(int a,int b)
 8 {
 9     return (a>b?a:b);
10 }
11 int main()
12 {
13     while(cin>>str1>>str2)
14     {
15        //int counter=0;二货!!!!!!!!!!!
16         memset(c,0,sizeof(c));
17         int s1=str1.size();
18         int s2=str2.size();
19         //for(int i=0;i<s1;++i) c[i][0]=0;二货!!字符串时str[0]也是有用的!!
20         //for(int j=0;j<s2;++j) c[0][j]=0;
21         for(int i=1;i<=s1;++i)
22         {
23             for(int j=1;j<=s2;++j)
24             {
25                 if(str1[i-1]==str2[j-1])//处理字符串时又不能从一开始的时候,可以在判断的时候迂回一下
26                 {
27                     c[i][j]=c[i-1][j-1]+1;//通过上一个表示自己,i和j在c[i][j]表示个数时都为加一以后所负责表示。
28                 }
29                 else
30                 {
31                     c[i][j]=max(c[i-1][j],c[i][j-1]);
32                 }
33             }
34         
35         }
36        cout<<c[s1][s2]<<endl;//通过最后递推结果来说明。
37     }
38 }
39 

posted on 2011-11-27 16:34 四也 阅读(197) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜