公告

联系我:我的126邮箱: billhsu。 Locations of visitors to this page
<2008年8月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

  • 随笔 - 41
  • 文章 - 0
  • 评论 - 82
  • 引用 - 0

常用链接

留言簿(16)

随笔分类

随笔档案

相册

Game Dev

搜索

  •  

最新评论

阅读排行榜

评论排行榜

stredit problem
s and t are two strings.
Change string s into string t in the least steps.
In each step you can insert or delete a char of the string.
INPUT n1 s
n2 t
n1 is the length of string s
n2 is the length of string t
OUT the least steps
exp:
INPUT 4 abcd
6 aefbhd
OUT 4
#include<iostream>
#include
<string>

using namespace std;

string s1,s2;
int map[100];
int i,j,result[100];
int n1,n2,nc;

int main(){
    cin
>>n1>>s1>>n2>>s2;
    nc
=0;
    
for (i=0;i<n1;i++){
        
if ((j=s2.find(s1[i]))>=0){
          map[nc]
=j;
          s2.replace(j,
1," ");
          nc
++;
          }
          }
    result[nc
-1]=1;
    
for (i=nc-2;i>=0;i--){
        
for (j=i+1;j<nc;j++if ((map[i]<map[j])&&(result[i]<result[j])) result[i]=result[j];
        result[i]
++;
        }
    j
=0;
    
for (i=0;i<nc;i++if(result[i]>j) j=result[i];
    cout
<<n1+n2-j-j;
    system(
"pause");
    
return 0;
}



posted on 2008-08-01 13:41 Bill Hsu 阅读(286) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


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