算法串一個錯配

Question

可能有人建議爲兩個字符串atmost一個錯配之間的字符串比較的更好方法。

實施例：

• 答：abcdefghabX
• B：ABC
• 輸出：1 9

上述輸出是在 「A」

ABC的子串匹配的位置

我試着用兩個for循環的基本方法，但是，它似乎是採取N * N的時間。這是大量投入的重要因素，需要花費大量時間。

我的算法是這樣，但它不是數據

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; 
    if((length+1)%2 != 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; 
     } 
    } 
    else { 
     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; 
} 

Answer 1

我想你以後是Boyer-Moore算法。

具體地，近似的版本here。

Answer 2

巨量一個最好的一個，你想在AGREP實現，所以看看它使用algorithms什麼。