題意：輸入兩個(gè)A-Z組成的字符串，找到一個(gè)最短的串，使得兩個(gè)串均是他的子串。

思路：最長(zhǎng)公共序列問(wèn)題。當(dāng)i和j相等時(shí)，dp[i][j]=dp[i-1][j-1]，不等時(shí)就是max(dp[i-1][j],dp[i][j-1]),如果當(dāng)前的統(tǒng)計(jì)的數(shù)量大于s就置為s，否則加上s。

code：

#include <bits/stdc++.h> using namespace std;#define cls(a,c) memset(a,c,sizeof (a)) #define ft(i,s,t) for (int i=s;i<=t;i++) const int N=32,M=1005;char s1[N],s2[N]; int dp[N][N],num[N][N]; int s,cnt; void sol(int i,int j){if (dp[i][j]==s) num[i][j]+=cnt;else if (dp[i][j]>s) dp[i][j]=s,num[i][j]=cnt; } int main() {int T;scanf("%d",&T);getchar();ft(ca,1,T){cls (dp,63);cls(num,0);gets(s1+1);gets(s2+1);int len1=strlen(s1+1),len2=strlen(s2+1);dp[1][1]=0;num[1][1]=1;ft(i,1,len1+1) ft(j,1,len2+1){s=dp[i][j]+1,cnt=num[i][j];if (s1[i]==s2[j]) sol(i+1,j+1);else sol(i+1,j),sol(i,j+1);}printf("Case #%d: %d %d\n",ca,dp[len1+1][len2+1],num[len1+1][len2+1]);} }

總結(jié)

以上是生活随笔為你收集整理的uva 10723——Cyborg Genes的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。