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

MockingBird 發(fā)布于2019-08-23 11:36 / 3186人閱讀

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

問題描述

鏈接：https://www.nowcoder.com/ques...
來源：?？途W(wǎng)

給出兩個字符串（可能包含空格）,找出其中最長的公共連續(xù)子串,輸出其長度。

輸入描述

輸入為兩行字符串（可能包含空格），長度均小于等于50.

輸出描述

輸出為一個整數(shù)，表示最長公共連續(xù)子串的長度。

示例

輸入

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云服務(wù)器云服務(wù)器最大連續(xù)子串算法最大公共子串算法最長公共子串字符串找子串算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/97205.html

相關(guān)文章

javascript 最長公共子序列

摘要：但不是和的最長公共子序列，而序列和也均為和的最長公共子序列，長度為，而和不存在長度大于等于的公共子序列。最長公共子序列給定序列和，從它們的所有公共子序列中選出長度最長的那一個或幾個。為和的最長公共子序列長度。最長公共子序列（Longest Common Subsequence LCS）是從給定的兩個序列X和Y中取出盡可能多的一部分字符，按照它們在原序列排列的先后次序排列得到。LCS問...

Xufc 2019-08-22 13:52 評論0 收藏0
[算法總結(jié)] 搞定 BAT 面試——幾道常見的子符串算法題

摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數(shù)值為或者字符串不是一個合法的數(shù)值則返回。說明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評論0 收藏0
一道算法題：求出異或和為零的最長連續(xù)子串

摘要：最近看見一道算法題，本著見題解題的學(xué)習(xí)心態(tài)解決了它，由于目前正在研究正則表達(dá)式，所以就從正則的方向入手了題目如下輸入個整數(shù)，中間用空格隔開，求出異或和為的最長連續(xù)子串。要求輸出子串的長度子串在輸入的數(shù)組中的起始位置和結(jié)束位置。最近看見一道算法題，本著見題解題的學(xué)習(xí)心態(tài)解決了它，由于目前正在研究正則表達(dá)式，所以就從正則的方向入手了：題目如下：輸入N個整數(shù)，中間用空格隔開，求出異或和為...

劉玉平 2019-07-30 18:00 評論0 收藏0
[算法筆記]動態(tài)規(guī)劃之最長公共子串和最長公共子序列

摘要：源代碼管理中，指令，可以查找出編輯前后文件的差異，這是基于動態(tài)規(guī)劃實現(xiàn)的。編輯距離，判斷字符串的相似程度，也是基于動態(tài)規(guī)劃計算。本文是《算法圖解》筆記應(yīng)用場景一切脫離實際應(yīng)用場景的算法都是耍流氓！生物學(xué)家根據(jù)最長公共序列來確定 DNA 鏈的相似性，進(jìn)而判斷兩種動物或疾病有多相似。最長公共序列還被用來尋找多發(fā)性硬化癥治療方案。源代碼管理中，git diff指令，可以查找出編輯...

DandJ 2019-07-30 15:40 評論0 收藏0
算法設(shè)計 - LCS 最長公共子序列&&最長公共子串 &&LIS 最

摘要：若且，則是和的最長公共子序列若且，則是和的最長公共子序列。遞歸結(jié)構(gòu)容易看到最長公共子序列問題具有子問題重疊性質(zhì)。例如，在計算和的最長公共子序列時，可能要計算出和及和的最長公共子序列。雖是讀書筆記，但是如轉(zhuǎn)載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨本章講解： 1. LCS（最長公共子序列）O(n^2)的時間復(fù)雜...

weizx 2019-08-14 12:07 評論0 收藏0