Codeforces 163A Substring and Subsequence：dp【子串与子序列匹配】-白红宇

Codeforces 163A Substring and Subsequence：dp【子串与子序列匹配】

阅读量：5040 次

发布时间：2019-06-12

本文共 1015 字，大约阅读时间需要 3 分钟。

题目链接：

题意：

　　给你两个字符串a,b，问你有多少对"(a的子串，b的子序列)"可以匹配。

题解：

　　表示状态：

　　　　dp[i][j] = pairs

　　　　a的子串以a[i]结尾，b的子序列以b[1 to j]结尾的方案数。

　　找出答案：

　　　　ans = ∑ dp[i][lb]

　　　　（la,lb代表a和b的长度）

　　如何转移：

　　　　dp[i][j] = dp[i][j-1]

　　　　if(a[i] == b[j]) dp[i][j] += dp[i-1][j-1]+1

　　　　a[i]和b[j]相同时，可以将dp[i][j]中的匹配都向后延伸一位。

　　　　同时(a[i],b[j])也是一种匹配，所以还要+1。

　　边界条件：

　　　　set dp = 0

AC Code:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAX_N 5005 5 #define MOD 1000000007 6  7 using namespace std; 8  9 int ans=0;10 int dp[MAX_N][MAX_N];11 char a[MAX_N];12 char b[MAX_N];13 14 int main()15 {16     scanf("%s%s",a+1,b+1);17     int la=strlen(a+1);18     int lb=strlen(b+1);19     memset(dp,0,sizeof(dp));20     for(int i=1;i<=la;i++)21     {22         for(int j=1;j<=lb;j++)23         {24             dp[i][j]=(dp[i][j-1]+(a[i]==b[j])*(dp[i-1][j-1]+1))%MOD;25         }26         ans=(ans+dp[i][lb])%MOD;27     }28     printf("%d\n",ans);29 }