Untitled

 avatar
unknown
plain_text
5 months ago
1.4 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 k = 0; k < m; k++)
    {
        for(int i = 0; i < n; i++)
        {

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


           if (thienthan[i] == s[k])
            {
                if (k > 0)
                {
                    if (i > 0) g[i][k] = (g[i][k] + f[i - 1][k - 1]) % MOD;
                    else if (i == 0) g[i][k] = 1;
                }
                else if (k == 0 && i == 0) g[i][k] = 1;
            } else
                if (i > 0) 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