patternjavaMinor
Test whether target string is substring of source string
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
NAMING
I suggest you rename
CODE
After simplifying your code, you may get something like:
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.
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.