Найти наибольшую общую подстроку в двух строках - 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;
}

Объяснение кода листинга программы

  1. Включаем необходимые заголовочные файлы для работы с C
  2. Определяем функцию share_maxsub, которая принимает три аргумента: s1, s2 и e.
  3. Инициализируем переменные n, m, i, j, a, b и p как NULL. Переменная n используется для хранения длины наибольшей общей подстроки, m используется для хранения текущей максимальной длины подстроки, i и j используются для обхода строк s1 и s2 соответственно, a и b используются для хранения текущих символов подстроки, а p используется для хранения начала наибольшей общей подстроки.
  4. Используя два вложенных цикла, мы сравниваем каждый символ из s1 с каждым символом из s2. Если символы совпадают, мы продолжаем сравнивать следующие символы до тех пор, пока не найдем различие или не достигнем конца строки.
  5. Если текущая длина подстроки больше, чем текущая максимальная длина, мы обновляем переменные m и p.
  6. По завершении циклов, мы возвращаем p.
  7. В функции main мы создаем строки s1 и s2 и вызываем функцию share_maxsub, передавая ее в качестве аргументов эти строки и указатель на переменную e.
  8. Если наибольшая общая подстрока найдена, мы выводим ее на экран с помощью функции printf.
  9. Мы также можем вывести символы общей подстроки с помощью цикла while и функции putchar.
  10. Если наибольшая общая подстрока не найдена, мы выводим сообщение об ошибке с помощью функции puts.
  11. Функция main возвращает 0, что означает успешное выполнение программы.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4.182 из 5
Похожие ответы