2018.11.2 2018NOIP冲刺之最短公共父串

很有意思的一个题


试题描述
给定字符串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