首页 > 其他 > 详细

LCS

时间:2016-01-16 19:23:04      阅读:122      评论:0      收藏:0      [点我收藏+]
size_t LCS(const std::string& x, const std::string& y)
{
    if (x.empty () || y.empty ()){
        return 0;
    }
    const size_t width  = x.length () + 1;
    const size_t height = y.length () + 1;
    std::vector<size_t> results(width);
    for (size_t i = 1; i != height; ++i){
        const auto key = y[i - 1];
        for (size_t j = 1; j != width; ++j){
            if (results[j] == results[j - 1]){
                if (x[j - 1] == key){
                    ++results[j];
                }
            }else{
                results[j] = std::max(results[j], results[j - 1]);
            }
        }
    }
    return results.back ();
}

 技术分享

LCS

原文:http://www.cnblogs.com/wuOverflow/p/5135962.html

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