Untitled
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