很有意思的一个题
|
试题描述
|
|
给定字符串A和字符串B，要求找一个最短的字符串，使得字符串A和B均是它的子序列。
|
|
输入
|
|
输入包含两行，每行一个字符串，分别表示字符串A和字符串B。（串的长度不超过30）
|
|
输出
|
|
输出A和B最短公共父串的长度以及在该长度下可以生成的父串个数，用空格隔开。
|
|
输入示例
|
|
ABAAXGF
AABXFGA |
|
输出示例
|
|
10 9
|
|
其他说明
|
|
ABAAXGF和AABXFGA的最短公共父串之一是AABAAXGFGA，长度为10，满足该长度的父串一共有9个。
|
看到这个题有没有想到最长公共子序列？？这个题情况类似
我们用dp[i][j]表示第一个串前i位以及第二个串前j位最短公共父串的长度，用f[i][j]同理表示有几个最短公共父串
不难得到
当a[i]==b[j]时 dp[i][j]=dp[i-1][j-1]+1
否则dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1（参见最长公共子序列）
同样的
当a[i]==b[j]时说明串的个数应该从f[i-1][j-1]的位置转移 于是f[i][j]=f[i-1][j-1]
否则：
（1）当dp[i-1][j]<dp[i][j-1]时说明从f[i-1][j]转移的父串最短 于是f[i][j]=f[i-1][j]
（2）当dp[i][j-1]<dp[i-1][j]时说明从f[i][j-1]转移的父串最短 于是f[i][j]=f[i][j-1]
（3）当dp[i-1][j]==dp[i][j-1]时说明两边转移的父串都是最短 于是f[i][j]=f[i-1][j]+f[i][j-1]
上代码
#include<iostream> #include<cstring> using namespace std; int dp[105][105],f[105][105],len1,len2,cnt; char a[105],b[105]; int main() { gets(a+1),gets(b+1); len1=strlen(a+1),len2=strlen(b+1); for(int i=0;i<=max(len1,len2);i++)dp[i][0]=dp[0][i]=i; for(int i=0;i<=max(len1,len2);i++)f[i][0]=f[0][i]=1; for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(a[i]==b[j]) { dp[i][j]=dp[i-1][j-1]+1; f[i][j]=f[i-1][j-1]; } else { dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1; if(dp[i-1][j]<dp[i][j-1])f[i][j]=f[i-1][j]; else if(dp[i][j-1]<dp[i-1][j])f[i][j]=f[i][j-1]; else f[i][j]=f[i-1][j]+f[i][j-1]; } } } printf("%d %d",dp[len1][len2],f[len1][len2]); }
原文：https://www.cnblogs.com/qxds/p/9897561.html