Consider the following string match function that extracts a substring from the length of the pattern P in the string text T. It works for the pattern "why" and the text "whysaywhycatwhy" but fails with the text " why say why cat why" for the same pattern. Why does the "dum" string match function fail?

Question

void dum(String P, String T) {

int N = T.length()-1;
int M = P.length();

int start = 0;
while(start < N){

String extract = T.substring(start, start+M);
if(extract.equals(P))
System.out.printf("Match at %d%n",start);
start = start + M;
}
}

a. The dum() function fails because it does not consider the overlap of the pattern within the extracted substring
b. The dum() function fails because it does not preprocess the string text
c. The dum() string match function fails because it does not hash efficiently
d. The dum() string match function fails because of the whitespace characters

Answer 1

a. The dum() function fails because it does not consider the overlap of the pattern within the extracted substring
This algorithm is like a naïve string search, except it is skipping ahead the length of the pattern P. This overlooks any possible matches from the overlapping text by so many characters 1 … to the length of the pattern P -1.