LCS 最长公共字串

迷南。 2022-08-07 01:48 224阅读 0赞

#include
#include

int c[10000][10000];
char str1[10000];
char str2[10000];

void func(int m,int n) {
if(m < 0 || n < 0)
return ;
int i,j;
for(i = 0 ; i < m ; i++)
for(j = 0 ;j < n;j++)
c[i][j] = 0;
int besti = 0,bestj = 0;
int count = 0;

for(i = 0; i < m;i++)
for(j = 0;j<n;j++)
if(str1[i] == str2[j]){
if(i ==0 || j ==0)
c[i][j] = 1;
else
c[i][j] = c[i-1][j-1] + 1;
}
else
c[i][j] = 0;

for(i = 0;i < m ;i++)
for(j = 0; j < n ;j++)
if(c[i][j] > count){
count = c[i][j];
besti = i;
bestj = j;
}

for(i = 0 ; i < m ;i++)
{
for(j = 0 ; j < n;j++)
{
printf(“%d “,c[i][j]);
}
printf(“\n”);
}

if(count > 0)
for(i = besti - count + 1; i <= besti;i++)
printf(“%c”,str1[i]);

}
int main(){
int m = 0;
int n = 0;
scanf(“%s”,&str1);
scanf(“%s”,&str2);
m = strlen(str1);
n = strlen(str2);
func(m,n);
scanf(“%d”);
}

发表评论

表情：
评论列表 （有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LCS 最长公共子序列

    首先要明白什么是子序列，什么是子串； 设：主串长度为n； 子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；        

    绝地灬酷狼绝地灬酷狼/ 0 赞/ 249 阅读