3
\$\begingroup\$

In an attempt to think up a more efficient String Matching algorithm than the naïve \$O(n \cdot k)\$ one I came up with a slightly modified approach.

In my algorithm (code in Java), I tried a little modification of the \$O(n \cdot k)\$ approach where every time a character match starting from i fails after k positions, we start from i+1th place.

In this algo however, if matching fails at k position, I resume comparison from k-1 because we know up to k-1 the characters are common.

Below is the implementation of this approach.

I will really appreciate anyone taking a look into the code and

  1. Confirm if things work the way I explained. My tests seem to be working fine.
  2. What is the complexity of this approach? Is it worst case \$O(n \cdot k)\$ still?
  3. An example of a worst case input.

Code:

public class ModifiedSearch {
    private String text;

    public ModifiedSearch(String text) {
        this.text = text;
    }

    public int findPattern(String pattern) {
        int textLength = text.length();
        int patLength = pattern.length();
        int common = 0;
        boolean broken = false;

        for (int tIndex = 0; tIndex <= textLength - patLength; broken = false, tIndex++) {
            int k = 0;

            while (tIndex + common + k < textLength && common + k < patLength) {


                if (text.charAt(tIndex + common + k) != pattern.charAt(common + k)) {
                    broken = true;
                    common = (common + k - 1 < 0) ? 0 : common + k - 1 ;
                    break;
                }

                k++;
            }

            if (!broken && common + k == patLength) {
                return tIndex;
            }
        }

        return -1;
    }
}

I have tried this with a combination of inputs large and small, but this does not seem to worse out to \$O(n \cdot k)\$. Any help greatly appreciated.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Confirm if things work the way I explained. My tests seem to be working fine.

I'm afraid not. For example, for text hehehello and pattern hehello, the output is 0 instead of 2. You see, the algorithm prematurely exits after heheh, when it should continue searching from position 2.

With your modified version this test case passes, but fails for text heheehello and pattern hehello, incorrectly returning 3 instead of -1. (In the future, please do not modify the code in the question after you received answers. Changing the code typically invalidates answers, as it did in this example too.)

See the Knuth-Morris-Pratt algorithm for something that actually works.

What is the complexity of this approach? Is it worst case O(n⋅k) still?

The complexity of your algorithm is \$O(n + k)\$, same as that of KMP. Unfortunately it doesn't really matter, because it doesn't work correctly.

Usage

The usage of your class is a bit awkward:

int index = new ModifiedSearch(text).findPattern(pattern);

I recommend to rewrite to make it work this way:

int index = ModifiedSearch.findPattern(text, pattern);

That is, turn the class into a static utility method. It will be lighter that you don't have to create an instance of the class.

Looking at the function name "findPattern" alone, it's not obvious what it returns. Since the function returns an index, like String.indexOf, I recommend to rename it to indexOf. Or, rename to contains and make it return a boolean.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the answer. In reply to your comments: 1. Making it static totally makes sense. But I was only playing around with searches and did not bother about its application per say. 2. I screwed up in the logic for testing whether the search has ended. I have modified the code. But otherwise the use of common actually helped in reducing the complexity. Sure it's possible there are places it still might break, but that should boil down to writing a better implementation of the above logic. I am aware of KMP, but don't you agree this looks simpler? Many thanks for the review! \$\endgroup\$
    – iammrigank
    Apr 16, 2016 at 1:01
  • \$\begingroup\$ I found a counter-example for your updated code. Note that you should not modify the code in the question if that invalidates my answer. (Normally we roll back such edits.) You are welcome to post a new question with the revised code. However, I doubt you can beat KMP. Sure your algorithm is simpler, unfortunately, correctness comes first, not simplicity. \$\endgroup\$
    – janos
    Apr 16, 2016 at 7:04
  • \$\begingroup\$ Yes Janos. After I updated the code, i realized the main issue with the approach. Thanks for the advices. :) \$\endgroup\$
    – iammrigank
    Apr 17, 2016 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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