Найти наибольшую общую подстроку в двух строках - C (СИ)
Формулировка задачи:
Помогите написать программу на Си: найти длиннейшее вхождение в двух строках. строки могут быть разной длины.
ПРИМЕР:
123cde
453cd86
ответ: 3cd
Решение задачи: «Найти наибольшую общую подстроку в двух строках»
textual
Листинг программы
#include <stdio.h> //наивный алгоритм const char* share_maxsub(const char* s1, const char* s2, const char** e){ int n, m; const char* i, *j, *a, *b, *p = NULL; for(m = 0, i = s1; *i; ++i){ for(j = s2; *j; ++j){ a = i; b = j; while(*a && (*a == *b)){ ++a; ++b; } if((n = (int)(a - i)) > m){ m = n; p = i; *e = a; } } } return p; } int main(void){ const char* p, *e; char s1[] = "123cde"; char s2[] = "453cd86"; p = share_maxsub(s1, s2, &e); if(p != NULL){ //выводим общую макс. под-строку printf("%.*s\n", e - p, p); //можно вывести и так while(p != e) putchar(*p++); putchar('\n'); } else puts("error find!"); return 0; }
Объяснение кода листинга программы
- Включаем необходимые заголовочные файлы для работы с C
- Определяем функцию share_maxsub, которая принимает три аргумента: s1, s2 и e.
- Инициализируем переменные n, m, i, j, a, b и p как NULL. Переменная n используется для хранения длины наибольшей общей подстроки, m используется для хранения текущей максимальной длины подстроки, i и j используются для обхода строк s1 и s2 соответственно, a и b используются для хранения текущих символов подстроки, а p используется для хранения начала наибольшей общей подстроки.
- Используя два вложенных цикла, мы сравниваем каждый символ из s1 с каждым символом из s2. Если символы совпадают, мы продолжаем сравнивать следующие символы до тех пор, пока не найдем различие или не достигнем конца строки.
- Если текущая длина подстроки больше, чем текущая максимальная длина, мы обновляем переменные m и p.
- По завершении циклов, мы возвращаем p.
- В функции main мы создаем строки s1 и s2 и вызываем функцию share_maxsub, передавая ее в качестве аргументов эти строки и указатель на переменную e.
- Если наибольшая общая подстрока найдена, мы выводим ее на экран с помощью функции printf.
- Мы также можем вывести символы общей подстроки с помощью цикла while и функции putchar.
- Если наибольшая общая подстрока не найдена, мы выводим сообщение об ошибке с помощью функции puts.
- Функция main возвращает 0, что означает успешное выполнение программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д