Понадобилось мне недавно написать аналог функции strstr(поиск подстроки в строке). Я решил его ускорить. В результате получился алгоритм. Я не нашел его по первым ссылкам в поисковике, зато там куча других алгоритмов, поэтому и написал это.

График сравнения скорости работы моего алгоритма, с функцией strstr на 600 кб тексте русскоязычной книги, при поиске строк размером от 1 до 255 байт:

Идея лежащая в основе алгоритма следующая. Сперва обозначения:

S - Строка в которой будет производится поиск будет называться
P - строка, которую ищем будет называться
sl - длина строки S
pl - длина строки P
PInd - табличка составляемая на первом этапе.

Итак идея такая: Если в строке S выбирать элементы с индексами равными: pl1, pl 2,..., plJ,..., pl (sl/pl), то если в отрезок pl(J-1)...pl (J+1) входит искомая строка P, то тогда выбранный элемент должен принадлежать строке P. Иначе строка бы не вписывалась по длине.

Картинка, где нарисовано до куда дотягивается P, в pl*3.:

И ещё, так как выбранный элемент входит в строку P обычно маленькое число раз, то можно проверять только эти вхождения, а не весь диапазон.

Итого алгоритм такой:

Этап 1. Сортировка P

Для всех элементов(символов) строки P сортируем индексы этих элементов по значению этих элементов. То есть делаем так, что-бы все номера всех элементов равных какому-то значению, можно было быстро получить. Эта табличка будет дальше называться PInd:

Как видно из этой таблички, при поиске на этапе 2 при искомой строке P равной "сортировать индексы" нам понадобится проверять максимум 2 варианта подстрок в S.

Сначала я для составления этой таблички использовал быструю сортировку и какую-то ещё, а потом я сообразил, что так как элементы строки однобайтовые, то можно использовать поразрядную.

Этап 2. Поиск

Проходим по строке строке S скачками равными pl, выбирая соответствующие элементы. Для каждого выбранного элемента проверяем входит ли он в строку P.

Если входит, то для всех индексов из PInd соответствующего элемента, проверяем совпадает ли подстрока S с началом в соответствующим индексу из PInd смещением относительно выбранного элемента и искомая строка P.

Если совпало, то возвращаем результат, если нет то продолжаем.

Худший вариант для этого алгоритма, зависит от способа сравнения строк во втором этапе. Если простое сравнение, то sl*pl+pl, если какой-то ещё, то другой. Я использовал просто сравнение, как в обычном strstr.

За счёт того, что алгоритм скачет через pl элементов и проверяет только возможные строки он работает быстрее.

Лучший вариант, это когда алгоритм проскачет всю строку S и не найдёт текст или найдёт с первого раза, тогда потратит примерно sl/pl.
Среднюю скорость я не знаю как подсчитать.

Вот одна из моих реализаций этого алгоритма, по которой строился график на языке си. Здесь pl ограничено, то есть таблица PInd строится по префиксу P длины max_len, а не по всей строке. Именно он использовался при построении графика:

Вот закодированный на си

