Алгоритмы поиска в тексте

n, где x[i] – i -ый символ строки Х, принадлежащий

алфавиту. Строка, не содержащая ни одного символа, называется пустой.
Строка X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. При этом Z1 называют левым, а Z2 – правым крылом подстроки. Подстрокой может быть и сама строка. Иногда при этом строку X называют вхождением в строку Y. Например, строки hrf и fhr является подстроками строки abhrfhr.

Z, что Y=XZ. Причем сама строка является префиксом для себя

самой (так как найдется нулевая строка L, что X=XL ). Например, подстрока ab является префиксом строки abcfa.

Подстрока X называется суффиксом строки Y, если есть такая подстрока Z, что Y=ZX. Аналогично, строка является суффиксом себя самой. Например, подстрока bfg является суффиксом строки vsenfbfg.

*substring){
int sl, ssl;
int res = -1;
sl =

strlen(string);
ssl = strlen(substring);
if ( sl == 0 )
cout << "Неверно задана строка\n";
else if ( ssl == 0 )
cout << "Неверно задана подстрока\n";
else
for (int i = 0; i < sl - ssl + 1; i++)
for (int j = 0; j < ssl; j++)
if ( substring[j] != string[i+j] )
break;
else if ( j == ssl - 1 ){
res = i;
break;
}
return res;
}

в 1977 году. Алгоритм Кнута, Морриса и Пратта (КМП-алгоритм) требует

только O(n) сравнений даже в самом худшем случае.

*substring){
int sl, ssl;
int res = -1;
sl =

strlen(string);
ssl = strlen(substring);
if ( sl == 0 )
cout << "Неверно задана строка\n";
else if ( ssl == 0 )
cout << "Неверно задана подстрока\n";
else {
int i, j = 0, k = -1;
int *d;
d = new int[1000];
d[0] = -1;
while ( j < ssl - 1 ) {
while ( k >= 0 && substring[j] != substring[k] )
k = d[k];
j++;
k++;
if ( substring[j] == substring[k] )
d[j] = d[k];
else
d[j] = k;
}
i = 0;
j = 0;
while ( j < ssl && i < sl ){
while ( j >= 0 && string[i] != substring[j] )
j = d[j];
i++;
j++;
}
delete [] d;
res = j == ssl ? i - ssl : -1;
}
return res;
}

1977 году
наихудший случай O(m+n)

int sl, ssl;
int res = -1;
sl = strlen(string);

ssl = strlen(substring);
if ( sl == 0 )
cout << "Неверно задана строка\n";
else if ( ssl == 0 )
cout << "Неверно задана подстрока\n";
else {
int i, Pos;
int BMT[256];
for ( i = 0; i < 256; i ++ )
BMT[i] = ssl;
for ( i = ssl-1; i >= 0; i-- )
if ( BMT[(short)(substring[i])] == ssl )
BMT[(short)(substring[i])] = ssl - i - 1;
Pos = ssl - 1;
while ( Pos < sl )
if ( substring[ssl - 1] != string[Pos] )
Pos = Pos + BMT[(short)(string[Pos])];
else
for ( i = ssl - 2; i >= 0; i-- ){
if ( substring[i] != string[Pos - ssl + i + 1] ) {
Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1;
break;
}
else
if ( i == 0 )
return Pos - ssl + 1;
cout << "\t" << i << endl;
} }
return res; }