[UPDATE] [Code] [Fastest String Search Algorithm]
Amit Choudhary
amitchoudhary0523@gmail.com
Sun Jun 13 07:17:08 GMT 2021
Last time I had sent old code. This is the latest code.
Again, I am not sending this code so that this code gets included in glibc.
I am sending this code because glibc mailing list is in public domain and
getting indexed by search engines. So, people outside of glibc can see this
algo if they search for fastest string search algorithm on web.
Code:
===================================================================================
// Choudhary string search algorithm
static char * choudhary_string_search_algorithm(char *text, char *pattern)
{
#define false 0
#define true 1
#define ALPHABET_SIZE 256
int i = 0;
int end_index = 0;
int not_found = false;
char pattern_char[ALPHABET_SIZE] = {0};
int text_len = strlen(text);
int pattern_len = strlen(pattern);
int pi_44 = pattern_len - 1;
int pi_34 = (3 * pattern_len) / 4;
int pi_24 = pattern_len / 2;
int pi_14 = pattern_len / 4;
int last_failed_index = -1;
// preprocessing
for (i = 0; i < pattern_len; i++) {
pattern_char[(int)(pattern[i])] = 1;
}
// now search
for (i = 0; i < text_len; i++) {
if ((text_len - i) < pattern_len) {
return NULL;
//return -1;
}
if (pattern[pi_44] != text[i + pi_44]) {
last_failed_index = pi_44;
// this character doesn't appear in pattern, so skip
if (pattern_char[(int)(text[i + pi_44])] == 0) {
i = i + pi_44;
}
continue;
} else if (pattern[pi_34] != text[i + pi_34]) {
last_failed_index = pi_34;
// this character doesn't appear in pattern, so skip
if (pattern_char[(int)(text[i + pi_34])] == 0) {
i = i + pi_34;
}
continue;
} else if (pattern[pi_24] != text[i + pi_24]) {
last_failed_index = pi_24;
// this character doesn't appear in pattern, so skip
if (pattern_char[(int)(text[i + pi_24])] == 0) {
i = i + pi_24;
}
continue;
} else if (pattern[pi_14] != text[i + pi_14]) {
last_failed_index = pi_14;
// this character doesn't appear in pattern, so skip
if (pattern_char[(int)(text[i + pi_14])] == 0) {
i = i + pi_14;
}
continue;
} // end of if-else.. block
// compare with character at last failed index.
if (last_failed_index >= 0) {
if (pattern[last_failed_index] != text[i + last_failed_index]) {
continue;
}
}
if (pattern[0] == text[i]) {
//full_pattern_search = full_pattern_search + 1;
end_index = i + pi_44;
not_found = false;
int index = 0;
for (index = i; index <= end_index; index++) {
if (text[index] != pattern[index - i]) {
last_failed_index = index - i;
not_found = true;
break;
}
} // end of inner for loop
if (not_found == false) { // match is found
return (text + i);
//return i;
} else if (pattern_char[(int)(text[index])] == 0) {
i = index;
}
} // end of if pattern[0]
} // end of outer for loop
return NULL;
//return -1;
} // end of choudhary_string_search_algorithm
===================================================================================
Amit
More information about the Libc-alpha
mailing list