怎么用Java輸出最長公共子串

本篇內(nèi)容主要講解“怎么用Java輸出最長公共子串”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“怎么用Java輸出最長公共子串”吧!

創(chuàng)新互聯(lián)成立于2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都做網(wǎng)站、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元寶山做網(wǎng)站,已為上家服務(wù),為寶山各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:13518219792

1.簡述：

描述

給定兩個(gè)字符串str1和str2,輸出兩個(gè)字符串的最長公共子串

題目保證str1和str2的最長公共子串存在且唯一。 

數(shù)據(jù)范圍： 要求： 空間復(fù)雜度 ，時(shí)間復(fù)雜度 

示例1

輸入：

"1AB2345CD","12345EF"

返回值：

"2345"

2.代碼實(shí)現(xiàn)：

import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        //dp[i][j]表示到str1第i個(gè)個(gè)到str2第j個(gè)為止的公共子串長度
        int[][] dp = new int[str1.length() + 1][str2.length() + 1]; 
        int max = 0;
        int pos = 0;
        for(int i = 1; i <= str1.length(); i++){
            for(int j = 1; j <= str2.length(); j++){
                //如果該兩位相同
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) 
                    //則增加長度
                    dp[i][j] = dp[i - 1][j - 1] + 1; 
                else 
                    //該位置為0
                    dp[i][j] = 0; 
                //更新最大長度
                if(dp[i][j] > max){ 
                    max = dp[i][j];
                    pos = i - 1;
                }
            }
        }
        return str1.substring(pos - max + 1, pos + 1);
    }
}

到此，相信大家對(duì)“怎么用Java輸出最長公共子串”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

本文標(biāo)題：怎么用Java輸出最長公共子串
文章地址：http://m.jiaotiyi.com/article/psggco.html