Pattern Matching with Mismatch I have been using a slightly modified Hamming Distance algorithm for approximate String Matching for patterns and wondering if there is something better out there. The t being the length of the text and p being the length of the pattern the worst case is roughly O(t*p). Which from looking at other Fuzzy String matching seems to be in norm.   

    final int mismatches = 1;
    final String text = "bubbles";
    final String pattern = "bu";    

    for(int iter = 0; iter &lt; text.length() - pattern.length() + 1; iter++)
    {
        int missed = 0;
        int ator = 0;

        do
        {
            if(text.charAt(iter + ator) != pattern.charAt(ator))
            {
                missed++;
            }
        }while(++ator &lt; pattern.length() &amp;&amp; missed &lt;= mismatches);

        if(missed &lt;= mismatches)
        {
            System.out.println("Index: " + iter + " Pattern: " + text.substring(iter, iter + pattern.length()));
        }
    }


The output being indexes 0 bu, 2 bb, and 3 bl. The last two being mismatches with the tolerance of 1.
It looks fine. Some readability improvements:


I'd rename some variables first:


mismatches should be tolerance, mismatchTolerance or allowedMismatches. For me mismatches sounds like a counter but it never changes which is confusing somehow.
iter and ator do not make the code easier to read. textIndex (maybe searchIndex) and patternIndex would be better since they are more meaningful and explains the purpose.

Then extract out some named variables like


final int textIndexMax = text.length() - pattern.length() + 1;
final char textChar = text.charAt(textIndex + patternIndex);
final char patternChar = pattern.charAt(patternIndex);
final String match = text.substring(textIndex, textIndex + pattern.length());


Reference: Chapter 6. Composing Methods, Introduce Explaining Variable in Refactoring: Improving the Design of Existing Code by Martin Fowler


  Put the result of the expression, or parts of the expression, 
  in a temporary variable with a name that explains the purpose.

The condition of the do-while loop could be rewritten as a usual (and a not so complex, therefore an easier to understand and less error-prone) for (i = 0; i &lt; x; i++) loop and a break statement.


Here is my version:

final int mismatchTolerance = 1;
final String text = "bubbles";
final String pattern = "bu";

final int textIndexMax = text.length() - pattern.length() + 1;
for (int textIndex = 0; textIndex &lt; textIndexMax; textIndex++) {
    int missed = 0;

    for (int patternIndex = 0; patternIndex &lt; pattern.length(); patternIndex++) {
        final char textChar = text.charAt(textIndex + patternIndex);
        final char patternChar = pattern.charAt(patternIndex);
        if (textChar != patternChar) {
            missed++;
        }
        if (missed &gt; mismatchTolerance) {
            break;
        }
    }

    if (missed &lt;= mismatchTolerance) {
        final String match = text.substring(textIndex, textIndex + pattern.length());
        System.out.println("Index: " + textIndex + " Match: " + match);
    }
}