【算法】算法测试题4：最长公共连续子串

MockingBird 发布于2019-08-23 11:36 / 3130人阅读

摘要：问题描述链接来源牛客网给出两个字符串可能包含空格找出其中最长的公共连续子串输出其长度。示例输入输出解题思路比较两个字符串找出的子串是否在中两个指针和从头遍历到尾，找以开头的子串中最长的在中的子串。

问题描述

链接：https://www.nowcoder.com/ques...
来源：牛客网

给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。

输入描述

输入为两行字符串（可能包含空格），长度均小于等于50.

输出描述

输出为一个整数，表示最长公共连续子串的长度。

示例

输入

abcde
abgde

输出

解题思路

比较两个字符串str1,str2
找出str1的子串是否在str2中
两个指针i和j：i从头遍历到尾，找以str1[i]开头的子串中最长的在str2中的子串。j从尾倒着走，直到找到子串str1(i,j)在str2中为止。

JavaScript代码

let str1 = new String(readline());
let str2 = new String(readline());
let count = 0;
//print(str1);
//print(str2);
for(let i = 0; i < str1.length; i++){
    for(let j = str1.length; j > i; j--){
        let strc = str1.slice(i, j);
        //print(strc);
        if(str2.indexOf(strc)!=-1){
            let len = strc.length;
            if(len > count){
                count = len;
            }
            break;
        }
    }
}
print(count);

GPU云服务器云服务器最大连续子串算法最大公共子串算法最长公共子串字符串找子串算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97205.html

javascript 最长公共子序列

摘要：但不是和的最长公共子序列，而序列和也均为和的最长公共子序列，长度为，而和不存在长度大于等于的公共子序列。最长公共子序列给定序列和，从它们的所有公共子序列中选出长度最长的那一个或几个。为和的最长公共子序列长度。最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。LCS问...

Xufc 2019-08-22 13:52 评论0 收藏0
[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。说明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 评论0 收藏0
一道算法题：求出异或和为零的最长连续子串

摘要：最近看见一道算法题，本着见题解题的学习心态解决了它，由于目前正在研究正则表达式，所以就从正则的方向入手了题目如下输入个整数，中间用空格隔开，求出异或和为的最长连续子串。要求输出子串的长度子串在输入的数组中的起始位置和结束位置。最近看见一道算法题，本着见题解题的学习心态解决了它，由于目前正在研究正则表达式，所以就从正则的方向入手了：题目如下：输入N个整数，中间用空格隔开，求出异或和为...

刘玉平 2019-07-30 18:00 评论0 收藏0
[算法笔记]动态规划之最长公共子串和最长公共子序列

摘要：源代码管理中，指令，可以查找出编辑前后文件的差异，这是基于动态规划实现的。编辑距离，判断字符串的相似程度，也是基于动态规划计算。本文是《算法图解》笔记应用场景一切脱离实际应用场景的算法都是耍流氓！生物学家根据最长公共序列来确定 DNA 链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。源代码管理中，git diff指令，可以查找出编辑...

DandJ 2019-07-30 15:40 评论0 收藏0
算法设计 - LCS 最长公共子序列&&最长公共子串 &&LIS 最

摘要：若且，则是和的最长公共子序列若且，则是和的最长公共子序列。递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算和的最长公共子序列时，可能要计算出和及和的最长公共子序列。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党本章讲解： 1. LCS（最长公共子序列）O(n^2)的时间复杂...

weizx 2019-08-14 12:07 评论0 收藏0