Test whether target string is substring of source string

Question

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

Answer 1

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.