【算法】算法測試題4：最長公共連續子串

MockingBird 發布于2019-08-23 11:36 / 3178人閱讀

摘要：問題描述鏈接來源牛客網給出兩個字符串可能包含空格找出其中最長的公共連續子串輸出其長度。示例輸入輸出解題思路比較兩個字符串找出的子串是否在中兩個指針和從頭遍歷到尾，找以開頭的子串中最長的在中的子串。

問題描述

鏈接：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云服務器最大連續子串算法最大公共子串算法最長公共子串字符串找子串算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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