Pattern-Matching Algorithm

This is slide from class at my University, it about Pattern-Matching Algotithm..

And I try to code it in Java below;

            // Get values for both the text T1,T2 ... Tn and the pattern P1 P2 ... Pm
            String[] T = {"Java", "is", "too", "delicious", ", Dr.Java", "is", "confrim!"};
            String[] P = { "is", "too"};
            // Get values for n and m, the size of the text and the pattern, respectively
            int n = T.length;
            int m = P.length;
            // Set k1 the starting location for the attempted match, to 1
            int k = 0;

            // While(k<=(n-m+1))do
            while (k <= (n - m + 1) - 1) {
                    // Set the value of i to 1
                    int i = 0;
                    // Set the value of Mismatch NO
                    boolean Mismatch = true; // Not found (true - NO)

                    // While both (i<=m) and (Mismatch = NO) do
                    while ((i <= m - 1) && (Mismatch)) { // if Not found (true - NO)
                            // if Pi != Tk+(i-1) then
                            if (P[i].equals(T[k])) { // if Found(true)
                                    // Set Mismatch to YES
                                    Mismatch = false; // Found (false - YES)
                                    // Else
                            } else {
                                    // Increment i by 1 (to move to the next character)
                                    i = i + 1;
                            }
                            // End of the loop
                    }
                    // If mismatch = NO then
                    if (!Mismatch) { // if Found (false - YES)
                            // Print the message 'There is a match at position'
                            System.out.print("There is a match at position ");
                            // Print the value of k
                            Sy开发者_运维技巧stem.out.println(k);
                    }
                    // Increment k by 1
                    k = k + 1;
                    // Enf of the loop
            }
            // Stop, we are finished

But I have a question! why in pseudo code version, check if P not equal T ? I think it would rather to be check if P equal T (How it difference with my version? , sorry for my terrible English)

---

You made a translation mistake at the inner while

while ((i <= m - 1) && (Mismatch)) { // if Not found (true - NO) 

In pseudo code it was said to be Mismatch=no which would be !Mismatch

This resulted in the case that you had to invert the inner if statement.

---

The pseudo code essentially checks from every point a match could possibly begin in T (1 <= k <= n-m+1), loops and checks that the substring of T from k to k+m-1 matches P. So as soon as it finds one mismatched letter, it stops checking the substring, and increments k (to check from the next position). That conditional (T[k+i-1] != P[i]) is the breaking condition for the inner loop, and the boolean to flag that from the current starting position k, there is no match.

Note that this algorithm has complexity O(nm) which is slow. There are smarter algorithms that can search in linear time, like KMP.