Лексикографическое сравнение.
Такое страшное название алгоритма означает всего-навсего, что он выполняет сравнение содержимого двух контейнеров, аналогичное сравнению текстовых строк.
Лексикографическое сравнение двух строк осуществляется функцией strcmp()
Функции
strlen( ) - определение длины строки;
int strlen(const char *s)
{
int res=0;
while(s[res]!='\0')
res++;
return res;
}
strset( ) - заполнение строки заданным символом;
char strset(const char *s, int c)
{
int i=0;
while(s[i]!='\0')
s[i++]=c;
return s;
}
strnset( ) – заполнение части строки заданным символом;
char strnset(const char *s, int c, int n)
{
int i=0;
while(s[i]!='\0'||i<n)
s[i++]=c;
return s;
}
strcpy( ) – копирование строки в строку;
char strcpy(char *dest, const char *src)
{
int i=0;
while(src[i]!='\0');
{
dest[i]=src[i];
i++;
}
return dest;
}
strcat( ) – соединение (конкатенация) строк;
char strcat(char *dest, const char *src)
{
int i=0, len=strlen(dest);
while(src[i]!='\0')
{
dest[len+i]=src[i];
i++;
}
dest[len+i]='\0';
return dest;
}
strcmp( ) – сравнение двух строк;
strcmp(char *s1, char *s2)
{
int len1=strlen(s1), len2=strlen(s2),
len=(len1>len2)?len1:l1n2;
int i=0, res=0;
for(;i<len;i++)
{
if((res=s1[i]=s2[i])==0) break;
}
return res;
}
strtok( ) – поиск и выделение лексических единиц в строке;
char *strstok(const char *s1, const char *s2)
{
char *res=NULL;
int i, len1=strlen(s1),
len2=strlen(s2);
for(i=0;i<len1;i++)
{ for(j=0;j<len2;j++)
{ s1[i]='\0';
res=s1+i; goto END;
}
}
END: return res;
}
strstr( ) – поиск подстроки в строке (по образцу).
char *strstr(char *s1, char *s2)
{
char *res=NULL;
int i, j, len1=strlen(s1),
len2=strlen(s2),
len=len1-len2;
if(len<0) return res;
for(i=0;i<len;i++)
{ for(j=0;j<len2;j++)
{
if(s1[i]!=s2[j])
break;
if(j==len2) return s1;
}
}
}
strchr( ) – поиск заданного символа в строке;
strpbrk( ) – поиск первого вхождения символа из шаблона в строке
strspn( ) – определение длины начальной части строки-шаблона, которой нет в исследуемой строке;
strstr KMP!
В информатике подстрока — это непустая связная часть строки.(Суффикс)
Пре́фикс-фу́нкция от строки — длина наибольшего префикса строки , который не совпадает с этой строкой и одновременно является её суффиксом.
int algorithm_KMP (char s[], char q[])
{
int i=0, j=-1, N, M;
N = strlen(s);
M = strlen(q);
int *d =(int*)malloc(M*sizeof(int)); // динамический массив длины М
/* Вычисление префикс-функции */
d[0]=-1;
while(i<M-1)
{
while((j>=0) && (q[j]!=q[i]))
j = d[j];
i++;
j++;
if(q[i]==q[j])
d[i]=d[j];
else
d[i]= j;
}
/* поиск */
for(i=0,j=0;(i<N)&&(j<M); i++,j++)
while((j>=0)&&(q[j]!=s[i]))
j=d[j];
free (d); /* освобождение памяти массива d */
if (j==M)
return i-j;
else /* i==N */
return -1;
}
Алгоритм Бойера — Мура
Алгоритм
Данный алгоритм также известен под названием алгоритм Бойера-Мура-Хорспула. Процедура алгоритма очень простая. Сначала строится таблица смещений для каждого символа. Затем исходная строка и шаблон совмещаются по началу, сравнение ведется по последнему символу. Если последние символы совпадают, то сравнение идет по предпоследнему символу и так далее. Если же символы не совпали, то шаблон смещается вправо, на число позиций взятое из таблицы смещений для символа из исходной строки, и тогда снова сравниваются последние символы исходной строки и шаблона. И так далее, пока не шаблон полностью не совпадет с подстрокой исходной строки, или не будет достигнут конец строки.