题意:求两串数字有多少个相同的子串,子串不要求连续。
思路:直接DP,dp[i][j] 代表A串长度为i、B串为j时满足条件的子串个数。转移dp[i][j] = dp[i -1][j] + dp[i][j – 1] – dp[i – 1][j – 1].后面是因为重复而减去的。
#include<bits/stdc++.h>
using namespace std;const int maxn = 1e3 + ;
const int mod = 1e9 + ;
int n, m, a[maxn], b[maxn], dp[maxn][maxn];int main(){
while(~scanf("%d%d", &n, &m)) {
for(int i = ; i <= n; i ++) scanf("%d", &a[i]);
for(int i = ; i <= m; i ++) scanf("%d", &b[i]); for(int i = ; i <= n; i ++) {
for(int j = ; j <= m; j ++) {
dp[i][j] = ((dp[i - ][j] + dp[i][j - ] - dp[i - ][j - ]) % mod + mod) % mod;
if(a[i] == b[j]) dp[i][j] = (dp[i][j] + dp[i -][j - ] + ) % mod;
}
}
printf("%d\n", dp[n][m]);
}
return ;
}