Найти наибольшую общую подстроку двух строк - C (СИ)
Формулировка задачи:
Найти наибольшую общую подстроку двух строк
Решение задачи: «Найти наибольшую общую подстроку двух строк»
textual
Листинг программы
#include <string.h> #include <stdio.h> size_t get_common_length(char* str1, char* str2) { size_t len = 0; while( *str1 && *str1++ == *str2++ ) { ++len; } return len; } int main(int argc, char* argv[]) { char* str1 = "kakadu zanaveska ananas kolibri kolovratka"; char* str2 = "kaka zanaves"; int len1 = strlen(str1); int len2 = strlen(str2); size_t max_len = 0; size_t cur_len; char* max_substr; int i, j; for( i = 0; i < len1 - max_len; ++i ) { for( j = 0; j < len2 - max_len; ++j ) { cur_len = get_common_length(str1 + i, str2 + j); if( cur_len > max_len ) { max_len = cur_len; max_substr = str1 + i; } } } for( i = 0; i < max_len; ++i ) { putchar(max_substr[i]); } return 0; }
Объяснение кода листинга программы
- В функции
get_common_length
сравниваются две строкиstr1
иstr2
с помощью циклаwhile
. Условие цикла*str1 && *str1++ == *str2++
означает, что цикл будет выполняться до тех пор, пока не будет найдена различающаяся буква в строках или пока не будут проверены все символы в строкеstr2
. - В функции
main
создаются две строкиstr1
иstr2
, и вычисляется их длина с помощью функцииstrlen
. - Переменная
max_len
инициализируется нулем и используется для хранения максимальной длины общей подстроки. - Переменная
cur_len
используется для хранения текущей длины общей подстроки во время поиска. - Переменная
max_substr
используется для хранения адреса начала наибольшей общей подстроки в строкеstr1
. - Два вложенных цикла
for
используются для перебора всех возможных начальных индексов общей подстроки в строкахstr1
иstr2
. - Внутри вложенных циклов функция
get_common_length
вызывается для вычисления длины общей подстроки, начиная с текущих индексов. - Если текущая длина общей подстроки больше
max_len
, то обновляются значенияmax_len
иmax_substr
. - В конце программы выводится наибольшая общая подстрока с помощью цикла
for
и функцииputchar
. - Программа возвращает
0
, что означает успешное завершение.