1577
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> #include <hash_map> using namespace std; //using namespace stdext; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "feelgood.in" #define OUTPUT_FILE "feelgood.out" unsigned int m[2010][2010] = {0}; unsigned int r[2010][2010] = {0}; unsigned int mod = 1000000007; char s1[3000]; char s2[3000]; int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif scanf("%s", s1); scanf("%s", s2); int l1 = strlen(s1); int l2 = strlen(s2); for(int i = 0; i < 2010; i++) { r[0][i] = 1; r[i][0] = 1; } for(int i = 0; i < l1; i++) { for(int j = 0; j < l2; j++) { int ii = i+1; int jj = j+1; if(s1[i] == s2[j]) { m[ii][jj] = m[ii-1][jj-1] + 1; } else { m[ii][jj] = max(m[ii-1][jj], m[ii][jj-1]); } if(s1[i] == s2[j]) r[ii][jj] = r[ii-1][jj-1]; else { if(m[ii-1][jj] == m[ii][jj]) r[ii][jj] = ((r[ii][jj] % mod) + (r[ii-1][jj] % mod)) % mod; if(m[ii][jj-1] == m[ii][jj]) r[ii][jj] = ((r[ii][jj] % mod) + (r[ii][jj-1] % mod)) % mod; } } } cout << r[l1][l2]; return 0; }
page revision: 0, last edited: 09 May 2008 17:57