Messages in this thread | | | From | Amit Choudhary <> | Date | Sun, 13 Jun 2021 14:00:18 +0530 | Subject | [Code] Fastest String Search Algorithm. |
| |
Hi All,
I have invented a new string search algorithm. It has performed better than strstr(), Boyer-Moore, and KPM algorithms.
But I am not sending my code so that my algorithm gets included in linux kernel.
I am sending this code because linux kernel mailing list is in public domain and getting indexed by search engines. So, people 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
===================================================================================
Regards, Amit
| |