5
\$\begingroup\$

The code is self-explanatory. It has \$O(n)\$ complexity, and it tells whether a given string is the substring of the source string. Are there any cases where this algorithm fails? Is there anything that can be improved?

    public static boolean isSubStringOf(char src[], char target[]) {
    int pointTarget=0;
    for (int pointSrc = 0;pointSrc < src.length; pointSrc++) {
        // If target's pointer is at target's length , Voila !
        if (pointTarget == target.length)
            return true;

        //If value at src's pointer equals value at target's pointer increment target's pointer and continue.
        if (src[pointSrc] == target[pointTarget]) {
            pointTarget++;
            continue;
        } 
        //However if they are not equal reset target's pointer back to target's beginning.
        else if (src[pointSrc] != target[pointTarget]) {
            pointTarget = 0;
        }
    }
    // To handle right corner case
    return pointTarget == target.length;
}
\$\endgroup\$
4
\$\begingroup\$

A BUG

Your method fails on string "baaaba" whenever searching for "aab". The problem here is that when you reset pointTarget to 0, you may ignore a prefix of the pattern.

NAMING

I suggest you rename src to text or string, and rename target to pattern.

CODE

After simplifying your code, you may get something like:

public static boolean isSubstringOf(char string[], char pattern[]) {
    int pointTarget = 0;

    for (int cursor = 0; cursor < string.length; cursor++) {
        if (pointTarget == pattern.length) {
            break;
        }

        if (string[cursor] == pattern[pointTarget]) {
            pointTarget++;
        } else {
            cursor -= pointTarget - 1;
            pointTarget = 0;
        }
    }

    return pointTarget == pattern.length;
}

The above runs in time \$\mathcal{O}(nm)\$, where \$n\$ is the length of the text to search and \$m\$ is the length of the pattern string. If you want to find the pattern in the text in linear time, you could use Knuth-Morris-Pratt algorithm.

\$\endgroup\$
  • \$\begingroup\$ How did you calculate the complexity as O(mn) ? \$\endgroup\$ – Kanwaljeet Singh Oct 21 '15 at 15:59
  • \$\begingroup\$ The algorithm in my answer is just a fancy way of doing String.contains. You start from the first character (cursor = 0) of the text and as long as you can "pump" characters from the pattern, you do just that. If, however, you notice that there can be no match, you increment the cursor and begin from (cursor = 1), and so on. Don't get me wrong, on most real-world strings/patterns this implementation is sufficient (and, in fact, can be faster than linear time KMP); \$\mathcal{O}(mn)\$ is the worst case which won't happen too often. \$\endgroup\$ – coderodde Oct 21 '15 at 16:06

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.