public static int getEditDistance(
      String source,
      String target,
      boolean caseSensitive,
      int changeCost,
      int openGapCost,
      int continueGapCost) {

    if (!caseSensitive) {
      source = Ascii.toLowerCase(source);
      target = Ascii.toLowerCase(target);
    }

    int sourceLength = source.length();
    int targetLength = target.length();

    if (sourceLength == 0) {
      return scriptCost(openGapCost, continueGapCost, targetLength);
    }

    if (targetLength == 0) {
      return scriptCost(openGapCost, continueGapCost, sourceLength);
    }

    // mMatrix[i][j] = Cost of aligning source.substring(0,i) with
    // target.substring(0,j), using an edit script ending with
    // matched characters.
    int[][] mMatrix = new int[sourceLength + 1][targetLength + 1];

    // Cost of an alignment that ends with a bunch of deletions.
    // dMatrix[i][j] = best found cost of changing the first i chars
    // of source into the first j chars of target, ending with one
    // or more deletes of source characters.
    int[][] dMatrix = new int[sourceLength + 1][targetLength + 1];

    // Cost of an alignment that ends with one or more insertions.
    int[][] iMatrix = new int[sourceLength + 1][targetLength + 1];

    mMatrix[0][0] = dMatrix[0][0] = iMatrix[0][0] = 0;

    // Any edit script that changes i chars of source into zero
    // chars of target will only involve deletions.  So only the
    // d&m Matrix entries are relevant, because dMatrix[i][0] gives
    // the cost of changing an i-length string into a 0-length string,
    // using an edit script ending in deletions.
    for (int i = 1; i <= sourceLength; i++) {
      mMatrix[i][0] = dMatrix[i][0] = scriptCost(openGapCost, continueGapCost, i);

      // Make the iMatrix entries impossibly expensive, so they'll be
      // ignored as inputs to min().  Use a big cost but not
      // max int because that will overflow if anything's added to it.
      iMatrix[i][0] = Integer.MAX_VALUE / 2;
    }

    for (int j = 1; j <= targetLength; j++) {

      // Only the i&m Matrix entries are relevant here, because they represent
      // the cost of changing a 0-length string into a j-length string, using
      // an edit script ending in insertions.
      mMatrix[0][j] = iMatrix[0][j] = scriptCost(openGapCost, continueGapCost, j);

      // Make the dMatrix entries impossibly expensive, so they'll be
      // ignored as inputs to min().  Use a big cost but not
      // max int because that will overflow if anything's added to it.
      dMatrix[0][j] = Integer.MAX_VALUE / 2;
    }

    for (int i = 1; i <= sourceLength; i++) {

      char sourceI = source.charAt(i - 1);
      for (int j = 1; j <= targetLength; j++) {
        char targetJ = target.charAt(j - 1);

        int cost = (sourceI == targetJ) ? 0 : changeCost;

        // Cost of changing i chars of source into j chars of target,
        // using an edit script ending in matched characters.
        mMatrix[i][j] =
            cost + Ints.min(mMatrix[i - 1][j - 1], iMatrix[i - 1][j - 1], dMatrix[i - 1][j - 1]);

        // Cost of an edit script ending in a deletion.
        dMatrix[i][j] =
            Math.min(
                mMatrix[i - 1][j] + openGapCost + continueGapCost,
                dMatrix[i - 1][j] + continueGapCost);

        // Cost of an edit script ending in an insertion.
        iMatrix[i][j] =
            Math.min(
                mMatrix[i][j - 1] + openGapCost + continueGapCost,
                iMatrix[i][j - 1] + continueGapCost);
      }
    }

    // Return the minimum cost.
    int costOfEditScriptEndingWithMatch = mMatrix[sourceLength][targetLength];
    int costOfEditScriptEndingWithDelete = dMatrix[sourceLength][targetLength];
    int costOfEditScriptEndingWithInsert = iMatrix[sourceLength][targetLength];
    return Ints.min(
        costOfEditScriptEndingWithMatch,
        costOfEditScriptEndingWithDelete,
        costOfEditScriptEndingWithInsert);
  }
@Test
  public void needlemanWunschEditDistance_matchesLevenschtein_withHugeGapCost() {
    String identifier = "fooBar";
    String otherIdentifier = "bazQux";

    double levenschtein = LevenshteinEditDistance.getEditDistance(identifier, otherIdentifier);
    double needlemanWunsch =
        NeedlemanWunschEditDistance.getEditDistance(
            identifier, otherIdentifier, /* caseSensitive= */ false, 1, 1000, 1000);

    assertThat(needlemanWunsch).isEqualTo(levenschtein);
  }