Localhost8080

知行合一,自强不息

 

最短公共祖先(多个短字符串)

/*==================================================*\
 | 最短公共祖先(多个短字符串)
| pku 1699  pku 3192  pku 1795
\*==================================================*/
首先用一个数组save[i][j]来保存第j个串加在第i个串之后,第i个串所
增加的长度,比如alba  bacau,把bacau加在alba后alba所增加的长度
就为3.我们采用搜索的策略,以每一个串为第一个串进行搜索
for(i=1;i<=n;i++)dfs(i)//以第i个串为第一个串进行搜索。
剪枝:主要是在搜索过程中,当前面一些串的长度比当前已经找到的min还
大的话就剪去该枝。 

posted on 2010-05-05 15:54 superKiki 阅读(384) 评论(0)  编辑 收藏 引用


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


导航

统计

常用链接

留言簿

随笔档案

文章分类

我的好友

一些常去的网站

搜索

最新评论

阅读排行榜

评论排行榜