計算兩個字符串最大公有子串

更新時間：2017年01月23日 14:07:54 作者：min.jiang

本文主要介紹了計算兩個字符串最大公有子串的解決方案。具有很好的參考價值，下面跟著小編一起來看下吧

背景

對算法一直應用的比較少，最近看到一些典型的算法想練練手，想看看到底有多么讓人討厭。其實發(fā)現(xiàn)算法都有一定的套路，一般并不是臨時憑空想出來的，大都建立在一些已經存在的經典算法知識以及數(shù)據(jù)結構上。換句話來說，如果某些玩法之前未接觸過，那么讓你在短時間內臨時想出來還是有一定難度的。這有點類似項目經驗，如果曾經做過一個CRM系統(tǒng)，下次再碰到它時你就輕松很多，如果你挑戰(zhàn)的是一個你從未遇到過的系統(tǒng)，你只能憑已有知識去強吃。

計算兩個字符串最大公共子串

這個也是經常遇到到，給出兩個任意長度的字符串，輸出最大公有字符串，比如輸入abcdef，cdef，則輸出cdef。

解決方案

采用雙層循環(huán)，指針移動來記錄所有子串，最后取最大長度子串。利用臨時隊列來存儲循環(huán)過程中匹配成功的字符元素，從兩個字符串首個元素開始匹配。

如果a.charAt(i)=b.charAt(j)，標記開始匹配，同時移動兩者指針，并將相同字符串壓入臨時隊列中
如果a.charAt(i)!=b.charAt(j)，只移動b的指針。如果處于匹配中，則將臨時隊列存儲到結果集中，并清空臨時隊列。
如果a,b任意一個到了最后一個元素，將臨時隊列中的值存儲到結果集中，并清空臨時隊列

示意圖

從元素0開始比較

字符串A指針不動，B依次向后找至少找到相同的，將相同字符壓入臨時隊列中。

出現(xiàn)第一個匹配元素

當出現(xiàn)匹配元素后，兩個字符串均向后移動一個元素再做比較。

匹配出現(xiàn)中斷

如果前面已經開始匹配成功，向后出現(xiàn)字符不相同時，終止。

重置索引，循環(huán)匹配

字符串B指針向后移動，字符串A的指針重置，遞歸上面的步驟。

示例代碼

下面的示例將所有子串均記錄下來，如果只想輸出最大子串需要改下邏輯，定義一個最大子串，然后與循環(huán)計算的子串相比較，取兩者長度最大值即可。

String b="abcdeqwe";
String a="cdeabrwqedeqwe";
int lengthA=a.length();
int lengthB=b.length();
//標識是否開始匹配
boolean match=false;
//循環(huán)中用于存儲相同字符的臨時隊列
Queue tmpResult=new ArrayQueue();
//存儲所有子串
List<Queue> result=new ArrayList<>();
for(int i=0;i<lengthA;i++){
 int indexA=i;
 for(int j=0;j<lengthB;j++){
  if(a.charAt(indexA)==b.charAt(j)){
   if(!match) {
    match = true;
   }
   tmpResult.add(a.charAt(indexA));
   if(indexA<lengthA-1) {
    indexA++;
   }
  }
  else {
   if(match) {
    result.add(tmpResult);
    //重置條件
    tmpResult=new ArrayQueue();
    indexA=i;
   }
  }
  if(j==lengthB-1||i==lengthA-1){
   if(!tmpResult.isEmpty()){
    result.add(tmpResult);
    //重置條件
    tmpResult=new ArrayQueue();
   }
  }
 }
}
//取最大的子串
Queue stringResult= Collections.max(result, new Ordering<Queue>() {
 @Override
 public int compare(Queue left, Queue right) {
  return Integer.compare(left.size(),right.size());
 }
});

優(yōu)點

指針移動在循環(huán)過程中不會產生多余的臨時字符串，如果是substring方案就需要考慮效率了。

以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持腳本之家！

您可能感興趣的文章:

@Transactional遇到try catch失效的問題
這篇文章主要介紹了@Transactional遇到try catch失效的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-01-01
解決logback-classic 使用testCompile的打包問題
這篇文章主要介紹了解決logback-classic 使用testCompile的打包問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2021-07-07
Java 在PPT中創(chuàng)建散點圖的實現(xiàn)示例
本文將以Java代碼示例展示如何在PPT幻燈片中創(chuàng)建散點圖表。文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-11-11
Java消息隊列RabbitMQ之消息模式詳解
這篇文章主要介紹了Java消息隊列RabbitMQ之消息模式詳解,RabbitMQ提供了一種qos(服務質量保證)功能,即在非自動確認消息的前提下,如果一定數(shù)目的消息(通過基于Consumer或者Channel設置Qos的值)未被確認前,不進行消費新的消息,需要的朋友可以參考下
2023-07-07
Java進階教程之異常處理
這篇文章主要介紹了Java進階教程之異常處理,本文講解了JAVA的異常處理機制、異常的類型、拋出異常、自定義異常等內容,需要的朋友可以參考下
2014-09-09
Mybatis-Plus自動填充的實現(xiàn)示例
這篇文章主要介紹了Mybatis-Plus自動填充的實現(xiàn)示例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2019-08-08
Java switch 語句如何使用 String 參數(shù)
這篇文章主要介紹了Java switch 語句如何使用 String 參數(shù),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，,需要的朋友可以參考下
2019-06-06
基于Restful接口調用方法總結(超詳細)
下面小編就為大家?guī)硪黄赗estful接口調用方法總結(超詳細)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2017-08-08
Java多線程中Callable和Future的解讀
這篇文章主要介紹了Java多線程中Callable和Future的解讀,Callable接口類似于Runnable,從名字就可以看出來了,但是Runnable不會返回結果,并且無法拋出返回結果的異常,而Callable功能更強大一些,被線程執(zhí)行后,可以返回值,這個返回值可以被Future拿到,需要的朋友可以參考下
2023-09-09
Java RPC框架熔斷降級機制原理解析
這篇文章主要介紹了Java RPC框架熔斷降級機制原理解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-02-02