HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Test whether target string is substring of source string

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
targetsourcesubstringtestwhetherstring

Problem

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

Solution

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.

Code Snippets

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

Context

StackExchange Code Review Q#108287, answer score: 4

Revisions (0)

No revisions yet.