int mystrcmp(const char *a, const char *b){ while ( *a && *b && *a == *b ) ++a, ++b; return *a - *b;}char *strstr (const char *s1, char *s2){ int n; n = strlen(s2);for ( ; ;) { s1 = strchr(s1, s2[0]); if (s1 == NULL) return NULL;if (strncmp (s1, s2, n) == 0) return (char *) s1; s1++; }}int boyer_moore(const char * haystack, const char * needle){ int i, j, k; int needle_table[256]; int needle_len = strlen(needle); int haystack_len = strlen(haystack); if (needle_len { for (i = 0; i needle_table[i] = needle_len; for (i = 1; i needle_table[needle[i]] = needle_len-i; i = needle_len; j = i; while ((j > 0) && (i { j = needle_len; k = i; while ((j > 0) && (haystack[k] = needle[j])) { k--; j--; } i += needle_table[haystack[i]]; } if (k > haystack_len - needle_len then) return 0; else return k + 1; } else return 0;}Алгоритм Бойера — МураОписание алгоритмаПервым делом строится таблица смещений для искомого шаблона. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если последний символ шаблона и соответствующий ему при наложении символ строки не совпадают, то образец сдвигается относительно строки на величину, полученную из таблицы смещений. Причем берем символ из строки(а не шаблона) и смотрим соответствующий сдвиг в таблице. Сдвигаем и снова начинаем проверку с последнего символа. Если же символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит мы нашли подстроку и поиск окончен. Если же какой-то (НЕ ПОСЛЕДНИЙ) символ шаблона не совпадает с соответствующим символом строки, мы сдвигаем шаблон на ОДИН символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.Алгоритм Кнута-Морриса-Пратта Этот алгоритм был получен благодаря глубокому анализу алгоритма Морриса-Пратта. Итак, посмотрим, что еще можно сделать, чтобы увеличить размер сдвига. Рассмотрим сравнение на позиции i, где образец x[ 0, m - 1 ] сопоставляется с частью текста y[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между y[ i + j ] и x[ j ] , где 1 При сдвиге вполне можно ожидать, что префикс образца u сойдется с каким-нибудь суффиксом подслова текста u. Более того, если мы хотим избежать выявления другого несовпадения ( то есть не тратить на это операцию сравнения ;-) ), буква, находящаяся за префиксом v в образце должна отличаться от b. Наиболее длинный такой префикс v называется границей u ( он встречается по обоим сторонам u ). Это приводит к следующему алгоритму: пусть kmp_next[ j ] - длина длиннейшей границы x[ 0, j - 1 ], за которой следует символ c, отличающийся от x[ j ]. Тогда после сдвига мы можем возобновить сравнения между символами y[ i + j ] и x[ j - kmp_next[ j ] ] без возможной потери местонахождения образца. Таблица kmp_next может быть вычислена за O( m ) перед поиском через применение этого же алгоритма поиска к самому образцу ( т.е y = x ). При этом максимальное количество сравнений для одного символа текста - logФ( m ), где Ф - золотое сечение: ( корень из 5 + 1 ) / 2.void PRE_KMP( char *x, int m, int kmp_next[] ) { int i, j; i=0; j=kmp_next[0]=-1; while ( i while ( j > -1 && x[ i ] != x[ j ] ) j=kmp_next[ j ]; i++; j++; if ( x[ i ] == x[ j ] ) kmp_next[i]=kmp_next[j]; else kmp_next[ i ] = j; }}void KMP( char *x, char *y, int n, int m ) { int i, j, kmp_next[XSIZE]; /* Preprocessing */ PRE_KMP(x, m, kmp_next ); /* Searching */i=j=0; while ( i while ( j > -1 && x[ j ] != y[ i ] ) j = kmp_next[ j ]; i++; j++; if ( j >= m ) { OUTPUT( i - j ); j = kmp_next[ j ]; } }}