题目链接
解题思路
第一思路：
1.用(length[i][j])表示(a)串的前(i)个字符与(b)串的前(j)个字符重叠的最长子串长度
2.用(num[i][j])表示 (a)串的前(i)个字符与(b)串的前(j)个字符重叠的最长子串个数
则求(length[i][j],num[i][j])时有以下递推关系：
*(length[i][j]:)
如果当前两串结尾字符相等，则(length[i][j]=length[i-1][j-1]+1)
否则(length[i][j]=max(length[i-1][j],length[i][j-1]))
*(num[i][j]:)
如果(length[i][j])与(length[i-1][j])相等，(num[i][j])可加(num[i-1][j])
如果(length[i][j])与(length[i][j-1])相等，(num[i][j])可加(num[i][j-1])
如果(length[i][j])与(length[i-1][j-1])相等，则(num[i][j])多加了个(num[i-1][j-1])，需要减去
代码：
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b?a:b)
int length[5010][5010],num[5010][5010],w=100000000;
char a[5010],b[5010];
int main(){
int i,j,la,lb;
scanf("%s%s",a,b);
la=strlen(a)-1;lb=strlen(b)-1;
for(i=0;i<=la;i++)num[i][0]=1;
for(i=0;i<=lb;i++)num[0][i]=1;
for(i=1;i<=la;i++){
for(j=1;j<=lb;j++){
if(a[i-1]==b[j-1]){
length[i][j]=length[i-1][j-1]+1;
num[i][j]=num[i-1][j-1];
}
else{
length[i][j]=max(length[i-1][j],length[i][j-1]);
if(length[i][j]==length[i-1][j-1])num[i][j]-=num[i-1][j-1];
num[i][j]+=w;
}
if(length[i-1][j]==length[i][j])num[i][j]+=num[i-1][j];
if(length[i][j-1]==length[i][j])num[i][j]+=num[i][j-1];
num[i][j]%=w;
length[i][j]%=w;
}
}
printf("%d
%d",length[la][lb],num[la][lb]);
return 0;
}
提交效果
优化代码
考虑优化代码。
考虑到(length)、(num)数组当前状态都只与上一状态相关，可以用滚动数组优化空间和时间。
AC代码
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b?a:b)
int length[2][5010],num[2][5010],w=100000000;
char a[5010],b[5010];
int main(){
int i,j,la,lb;
scanf("%s%s",a,b);
la=strlen(a)-1;lb=strlen(b)-1;
for(i=0;i<=lb;i++)num[0][i]=1;
num[1][0]=1;
for(i=1;i<=la;i++){
int temp=i%2;
for(j=1;j<=lb;j++){
num[temp][j]=0;//滚动数组一定要注意这一点
if(a[i-1]==b[j-1]){
length[temp][j]=length[temp^1][j-1]+1;
num[temp][j]=num[temp^1][j-1];
}
else{
length[temp][j]=max(length[temp^1][j],length[temp][j-1]);
if(length[temp][j]==length[temp^1][j-1])num[temp][j]-=num[temp^1][j-1];
num[temp][j]+=w;
}
if(length[temp^1][j]==length[temp][j])num[temp][j]+=num[temp^1][j];
if(length[temp][j-1]==length[temp][j])num[temp][j]+=num[temp][j-1];
num[temp][j]%=w;
length[temp][j]%=w;
}
}
printf("%d
%d",length[la%2][lb],num[la%2][lb]);
return 0;
}
提交效果
