Pattern search in a text

Question

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;
}

Answer 1

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; ) {