找到最長公共子序列的分段錯誤

-10

問題說明：給定兩個長度相等的字符串a和b，可以構造的最長的字符串（S）是什麼，以便S是a和b的子元素。一個字符串x被認爲是一個字符串y的子元素，如果x可以通過從y中刪除0個或更多個字符（ie..finding最長公共子序列）來形成。找到最長公共子序列的分段錯誤

輸入：兩個字符串a和b用換行符分開。

限制條件：所有字符都是大寫字母，位於ASCII值65-90之間。弦A和B的最大長度是5000。

輸出格式：串S.

我的問題的長度是，我抵達段故障爲一體的測試用例。 SOMEOE PLZ告訴我爲什麼？

這裏在C我的代碼：

#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#include <stdlib.h> 

int max(int a, int b) 
{ 

    return (a>b)?a:b; 

} 

int lcs(char *X, char *Y, int x, int y) 
{ 

    int L[x+1][y+1]; 
    int i,j; 

    for(i=0 ; i<=x ; i++) 
    { 
     for(j=0 ; j<=y ; j++) 
     { 
      if(i==0 || j==0) 
       L[i][j] = 0; 

      else if(X[i-1] == Y[j-1]) 
      { 
       L[i][j] = 1 + L[i-1][j-1]; 
      } 
      else 
       L[i][j] = max(L[i-1][j],L[i][j-1]); 

     } 
    } 
    return L[x][y]; 

} 

int main() { 

    char a[5000],b[5000]; 
    scanf("%s",a); 
    scanf("%s",b); 

    int lenA, lenB; 

    lenA = strlen(a); 
    lenB = strlen(b); 

    printf("%d",lcs(a,b,lenA,lenB)); 

    return 0; 
}

來源

2014-12-26 kasif

當您使用調試器逐行執行程序時，您發現了什麼？ –

也不要喊叫，並完成英語句子和單詞。 –

'int L [x + 1] [y + 1];'這不是標準的C++。鑑於此，您需要告訴我們測試案例失敗的原因。 – PaulMcKenzie

我看到三個可能的原因：

你輸入過大。 scanf（）不會檢測到該字符串，但您可以指定要讀取的最大字符串長度：

scanf（「％4999s」，a）;
您嘗試讀取5000個字符的字符串加上終止0到5000個字符的數組。這意味着終止0將覆蓋一些任意內存，或者可能被下一次調用scanf覆蓋。因此，只需定義數組大1個字節。可以肯定的是，將它們定義爲2個字節大一點，（a [5002]，b [5002]），允許掃描5001個字符，檢查掃描的長度並投訴它是否爲5001.聲音偏執，但明顯出現問題，你的代碼應該準備好檢測錯誤。
L [x + 1] [y + 1]可能會導致相當大的數組。假設你掃描兩個5000字節的字符串，終止0會丟失，因爲你的數組太短，strlen的結果是5012和10012.在這種情況下，你想在堆棧上分配200 MB。這相當多，可能會失敗。即使你很幸運，並且你的字符串被正確終止，你仍然可能需要100 MB的堆棧。這不是如何堆棧的工作。

順便說一句 - 你實現了萊文施泰因算法的變化 - 萊文施泰因衡量兩個字符串之間的差異，而你衡量公共部分，這只是另一種觀點同樣的問題。你知道它可以在沒有5001x5001矩陣的情況下實現嗎？在堆棧中有足夠的3x5001整數。爲了計算結果矩陣的下一行，您只需要前兩行，這意味着足夠在矩陣堆棧中保留3行矩陣。這3排將適合。

來源

2014-12-26 14:16:35

找到最長公共子序列的分段錯誤

回答

相關問題