Поиск подстрок в C: методы и реализация

Поиск подстроки в строке на языке C — это фундаментальная задача в программировании, для решения которой существует несколько стандартных и продвинутых методов. Основной функцией для поиска подстрок является strstr, входящая в стандартную библиотеку <string.h>, которая находит первое вхождение подстроки и возвращает указатель на нее или NULL, если подстрока не найдена. Кроме стандартных функций существуют более сложные алгоритмы, такие как Кнута-Морриса-Пратта и Бойера-Мура, которые обеспечивают более высокую производительность в определенных сценариях.

Содержание

• Введение в поиск подстрок в языке C
• Стандартная функция strstr для поиска подстрок
• Дополнительные функции для поиска символов и подстрок
• Алгоритмы поиска подстрок: Кнута-Морриса-Пратта и Бойера-Мура
• Практические примеры реализации поиска подстрок
• Заключение: Выбор метода для поиска подстрок

Введение в поиск подстрок в языке C

Поиск подстрок — одна из самых распространенных операций при работе со строками в языке C. Эта задача встречается в различных областях программирования: от текстовых редакторов до систем обработки данных. Стандартная библиотека C предоставляет несколько функций для поиска подстрок, включая strstr, strcasestr и другие. Помимо стандартных функций, существуют продвинутые алгоритмы поиска, такие как алгоритм Кнута-Морриса-Пратта (KMP) и алгоритм Бойера-Мура, которые обеспечивают более высокую производительность в определенных сценариях.

Основная задача поиска подстрок состоит в нахождении всех позиций, где одна строка (подстрока) начинается внутри другой строки (основной строки). Эффективность алгоритма поиска может существенно влиять на производительность приложения, особенно при работе с большими объемами данных или в системах реального времени.

Стандартная функция strstr для поиска подстрок

Функция strstr является основной функцией стандартной библиотеки C для поиска подстрок. Она объявлена в заголовочном файле <string.h> и используется для поиска первого вхождения подстроки в строке. Функция принимает два аргумента: строку, в которой производится поиск, и подстроку, которую нужно найти. Если подстрока найдена, функция возвращает указатель на начало подстроки в исходной строке, иначе возвращает NULL.

Вот пример использования функции strstr:

#include <stdio.h>
#include <string.h>

int main(void) {
 const char *text = "Hello, world!";
 const char *substr = "world";
 char *pos = strstr(text, substr);
 
 if (pos) {
 printf("Найдено: %s\n", pos);
 // Вывод: Найдено: world!
 } else {
 printf("Не найдено\n");
 }
 return 0;
}

В этом примере функция strstr ищет подстроку “world” в строке “Hello, world!” и находит ее. Выводится найденная подстрока вместе с оставшейся частью строки. Функция чувствительна к регистру символов, то есть “World” и “world” будут считаться разными подстроками.

Для нечувствительного к регистру поиска можно использовать функцию strcasestr (которая является расширением POSIX) или написать собственную реализацию:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

// Нечувствительная к регистру версия strstr
char *stristr(const char *haystack, const char *needle) {
 if (!haystack || !needle) return NULL;
 
 for (; *haystack; haystack++) {
 const char *h = haystack;
 const char *n = needle;
 
 for (; *h && *n && tolower(*h) == tolower(*n); h++, n++);
 
 if (!*n) return (char *)haystack;
 }
 return NULL;
}

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

Помимо strstr в стандартной библиотеке C существует несколько других функций, которые могут быть полезны для поиска символов и подстрок:

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

Функция strchr используется для поиска первого вхождения указанного символа в строке. Она возвращает указатель на найденный символ или NULL, если символ не найден:

#include <stdio.h>
#include <string.h>

int main() {
 char str[] = "This is a sample string";
 char *pch = strchr(str, 's');
 
 while (pch != NULL) {
 printf("Найдено 's' на позиции %ld\n", pch - str + 1);
 pch = strchr(pch + 1, 's');
 }
 return 0;
}

Функция strrchr для последнего вхождения символа

Функция strrchr ищет последнее вхождения символа в строке:

#include <stdio.h>
#include <string.h>

int main() {
 char str[] = "This is a sample string";
 char *pch = strrchr(str, 's');
 printf("Последнее вхождение 's' находится на позиции %ld\n", pch - str + 1);
 return 0;
}

