合併在Java中兩個字符串重疊，並與允許的差異

Question

我要「合併」兩個字符串，看到代碼：

public class Test { 

    public static void main(String[] args) { 
     printAllPossibleMergedString("abcdefdefd", "defdefdefghi"); 
    } 

    public static void printAllPossibleMergedString(String a, String b) { 
     System.out.println(a + b); 
     int maxOverlap = Math.min(a.length(), b.length()); 
     for (int i = 1; i <= maxOverlap; i++) { 
      if (b.startsWith(a.substring(a.length() - i, a.length()))) { 
       System.out.println(a + b.substring(i)); 
      } 
     } 
    } 
} 

輸出：

abcdefdefddefdefdefghi 
abcdefdefdefdefdefghi 
abcdefdefdefdefghi 
abcdefdefdefghi 

現在我想這個方法成爲'容錯'（希望你能理解），這樣的事情：

void printAllPossibleMergedString(String a, String b, int tolerance); 

所以，如果我做的：

// 'x' means a wrong character 
printAllPossibleMergedString("abcdefdefx", "defdefdefghi", 1); 

將輸出：

abcdefdefxdefdefdefghi 
abcdefdefdefdefghi 
abcdefdefdefghi 

同時：

printAllPossibleMergedString("abcdefdefxx", "defdefdefghi", 1); 

只能輸出：

abcdefdefxxdefdefdefghi 

，當然還有：

printAllPossibleMergedString("abcdefdefxx", "defdefdefghi", 2); 

將輸出：

abcdefdefxdefdefdefghi 
abcdefdefdefdefghi 
abcdefdefdefghi 

因此，如何有效地實現這一點？

謝謝。

Answer 1

並不清楚什麼是「容錯」是的，但處理這將是如下的一個正式的方式：

所有出現的可能性就比較兩個字符串，可以實現一種叫做編輯距離（或者至少是它的一個變體）。改變不同操作的權重（例如，在開始/結束成本= 1時插入，在開始/結束成本= 2時取代），以及其他所有成本都有無限的成本。然後以非無限成本產生所有可能性。

https://en.wikipedia.org/wiki/Edit_distance