1つの不一致のある文字列のアルゴリズム

Question

1つの不一致を持つ2つの文字列の文字列比較で、より良いアプローチを提案できますか？

例：

• A：abcdefghabX
• B：ABC
• 出力：1~9

上記出力は ""

におけるABCのサブストリングの一致の位置であります

2つの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を見てさ。