LRJ入门经典-0906最短公共父串305

原题

LRJ入门经典-0906最短公共父串305

难度级别：B； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B

试题描述

给定字符串A和字符串B，要求找一个最短的字符串，使得字符串A和B均是它的子序列。

输入

输入包含两行，每行一个字符串，分别表示字符串A和字符串B。（串的长度不超过30）

输出

输出A和B最短公共父串的长度以及在该长度下可以生成的父串个数，用空格隔开。

输入示例

ABAAXGF AABXFGA

输出示例

10 9

其他说明

ABAAXGF和AABXFGA的最短公共父串之一是AABAAXGFGA，长度为10，满足该长度的父串一共由9个。

分析

代码

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long LL;

const int MAXL=32;

char S1[MAXL],S2[MAXL];

LL len1,len2,Pa[MAXL][MAXL],Pac[MAXL][MAXL];

LL dpPa(int i1,int i2)

{

	LL& ans=Pa[i1][i2];

	if(ans!=-1) return ans;

	if(i1==0 || i2==0) return ans=max(i1,i2);

	if(S1[i1]==S2[i2]) return ans=dpPa(i1-1,i2-1)+1;

	int a=dpPa(i1-1,i2);

	int b=dpPa(i1,i2-1);

	return ans=min(a,b)+1;

}

LL dpPac(int i1,int i2)

{

	LL& ans=Pac[i1][i2];

	if(ans!=-1) return ans;

	if(i1==0 || i2==0) return ans=1;

	if(S1[i1]==S2[i2]) return ans=dpPac(i1-1,i2-1);

	LL sl1=dpPa(i1-1,i2),sl2=dpPa(i1,i2-1);

	if(sl1==sl2) ans=dpPac(i1-1,i2)+dpPac(i1,i2-1);

	else if(sl1<sl2) ans=dpPac(i1-1,i2);

	else ans=dpPac(i1,i2-1);

	return ans;

}

int main()

{

	gets(S1+1),gets(S2+1);

	len1=strlen(S1+1),len2=strlen(S2+1);

	memset(Pa,-1,sizeof(Pa)),memset(Pac,-1,sizeof(Pac));

	cout<<dpPa(len1,len2)<<" "<<dpPac(len1,len2)<<endl;

	/*for(int i=0;i<=len1;i++)

	{

		for(int j=0;j<=len2;j++) cout<<Pa[i][j]<<" ";

		cout<<endl;

	}

	cout<<endl;

	for(int i=0;i<=len1;i++)

	{

		for(int j=0;j<=len2;j++) cout<<Pac[i][j]<<" ";

		cout<<endl;

	}*/

	return 0;

}