WAP返回兩個字符串之間最長公共子串的長度

Question

給出兩個字符串，我們必須找到最長公共子串的長度。我不知道我的代碼有什麼問題。

外循環取B的子串，內循環一次增加一個字符的子串。

對於輸入 「www.lintcode.com代碼」， 「www.ninechapter.com代碼」 輸出來了5但它應該是9

public class Solution { 
/** 
* @param A, B: Two string. 
* @return: the length of the longest common substring. 
*/ 
public int longestCommonSubstring(String A, String B) { 
    // write your code here 
    int k = 0, temp = 0; 
    if(B.length() == 0){ 
     return 0; 
    } 

    for(int i = 0; i < B.length()-1; i++){ 
     String bb = B.substring(i, i+1); 
     if(A.contains(bb)){ 

      for(int j = 1; j < A.length()-i; j++){ 
       String bbb = B.substring(i, i+j); 
       if(!A.contains(bbb)) 
        break; 
       temp = bbb.length(); 
      } 
     } 
     if(temp > k) 
      k = temp; 
    } 

    return k; 
} 

}

Answer 1

只需更換這樣的：

for(int j = 1; j < A.length()-i; j++) 

與此：

for(int j = 1; j < B.length()-i+1; j++) 

Answer 2

我相信你可以減少你的功能尺寸有點這個......不知道，如果你的方法更有效與否，但...

public int longestCommonSubstring(String A, String B) { 
    int longestSubstring = 0; 
    for (int x=0; x < A.length(); x++) { 
     for (int y=x; y < A.length() + 1; y++) { 
      String testString = A.substring(x,y); 
      if (B.contains(testString) && (testString.length() > longestSubstring)) { 
       longestSubstring = testString.length(); 
      } 
     } 
    } 
    return longestSubstring; 
}