Функция strspn для поиска символов из набора

Функция strspn возвращает длину начального сегмента строки, который состоит только из символов из указанного набора:

#include <stdio.h>
#include <string.h>

int main() {
 char str[] = "Hello, world!";
 int len = strspn(str, "Helo, wrd");
 printf("Длина начального сегмента: %d\n", len); // Вывод: 13
 return 0;
}

Функция strcspn для поиска символов, не входящих в набор

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

#include <stdio.h>
#include <string.h>

int main() {
 char str[] = "Hello, world!";
 int len = strcspn(str, " ,!");
 printf("Длина сегмента до первого разделителя: %d\n", len); // Вывод: 5
 return 0;
}

Алгоритмы поиска подстрок: Кнута-Морриса-Пратта и Бойера-Мура

Алгоритм Кнута-Морриса-Пратта (KMP)

Алгоритм Кнута-Морриса-Пратта (KMP) является эффективным алгоритмом поиска подстрок со сложностью O(n+m), где n - длина текста, m - длина шаблона. KMP использует префикс-функцию для избежания ненужных сравнений.

Основная идея алгоритма заключается в предварительной обработке шаблона для создания массива lps (longest proper prefix which is also suffix), который позволяет алгоритму “запоминать” информацию о шаблоне и пропускать ненужные сравнения.

Вот реализация алгоритма KMP:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void computeLPSArray(char *pat, int M, int *lps) {
 int len = 0;
 lps[0] = 0;
 int i = 1;
 
 while (i < M) {
 if (pat[i] == pat[len]) {
 len++;
 lps[i] = len;
 i++;
 } else {
 if (len != 0) {
 len = lps[len - 1];
 } else {
 lps[i] = 0;
 i++;
 }
 }
 }
}

void KMPSearch(char *pat, char *txt) {
 int M = strlen(pat);
 int N = strlen(txt);
 int *lps = (int *)malloc(sizeof(int) * M);
 
 computeLPSArray(pat, M, lps);
 
 int i = 0; // индекс для txt
 int j = 0; // индекс для pat
 
 while (i < N) {
 if (pat[j] == txt[i]) {
 j++;
 i++;
 }
 
 if (j == M) {
 printf("Найдено вхождение на позиции %d\n", i - j);
 j = lps[j - 1];
 } else if (i < N && pat[j] != txt[i]) {
 if (j != 0) {
 j = lps[j - 1];
 } else {
 i++;
 }
 }
 }
 free(lps);
}

Алгоритм Бойера-Мура

Алгоритм Бойера-Мура - еще один эффективный алгоритм поиска подстрок, который обычно работает быстрее KMP на практике. Он использует две основные эвристики: “плохого символа” и “хорошего суффикса”.

Эвристика “плохого символа” позволяет пропустить часть текста, когда символ не совпадает, а эвристика “хорошего суффикса” использует информацию о совпадающих суффиксах для оптимизации поиска.

Вот упрощенная реализация алгоритма Бойера-Мура:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NO_OF_CHARS 256

void badCharHeuristic(char *str, int size, int *badChar) {
 int i;
 
 for (i = 0; i < NO_OF_CHARS; i++) {
 badChar[i] = -1;
 }
 
 for (i = 0; i < size; i++) {
 badChar[(int)str[i]] = i;
 }
}

void search(char *txt, char *pat) {
 int m = strlen(pat);
 int n = strlen(txt);
 int *badChar = (int *)malloc(sizeof(int) * NO_OF_CHARS);
 
 badCharHeuristic(pat, m, badChar);
 
 int s = 0; // смещение
 
 while (s <= (n - m)) {
 int j = m - 1;
 
 while (j >= 0 && pat[j] == txt[s + j])
 j--;
 
 if (j < 0) {
 printf("Найдено вхождение на позиции %d\n", s);
 s += (s + m < n) ? m - badChar[txt[s + m]] : 1;
 } else {
 s += max(1, j - badChar[txt[s + j]]);
 }
 }
 free(badChar);
}

В среднем сложность алгоритма Бойера-Мура составляет O(n/m), но в худшем случае она может быть O(nm).