char * my_strstr(const char * str1, const char * str2,size_t slen){ unsigned char max_len = 140; if (!*str2) return((char *)str1); //Очистка массивов unsigned char index_header_first; unsigned char index_header_end; unsigned char last_char; unsigned char sorted_index; memset(index_header_first,0x00,sizeof(unsigned char)*256); memset(index_header_end,0x00,sizeof(unsigned char)*256); memset(last_char,0x00,sizeof(unsigned char)*256); memset(sorted_index,0x00,sizeof(unsigned char)*256); //Этап 1. char *cp2 = (char*)str2; unsigned char v; unsigned int len =0; unsigned char current_ind = 1; while((v=*cp2) && (len slen){ return NULL; } //Этап 2. unsigned char *s1, *s2; //Начинаем проверку с элемента S+pl-1 unsigned char *cp = (unsigned char *) str1+(len-1); unsigned char *cp_end= cp+slen; while (cp=str1) { //Сравниваем строки s2 = (unsigned char*)str2; while (*s2 && !(*s1^*s2)) s1++, s2++; if (!*s2) return (char*)(cp-pos_in_len); } } while((ind = last_char)); } //Прыгаем вперёд на pl cp+=len; } return(NULL); }

Обновление: Это действительно не совсем прямая замена strstr, так как требует дополнительно параметр - длину строки S.

В программе строки могут определяться следующим образом:

• как строковые константы;
• как массивы символов;
• через указатель на символьный тип;
• как массивы строк.

Кроме того, должно быть предусмотрено выделение памяти для хранения строки.

Любая последовательность символов, заключенная в двойные кавычки «» , рассматривается как строковая константа .

Для корректного вывода любая строка должна заканчиваться нуль-символом "\0" , целочисленное значение которого равно 0. При объявлении строковой константы нуль-символ добавляется к ней автоматически. Так, последовательность символов, представляющая собой строковую константу, будет размещена в оперативной памяти компьютера, включая нулевой байт.

Под хранение строки выделяются последовательно идущие ячейки оперативной памяти. Таким образом, строка представляет собой массив символов. Для хранения кода каждого символа строки отводится 1 байт.

Для помещения в строковую константу некоторых служебных символов используются символьные комбинации. Так, если необходимо включить в строку символ двойной кавычки, ему должен предшествовать символ «обратный слеш»: ‘\»‘ .

Строковые константы размещаются в статической памяти. Начальный адрес последовательности символов в двойных кавычках трактуется как адрес строки. Строковые константы часто используются для осуществления диалога с пользователем в таких функциях, как printf() .

При определении массива символов необходимо сообщить компилятору требуемый размер памяти.

char m;

Компилятор также может самостоятельно определить размер массива символов, если инициализация массива задана при объявлении строковой константой:

char m2=;
char m3={"Т","и","х","и","е"," ","д","о","л","и","н","ы"," ","п","о","л","н","ы"," ","с","в","е","ж","е","й"," ","м","г","л","о","й","\0" };

В этом случае имена m2 и m3 являются указателями на первые элементы массивов:

• m2 эквивалентно &m2
• m2 эквивалентно ‘Г’
• m2 эквивалентно ‘o’
• m3 эквивалентно &m3
• m3 эквивалентно ‘x’

При объявлении массива символов и инициализации его строковой константой можно явно указать размер массива, но указанный размер массива должен быть больше, чем размер инициализирующей строковой константы:

char m2="Горные вершины спят во тьме ночной." ;

Для задания строки можно использовать указатель на символьный тип .

char *m4;

В этом случае объявление массива переменной m4 может быть присвоен адрес массива:

m4 = m3;
*m4 эквивалентно m3="Т"
*(m4+1) эквивалентно m3="и"

Здесь m3 является константой-указателем. Нельзя изменить m3 , так как это означало бы изменение положения (адреса) массива в памяти, в отличие от m4 .

Для указателя можно использовать операцию увеличения (перемещения на следующий символ):

Массивы символьных строк

Иногда в программах возникает необходимость описание массива символьных строк . В этом случае можно использовать индекс строки для доступа к нескольким разным строкам.

char *poet = {"Погиб поэт!", "- невольник чести -" ,
"Пал," , "оклеветанный молвой…" };

В этом случае poet является массивом, состоящим из четырех указателей на символьные строки. Каждая строка символов представляет собой символьный массив, поэтому имеется четыре указателя на массивы. Указатель poet ссылается на первую строку:
*poet эквивалентно "П" ,
*poet[l] эквивалентно "-" .

Инициализация выполняется по правилам, определенным для массивов.
Тексты в кавычках эквивалентны инициализации каждой строки в массиве. Запятая разделяет соседние
последовательности.
Кроме того, можно явно задавать размер строк символов, используя описание, подобное такому:

char poet;

Разница заключается в том, что такая форма задает «прямоугольный» массив, в котором все строки имеют одинаковую длину.

Свободный массив

Описание

сhar *poet;

Операции со строками

Большинство операций языка Си, имеющих дело со строками, работает с указателями. Для размещения в оперативной памяти строки символов необходимо:

• выделить блок оперативной памяти под массив;
• проинициализировать строку.

Для выделения памяти под хранение строки могут использоваться функции динамического выделения памяти . При этом необходимо учитывать требуемый размер строки:

char *name;
name = (char *)malloc(10);
scanf("%9s" , name);

Для ввода строки использована функция scanf() , причем введенная строка не может превышать 9 символов. Последний символ будет содержать "\0" .

Функции ввода строк

Для ввода строки может использоваться функция scanf() . Однако функция scanf() предназначена скорее для получения слова, а не строки. Если применять формат "%s" для ввода, строка вводится до (но не включая) следующего пустого символа, которым может быть пробел, табуляция или перевод строки.

Для ввода строки, включая пробелы, используется функция

char * gets(char *);

char * gets_s(char *);

В качестве аргумента функции передается указатель на строку, в которую осуществляется ввод. Функция просит пользователя ввести строку, которую она помещает в массив, пока пользователь не нажмет Enter .

Функции вывода строк

Для вывода строк можно воспользоваться рассмотренной ранее функцией

printf("%s" , str); // str - указатель на строку

или в сокращенном формате

printf(str);

Для вывода строк также может использоваться функция

int puts (char *s);

которая печатает строку s и переводит курсор на новую строку (в отличие от printf() ). Функция puts() также может использоваться для вывода строковых констант, заключенных в кавычки.

Функция ввода символов

Для ввода символов может использоваться функция

char getchar();

Функция вывода символов

Для вывода символов может использоваться функция

char putchar(char );

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include
#include
#include
int main() {
char s, sym;
int count, i;
system("chcp 1251" );
system("cls" );
printf("Введите строку: " );
gets_s(s);
printf("Введите символ: " );
sym = getchar();
count = 0;
for (i = 0; s[i] != "\0" ; i++)
{
if (s[i] == sym)
count++;
}
printf("В строке\n" );
puts(s); // Вывод строки
printf("символ " );
putchar(sym); // Вывод символа
printf(" встречается %d раз" , count);
getchar(); getchar();
return 0;
}

Результат выполнения

Основные функции стандартной библиотеки string.h

Основные функции стандартной библиотеки string.h приведены в таблице.