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

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

  1. В функции get_common_length сравниваются две строки str1 и str2 с помощью цикла while. Условие цикла *str1 && *str1++ == *str2++ означает, что цикл будет выполняться до тех пор, пока не будет найдена различающаяся буква в строках или пока не будут проверены все символы в строке str2.
  2. В функции main создаются две строки str1 и str2, и вычисляется их длина с помощью функции strlen.
  3. Переменная max_len инициализируется нулем и используется для хранения максимальной длины общей подстроки.
  4. Переменная cur_len используется для хранения текущей длины общей подстроки во время поиска.
  5. Переменная max_substr используется для хранения адреса начала наибольшей общей подстроки в строке str1.
  6. Два вложенных цикла for используются для перебора всех возможных начальных индексов общей подстроки в строках str1 и str2.
  7. Внутри вложенных циклов функция get_common_length вызывается для вычисления длины общей подстроки, начиная с текущих индексов.
  8. Если текущая длина общей подстроки больше max_len, то обновляются значения max_len и max_substr.
  9. В конце программы выводится наибольшая общая подстрока с помощью цикла for и функции putchar.
  10. Программа возвращает 0, что означает успешное завершение.

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

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