前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >整理的一些模版LCS(连续和非连续)

整理的一些模版LCS(连续和非连续)

作者头像
Gxjun
发布2018-03-26 14:48:20
6190
发布2018-03-26 14:48:20
举报
文章被收录于专栏:ml

    对于连续的最大串,我们称之为子串....非连续的称之为公共序列..

代码:

非连续连续

代码语言:javascript
复制
 1 int LCS(char a[],char b[],char sav[]){
 2     int lena=strlen(a);
 3     int lenb=strlen(b);
 4     int i,j;
 5      vector<vector<int> >mat(lena+1);
 6     for(int i=0;i<=lena;i++)
 7       mat[i].resize(lenb+1,0);
 8     for(i=1;i<=lena;i++){
 9       for(j=1;j<=lenb;j++){
10         if(a[i-1]==b[j-1])
11           mat[i][j]=mat[i-1][j-1]+1;
12         else
13           mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
14         }
15     }
16     i=lena-1;
17     j=lenb-1;
18     int k=0;
19  while(i!=-1&&j!=-1) {
20     if(a[i]==b[j]){
21        sav[k++]=a[i];
22         i--;
23         j--;
24   }
25   else{
26     if(mat[i+1][j+1]==mat[i][j]){
27         i--;
28         j--;
29    }
30    else{
31     if(mat[i][j+1]>=mat[i+1][j]) i--;
32      else j--;
33    }
34   }
35  }
36  return k;
37 }

连续子串

代码:

代码语言:javascript
复制
 1 int LCS(char a[],char b[],char sav[]){
 2     int lena=strlen(a);
 3     int lenb=strlen(b);
 4     int i,j,k=0,x=0;
 5     vector<vector<int> >lcs(lena+1);
 6     for(int i=0;i<=lena;i++)
 7       lcs[i].resize(lenb+1,0);
 8     for(i=1;i<=lena;i++){
 9       for(j=1;j<=lenb;j++)
10         if(a[i-1]==b[j-1]){
11            lcs[i][j]=lcs[i-1][j-1]+1;
12            if(k<lcs[i][j]){
13                x=i;
14                k=lcs[i][j];
15            }
16         }
17     }
18     strncpy(sav,a+(x-k),k);
19     return k;
20 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2014-08-25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档