2
\$\begingroup\$

Is this a practical algorithm for pattern matching in a text? Assume text can be very large, is there anything I can do to speed up the performance?

 public static int match(String pattern, String text) {
    int i = 0;
    int M = pattern.length();
    int N = text.length();
    int ret = -1;
    while (i < N) {
        StdOut.printf("i = %d\n", i);
        int j = 0;
        ret = i;
        while (j < M) {            
            if (pattern.charAt(j) == text.charAt(i)) {
                ++i;
                ++j;
                continue;
            } else {
                ++i;
                break;
            }            
        }
        if (j == M) return ret;
    }
    return -1;
}
\$\endgroup\$
1
  • \$\begingroup\$ Why not using String.matches(/*Regex*/) ? \$\endgroup\$
    – Ali Helmy
    Jul 14, 2015 at 7:22

1 Answer 1

3
\$\begingroup\$

Is this a practical algorithm for pattern matching in a text?

Are you trying to reinvent the wheel? String has .indexOf for exactly this purpose. These statements will print the same things, for example:

// both prints 2
System.out.println(match("hello", "x hello, there"));
System.out.println("x hello, there".indexOf("hello"));

// both prints -1
System.out.println(match("hello", "x, there"));
System.out.println("x, there".indexOf("hello"));

Assume text can be very large, is there anything I can do to speed up the performance?

In this example, using String.indexOf is probably the fastest you can get. If you have a more complex pattern, like a regular expression, then using Pattern will be more efficient than hand-coded solutions.


If you're reinventing the wheel intentionally, then here are some tips to improve your implementation:

  • Rename the method to indexOf(text, pattern), as "match" doesn't imply that it actually returns the starting index of the matched pattern. indexOf will also look familiar to other developers

  • The continue statement is unnecessary when it's the last statement in a loop

  • The int ret = -1 initialization before the loop is pointless: the value is reassigned in every iteration

  • It's better to declare variables in the smallest possible scope. So ret should be declared inside the loop.

    • The same goes for i, it would be better to convert that outer while loop to a for loop: for (int i = 0; i < N; ) {
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.