Geum.ru

Int needle len = strlen(needle)

Вид материалаДокументы
Подобный материал:
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 < haystack_len then)

{

for (i = 0; i < 256; i++)

needle_table[i] = needle_len;

for (i = 1; i < needle_len; i++)

needle_table[needle[i]] = needle_len-i;

i = needle_len;

j = i;

while ((j > 0) && (i <= haystack_len))

{

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 < j < m. Тогда y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u и a = y[ i + j ] =/= x[ j ] = b.

При сдвиге вполне можно ожидать, что префикс образца 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 < m ) {

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 < n ) {

while ( j > -1 && x[ j ] != y[ i ] ) j = kmp_next[ j ];

i++;

j++;

if ( j >= m ) {

OUTPUT( i - j );

j = kmp_next[ j ];

}

}

}