cALk9B - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int M = 1e9 + 7;

// string +dp 10th sep Amazon OA

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin >> s >> t;
    int m = s.size();
    int n = t.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = m - 1; i >= 0; i--)
    {
        dp[i][n] = dp[i + 1][n] + pow(2, m - i - 1);
    }
    for (int i = m - 1; i >= 0; i--)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            ll skip_count = dp[i + 1][j];
            ll count = 0;
            if (s[i] > t[j])
            {
                count += pow(2, m - i - 1);
            }
            else if (s[i] == t[j])
            {
                count += dp[i + 1][j + 1];
            }
            dp[i][j] = count + skip_count;
        }
    }

    cout << dp[0][0] << endl;

    return 0;
}