codeforces 163A A. Substring and Subsequence(dp)

题目链接：

codeforces 163A

题目大意：

给出两个字符串，求第一个字符串的子串和第二个字符串的子序列相等的个数。

题目分析：

• 定义状态dp[i][j]表示s的子串以i结尾，t的子序列以j结尾的相等的对数。
• 转移方程很简单，就是当某一位上两个字符相等的时候，
  dp[i][j]=∑k<jdp[i−1][k]
  
  

  ---

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 5007
using namespace std;
int dp[MAX][MAX],n,m;
char s[MAX],t[MAX];
int sum[MAX];
const int mod = 1e9+7;
int main ( )
{
while ( ~scanf ( "%s %s" , s , t ) )
{
n = strlen ( s );
m = strlen ( t );
memset ( dp , 0 , sizeof ( dp ) );
int ans = 0;
for ( int i = 0; i < n ; i++ )
if ( s[i] == t[0] )
{
dp[i][0] = 1;
ans++;
}
for ( int i = 1 ; i < m ; i++ )
if ( s[0] == t[i] )
{
dp[0][i] = 1;
ans++;
}
for ( int i = 1; i < n ; i ++ )
{
sum[0] = dp[i-1][0];
for ( int j = 1 ; j < m ; j++ )
{
sum[j] = sum[j-1] + dp[i-1][j];
sum[j] %= mod;
}
for ( int j = 1; j < m ; j++ )
{
if ( s[i] == t[j] )
dp[i][j] = sum[j-1] + 1;
else
dp[i][j] = 0;
dp[i][j] %= mod;
ans += dp[i][j];
ans %= mod;
}
}
printf ( "%dn" , ans );
}
}

最后

以上就是舒服百褶裙为你收集整理的codeforces 163A A. Substring and Subsequence(dp)的全部内容，希望文章能够帮你解决codeforces 163A A. Substring and Subsequence(dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。