首页 > 其他 > 详细

HackerRank "Square Subsequences" !!!

时间:2016-06-18 10:14:13      阅读:222      评论:0      收藏:0      [点我收藏+]

Firt thought: an variation to LCS problem - but this one has many tricky detail.

I learnt the solution from this link:
https://github.com/wangyongliang/Algorithm/blob/master/hackerrank/Strings/Square%20Subsequences/main.cc

And here is his code with my comments..

技术分享
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

long long lcs(string &a, string &b)
{
    int sizea = a.length();
    int sizeb = b.length();
    vector<vector<long long>> dp(sizea, vector<long long>(sizeb));
    
    //  We only consider prefixes with a[0] matched
    //  to avoid duplicate counting
    for(int i = 0; i < sizeb; i ++)
    {
        if(a[0] == b[i]) dp[0][i] = 1;
        if(i) dp[0][i] += dp[0][i - 1]; // we count accumulated
        dp[0][i] %= 1000000007;
    }
    
    for(int i = 1; i < sizea; i ++)
    {
        dp[i][0]  = dp[i - 1][0]; // all from dp[0][0]; part of init
        for(int j = 1; j < sizeb; j ++)
        {            
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // accumulated version of LCS.
            if(a[i] != b[j]) dp[i][j] -= dp[i-1][j-1]; // TODO: need 2nd thought on why
            dp[i][j] %= 1000000007;
        }
    }
    return dp.back().back();
}

int main() 
{
    int t; cin >> t;
    string str;
    while(t--)
    {
        cin >> str;
        long long ans = 0;
        for(int i = 1; i < str.length(); i ++)
        {
            string sb = str.substr(i, str.length()- i);
            string sa = str.substr(0, i);
            ans += lcs(sb, sa);
            ans %= 1000000007;
        }
        cout << ans << endl;
    }
        
    return 0;
}
View Code

 

HackerRank "Square Subsequences" !!!

原文:http://www.cnblogs.com/tonix/p/5595674.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!