Untitled

 avatar
unknown
plain_text
5 months ago
1.2 kB
3
Indexable
#include <bits/stdc++.h>
#define F first
#define S second
#define el cout << '\n'
#define maxn 101
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define For(i,a,b) for ( int i = a;  i <= b; i++)
#define MOD 1000000007
using namespace std;

string s, acquy, thienthan;
int f[maxn][maxn], g[maxn][maxn];
int main()
{
    faster
    cin >> s >> acquy >> thienthan;

    int n = acquy.size(); int m = s.size();

    for(int i = 0; i < n; i++)
    {
        int dem1 = 0, dem2 = 0;
        if (acquy[i] == s[0]) dem1++;
        if (thienthan[i] == s[0]) dem2++;
        f[i][0] = dem1; g[i][0] = dem2;
    }

    for(int k = 1; k < m; k++)
    {
        for(int i = 0; i < n; i++)
        {

            if (acquy[i] == s[k])
            {
                f[i][k] = (f[i][k] + g[i - 1][k - 1]) % MOD;
            } else f[i][k] = (f[i - 1][k]) % MOD;


           if (thienthan[i] == s[k])
            {
                g[i][k] = (g[i][k] + f[i - 1][k - 1]) % MOD;
            } else g[i][k] = (g[i - 1][k]) % MOD;

        }
    }
    int res = (f[n - 1][m - 1] + g[n - 1][m - 1]) % MOD;
    cout << res;

}
Editor is loading...
Leave a Comment