背景

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

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

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

解決方案

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

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

示意圖

從元素0開始比較

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

出現第一個匹配元素

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

匹配出現中斷

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

重置索引，循環匹配

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

示例代碼

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

String b="abcdeqwe";String a="cdeabrwqedeqwe";int lengthA=a.length();int lengthB=b.length();//標識是否開始匹配boolean match=false;//循環中用于存儲相同字符的臨時隊列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()); }});

優點

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

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