String Game “红旗杯”第十四届吉林省大学生程序设计竞赛_Java

String Game “红旗杯”第十四届吉林省大学生程序设计竞赛

String Game

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 309 Accepted Submission(s): 43

Problem Description

Clair and Bob play a game.Clair writes a string of lowercase characters, in which Bob sets the puzzle by selecting one of his favorite subsequence as the key word of the game. But Bob was so stupid that he might get some letters wrong.

Now Clair wants to know whether Bob’s string is a subsequence of Clair’s string. and how many times does Bob’s string appear as a subsequence in Clair’s string. As the answer maybe too large, you should output the answer modulo 109+7.

Input

The input may contain multiple test cases.

Each test case contains exactly two lines. The first line is Clair’s string, and the second line is Bob’s string. The length of both strings are no more than 5000.

Output

For each test case, output one line, including a single integer representing how many times Bob’s string appears as a subsequence in Clair’s string. The answer should modulo 109+7.

Sample Input

eeettt
et
eeettt
te

Sample Output

9
0

思路：

dp+排列组合公式的理解

Copy大佬至代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<cstring>
#include<string>
#include<iostream>
#define ll long long
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s1, s2;
    while (cin >> s1 >> s2) {
        ll i, j, h, a[1001], max = 0;
        for (i = 0; i < s2.size(); i++)a[i] = 0;
        for (i = 0; i < s1.size(); i++) {
            for (j = s2.size() - 1; j >= 0; j--) {
                if (s1[i] == s2[j]) {
                    if (j != 0) a[j] += a[j - 1];
                    else a[j]++;
                    a[j] %= 1000000007;
                }
            }
        }
        cout << a[s2.size() - 1] << endl;
    }
    return 0;
}