登录  /  注册
博主信息
博文 82
粉丝 0
评论 1
访问量 125597
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
最长子序列初探
子龙的博客搬家啦httpswwwcnblogscomZiLongZiLong
原创
896人浏览过

今天也尝试写一下最长公共子串,基本思路就是穷举,找到两个串中相等的元素,然后把它们的index记录下来,再通过for-in循环求出最长的子串,

2018-4-4 今天早上的这段代码目前能求出最长长度,尚不完善。

2018-4-6 已经可以得到公共字串的长度和详细数据了

function mostLong ( arr1,arr2 ){
    let result = {};
    var arr1Length =  arr1.length ;
    var arr2length = arr2.length;
    for(let i = 0; i < arr1Length; i++  ){
        for( let j = 0 ; j < arr2length; j++ ){
            if( arr1[i] === arr2[j] ){
                result[i + '$' + j] = {
                isMatch:true,
                }
            }
        }
    }
    result
    let subsequence = {
        length:0,
        key:[]
     };//子序列
    for (let key in result) {
        if (result.hasOwnProperty(key)) {
            let index1 = key.split('$')[0] //第一个数组的下标
            let index2 = key.split('$')[1];
            var count = 0//
            while( result[index1 + '' +  index2] ){
                count++;
                if( count > subsequence.length ){
                    subsequence.length = count;
                    let temp1 = index1,temp2=index2,//向上追迹 已经遍历过的数据
                    temp = [];
                    for(;result[temp1 + '$' +  temp2];){
                        temp.push(temp1 + '$' + temp2);
                        temp1--;
                        temp2--
                    }
                    temp.reverse();
                    subsequence.key = temp;
                    index1++;
                    index2++;
                    }else{
                    index2++;
                    index1++;
                    }
            }
        }
    }
    return subsequence
}


本博文版权归博主所有,转载请注明地址!如有侵权、违法,请联系admin@php.cn举报处理!
全部评论 文明上网理性发言,请遵守新闻评论服务协议
1条评论
舍。 2018-04-25 17:49:49
测试
1楼
作者最新博文
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号

  • 登录PHP中文网,和优秀的人一起学习!
    全站2000+教程免费学