與一個錯配的子串比較

下面是一個字符串A和串B與atmost一個錯配即進行比較的代碼， ABC是相同ABX或AXC或XBC但是，不相同AXZ與一個錯配的子串比較

我做檢查幾個案例，但網站說它提供了錯誤的答案。有人能幫忙弄清楚這段代碼失敗了嗎？另外，如果有人能爲相同的問題提供更好的算法，我會很高興。

int compare(string a, int pos, string b) { 
int count = 0; 
int length = b.length()-1; 
int mid = b.length() /2; 

if(pos+length >= a.length()) 
    return 0; 

for(int i=0,j=pos;i<=mid;i++,j++) {  
    if(i == mid) { 
     if(a[j] != b[i]) 
      count ++; 
    } 
    else { 
     if(a[j] != b[i]) 
      count ++; 
     if(a[pos+length - i] != b[length -i]) 
      count ++; 
    } 
    if(count >= 2) return 0; 
} 
return 1; 
}

來源

2012-02-23 Rama

聞起來像功課。 – Till 2012-02-23 22:08:58

不是功課，而是來自一個編程網站 – Rama 2012-02-23 23:30:43

無論如何，討論這裏的作業有什麼問題？ – jogojapan 2012-02-23 23:34:29

的一個問題是，如果b.length()是偶數，那麼你比較a[pos + b.length()/2]到b[b.length()/2]兩次：一次是當i == mid - 1，一旦i == mid時。因此，類似compare("abcd", 0, "abbd")返回0，因爲它將'c' -vs.- 'b'作爲兩個單獨的不匹配來計算差異。

我建議你簡單地去除與mid相關的所有邏輯。除了大量複雜的代碼之外，它沒有任何其他用途。如果從0直接迭代到b.length() - 1，那麼結果會好很多。

來源

2012-02-23 22:20:40 ruakh

不僅如此，目前的訪問模式，一次處理兩個緩衝區的兩端，具有可怕的緩存行爲。 – 2012-02-23 22:31:20

@ BenVoigt：是的，但我真的認爲這是最少的問題。如果雙端方法有充分的理由，那麼緩存行爲可能會或可能不足以推翻這一原因;但由於似乎沒有任何理由，我認爲這是沒有意義的。 – ruakh 2012-02-23 22:35:54

謝謝Ruakh ...我解決了這個問題我不得不忍受中期邏輯，希望它能讓我的代碼更快地運行更大的輸入但是，似乎我需要尋找一種新算法，而不是優化這種天真使用（N * N）時間的方法您能否提出一個更好的方法來執行此操作，它使用較少的時間。 TY – Rama 2012-02-24 00:05:12

與一個錯配的子串比較

回答

相關問題