Поиск подстроки в строке - C (СИ) (79429)
Формулировка задачи:
При запуске программы пользователь вводит две строки текста, каждая не длинее 1024 символа. Нужно вывести индексы всех вхождений второй строки в первую, используя алгоритм Бойера-Мура.
#include <stdio.h> #include <string.h> #define MAX 1023 int search_for_boyermoore(char first_line[MAX], char second_line[MAX]){ int table_shift[256]; int i; int j; int k; int length_of_the_first_line; int length_of_the_second_line; length_of_the_first_line = strlen(first_line); length_of_the_second_line = strlen(second_line); for (i=0; i<256; i++){ table_shift[i] = length_of_the_first_line; } for (i=0; i<length_of_the_first_line-1; i++){ table_shift[second_line[i]] = length_of_the_first_line-i-1; } for(i=length_of_the_first_line-1; i<length_of_the_second_line; i+=table_shift[first_line[i]]) { j = length_of_the_first_line-1; k = i; while ((j>=0)&&(second_line[j] == first_line[k])){ k--; j--; } if (j<0){ return k+1; } } printf("%d", k); return -1; } int main (){ char first_line[MAX]; char second_line[MAX]; printf("%s\n","Enter the first line..."); scanf("%s/n", &first_line); printf("%s\n","Enter the second line"); scanf("%s/n", &second_line); search_for_boyermoore(first_line[MAX], second_line[MAX]); return 0; }
Решение задачи: «Поиск подстроки в строке»
textual
Листинг программы
#include <stdio.h> #include <string.h> #define MAX 1023 size_t search_for_boyermoore(char first_line[MAX], char second_line[MAX]){ size_t table_shift[1023]; size_t i; size_t j; size_t k; size_t length_of_the_first_line; size_t length_of_the_second_line; length_of_the_first_line = strlen(first_line); length_of_the_second_line = strlen(second_line); for (i=0; i<1023; i++){ table_shift[i] = length_of_the_first_line; } for (i=0; i<length_of_the_first_line-1; i++){ table_shift[(unsigned char)first_line[i]] = length_of_the_first_line-i-1; } for(i=length_of_the_first_line-1; i<length_of_the_second_line; i+=table_shift[second_line[i]]) { j = length_of_the_first_line-1; k = i; while ((j>=0)&&(first_line[j] == second_line[k])){ k--; j--; } if (j<0){ return k+1; } } printf("%d\n",k); return -1; } int main (){ char first_line[MAX]; char second_line[MAX]; printf("%s\n","Enter the first line..."); scanf("%s", &first_line); printf("%s\n","Enter the second line"); scanf("%s", &second_line); search_for_boyermoore(first_line, second_line); return 0; }
Объяснение кода листинга программы
В этом коде реализован алгоритм поиска подстроки с использованием таблицы смещений (Boyer-Moore). Список действий:
- Создаются две строки
first_line
иsecond_line
, а также массивtable_shift
размером 1023. - Определяются длины строк
first_line
иsecond_line
с помощью функцииstrlen()
. - Заполняется массив
table_shift
значениемlength_of_the_first_line
. - В цикле обрабатываются символы строки
first_line
: в массивtable_shift
записывается значениеlength_of_the_first_line - i - 1
, гдеi
- номер текущего символа в строке. - В цикле выполняется поиск подстроки: начиная с последнего символа строки
second_line
, в каждой позиции проверяется, совпадает ли символ с символами строкиfirst_line
. Если символы совпадают, то сдвигается индекс в строкеsecond_line
на значение из массиваtable_shift
. Если символы не совпадают, то продолжается поиск с предыдущей позиции. Если подстрока найдена, то возвращается ее индекс в строкеsecond_line
. Если подстрока не найдена, то возвращается -1. - В основной функции
main()
запрашиваются строкиfirst_line
иsecond_line
, затем вызывается функцияsearch_for_boyermoore()
, и результат выводится на экран.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д