一.華為OJ題目：

查找兩個字符串a,b中的最長公共子串。

詳細描述：

查找兩個字符串a,b中的最長公共子串。

接口設計及說明：

?

?/*****************************************************************************

?Description??: 查找兩個字符串a,b中的最長公共子串

?Input Param??: String stringA, 輸入字符串A

????String stringB, 輸入字符串B??????????????

?Output Param?:

?Return Value?: 成功返回最大公共子串，失敗返回null（如：數據錯誤）

?*****************************************************************************/

?public static StringiQueryMaxCommString(String stringA, String stringB)

?{

????/* 在這里實現功能，將結果填入輸入數組中*/

????return null;

?}

?

二.詳細解答過程：

?

1.首先，計算2個字符串的長度。定義整形變量 counts,pos_end;lengthA=strA.length()

2.然后，進入兩層循環：

（1）第一層循環，用i作遞增變量（0～lengthA），初始化posA,countsA;

（2）第二層循環，用j作遞增變量(0～lengthB)

進入第二層循環，尋找B字符串中與str[posA]相等的字符，如果找到，那么posA++,countsA++,

接著在第二層循環內繼續尋找查看字符串B中是否下一個字符仍然與A字符串中的對應字符相同，

如果又找到，那么繼續讓posA++,countsA++，如果中間突然出現一個不相等然后后面一個又相等了怎么辦？會不會出現誤差？

?

事實證明不會出現這種情況，原因是posA++的同時j也在遞增，所以他們是對應相等的時候，才會進入相應的條件語句

并且posA++,countsA++

（3）第二層循環結束之后，i++，那么再重新尋找公共字符串，如果找到更大的字符串，那么countsA>counts條件語句將成立

于是進入條件語句，counts更新，posA的位置也更新。（因為posA位置遞增了，所以處理之后要-1）

?

3.該步驟將最大公共字符子串從末尾添加進string類str內；

?

4.函數返回str;

?

代碼：

//求最大公共字符串并輸出

?

#include <iostream> #include <string> using namespace std; static string iQueryMaxCommString(string&stringA, string stringB){int cnts=0,pos_end,lenA,lenB;lenA=stringA.size();lenB=stringB.size();for(int i=0;i<lenA;i++){int posA=i;int countA=0;for(int j=0;j<lenB;j++){if(stringA[posA]==stringB[j]){countA++;++posA;if(cnts<countA){cnts=countA;pos_end=posA-1;}}}}string str;int begin=pos_end-cnts+1;for(int j=begin;j<=pos_end;j++){str.push_back(stringA[j]);}return str;}intmain(){string str1,str2;getline(cin,str1);getline(cin,str2);cout<<iQueryMaxCommString(str1,str2)<<endl;return 0;}

總結

以上是生活随笔為你收集整理的最大公共字符串输出的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。