Практические примеры реализации поиска подстрок

Пример 1: Поиск всех вхождений подстроки

#include <stdio.h>
#include <string.h>

void findAllOccurrences(char *str, char *sub) {
 int len = strlen(str);
 int subLen = strlen(sub);
 int count = 0;
 
 for (int i = 0; i <= len - subLen; i++) {
 int j;
 for (j = 0; j < subLen; j++) {
 if (str[i + j] != sub[j]) {
 break;
 }
 }
 
 if (j == subLen) {
 printf("Найдено вхождение на позиции %d\n", i);
 count++;
 }
 }
 
 printf("Всего найдено %d вхождений\n", count);
}

int main() {
 char text[] = "abracadabra";
 char pattern[] = "abra";
 findAllOccurrences(text, pattern);
 return 0;
}

Пример 2: Замена подстроки

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *replaceSubstring(char *str, char *old, char *new) {
 char *result;
 int i, count = 0;
 int newLen = strlen(new);
 int oldLen = strlen(old);
 
 // Считаем количество вхождений
 for (i = 0; str[i] != '\0';) {
 if (strstr(&str[i], old) == &str[i]) {
 count++;
 i += oldLen;
 } else {
 i++;
 }
 }
 
 // Выделяем память для новой строки
 result = (char *)malloc(strlen(str) + count * (newLen - oldLen) + 1);
 
 i = 0;
 while (*str) {
 if (strstr(str, old) == str) {
 strcpy(&result[i], new);
 i += newLen;
 str += oldLen;
 } else {
 result[i++] = *str++;
 }
 }
 result[i] = '\0';
 
 return result;
}

int main() {
 char text[] = "Hello, world! Hello, universe!";
 char *result = replaceSubstring(text, "Hello", "Hi");
 printf("Исходная строка: %s\n", text);
 printf("Измененная строка: %s\n", result);
 free(result);
 return 0;
}

Пример 3: Поиск подстроки с учетом регистра

#include <stdio.h>
#include <string.h>
#include <ctype.h>

char *caseInsensitiveStrstr(char *haystack, char *needle) {
 char *h = haystack;
 char *n = needle;
 
 while (*h) {
 if (tolower(*h) == tolower(*n)) {
 char *found = h;
 while (*h && *n && tolower(*h) == tolower(*n)) {
 h++;
 n++;
 }
 if (!*n) return found;
 h = found + 1;
 n = needle;
 } else {
 h++;
 }
 }
 return NULL;
}

int main() {
 char text[] = "Hello, World! Welcome to C programming";
 char *result = caseInsensitiveStrstr(text, "world");
 if (result) {
 printf("Найдено: %s\n", result);
 } else {
 printf("Не найдено\n");
 }
 return 0;
}

Заключение: Выбор метода для поиска подстрок

Выбор метода для поиска подстрок в языке C зависит от конкретных требований к производительности, чувствительности к регистру и объема данных. Для большинства повседневных задач достаточно использовать стандартную функцию strstr, которая проста в использовании и достаточно эффективна для небольших и средних строк.

Для работы с большими объемами данных или в системах реального времени, где производительность имеет критическое значение, следует考虑 использование более сложных алгоритмов, таких как KMP или Бойера-Мура. Эти алгоритмы обеспечивают лучшую временную сложность в определенных сценариях, хотя их реализация более сложна.

Для поиска с учетом регистра необходимо использовать либо функцию strcasestr (если она доступна), либо написать собственную реализацию, как показано в примерах. При работе с очень большими строками также стоит учитывать возможность оптимизации использования памяти и распараллеливания вычислений.

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

Источники

1. CPlusPlus String Reference — Документация по функциям работы со строками в C: https://www.cplusplus.com/reference/cstring/
2. strstr Function Documentation — Подробная информация о функции strstr для поиска подстрок: https://www.cplusplus.com/reference/cstring/strstr/
3. strchr Function Documentation — Информация о функции поиска символов в строках: https://www.cplusplus.com/reference/cstring/strchr/
4. KMP Algorithm Explanation — Подробное описание алгоритма Кнута-Морриса-Пратта: https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
5. Boyer-Moore Algorithm Explanation — Описание алгоритма Бойера-Мура для поиска подстрок: https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/