C语言中最长的公共子串

Question

我用C语言实现了在两个字符串之间查找最长的公共子字符串的代码。

Syntax: int compute_lcs(char *first_string, char *second_string, struct lcs_result *lcsr, int *error_num_ptr);

我知道我可以在函数中的任何地方声明/定义变量，但我不这样做。我使用K & R风格声明/定义函数顶部的所有变量。所以，请不要对此发表评论。

该代码是使用下列gcc旗帜编译的：

-Wall -Werror -Wextra -Wundef -Wunreachable code -Winit-self -Wparentheses -Wconversion --Wall转换--Wall比较-Werror-隐式-函数声明-Wsign原型-Winit声明-Wformat-安全性

守则如下：

longest_common_substring.c

#include "longest_common_substring.h"

#include 
#include 
#include 

/*
 * const char *get_error_string(int error_num):
 *
 * Function get_error_string() returns the error string corresponding to the
 * value in 'error_num' argument.
 */
const char *get_error_string(int error_num)
{

    switch (error_num) {
        case NO_ERROR:
            return "No error happened.";
        case FIRST_STRING_IS_NULL:
            return "Argument 'first_string' is NULL.";
        case SECOND_STRING_IS_NULL:
            return "Argument 'second_string' is NULL.";
        case FIRST_STRING_IS_EMPTY:
            return "Argument 'first_string' is empty.";
        case SECOND_STRING_IS_EMPTY:
            return "Argument 'second_string' is empty.";
        case LCSR_IS_NULL:
            return "Argument 'lcsr' is NULL.";
        default:
            return "Invalid error number given.";
    } // end of switch

} // end of function get_error_string

/*
 * int compute_lcs(char *first_string, char *second_string, struct lcs_result *lcsr, int *error_num_ptr):
 *
 * Fucntion compute_lcs() finds the longest common substring between 'first_string'
 * and 'second_string'.
 */
int compute_lcs(char *first_string, char *second_string, struct lcs_result *lcsr, int *error_num_ptr)
{

    long first_string_len = 0;
    long second_string_len = 0;
    long temp_first_string_start_index = -1;
    long temp_first_string_end_index = -1;
    long temp_second_string_start_index = -1;
    long temp_second_string_end_index = -1;
    long cs_len = 0;
    long i = 0, j = 0, m = 0, n = 0;
    int find_no_more = 0;
    int some_cs_found = 0;

    if (!first_string) {
        if (error_num_ptr)
            *error_num_ptr = FIRST_STRING_IS_NULL;
        return LCS_NOT_FOUND;
    }

    if (!second_string) {
        if (error_num_ptr)
            *error_num_ptr = SECOND_STRING_IS_NULL;
        return LCS_NOT_FOUND;
    }

    if (!*first_string) {
        if (error_num_ptr)
            *error_num_ptr = FIRST_STRING_IS_EMPTY;
        return LCS_NOT_FOUND;
    }

    if (!*second_string) {
        if (error_num_ptr)
            *error_num_ptr = SECOND_STRING_IS_EMPTY;
        return LCS_NOT_FOUND;
    }

    if (!lcsr) {
        if (error_num_ptr)
            *error_num_ptr = LCSR_IS_NULL;
        return LCS_NOT_FOUND;
    }

    lcsr->first_string_start_index = -1;
    lcsr->first_string_end_index = -1;
    lcsr->second_string_start_index = -1;
    lcsr->second_string_end_index = -1;

    first_string_len = (long)(strlen(first_string));
    second_string_len = (long)(strlen(second_string));

    for (i = 0; i < first_string_len; i = i + 1) {

        for (j = 0; j < second_string_len; j = j + 1) {

            temp_first_string_start_index = -1;
            temp_first_string_end_index = -1;
            temp_second_string_start_index = -1;
            temp_second_string_end_index = -1;
            some_cs_found = 0;

            for (m = i, n = j; ((m < first_string_len) && (n < second_string_len)); m = m + 1, n = n + 1) {
                if (second_string[n] != first_string[m]) {
                    break;
                }

                some_cs_found = 1;

                if (temp_first_string_start_index == -1) {

                    if (temp_second_string_start_index != -1) {
                        fprintf(stderr, "Error: temp_first_string_end_index is -1 but"
                               " temp_second_string_start_index is not -1. Exiting..");
                        exit(1);
                    }

                    temp_first_string_start_index = m;
                    temp_first_string_end_index = m;
                    temp_second_string_start_index = n;
                    temp_second_string_end_index = n;

                } else {

                    temp_first_string_end_index = m;
                    temp_second_string_end_index = n;

                } // end of if else temp_first_string_start_index == -1

            } // end of for m, n

            if (some_cs_found == 1) {

                if ((lcsr->first_string_start_index == -1) ||
                    ((temp_first_string_end_index - temp_first_string_start_index + 1) > (lcsr->first_string_end_index - lcsr->first_string_start_index + 1))) {

                    lcsr->first_string_start_index = temp_first_string_start_index;
                    lcsr->first_string_end_index = temp_first_string_end_index;
                    lcsr->second_string_start_index = temp_second_string_start_index;
                    lcsr->second_string_end_index = temp_second_string_end_index;

                }

                // now check if length of CS is equal to length of any string
                cs_len = lcsr->first_string_end_index - lcsr->first_string_start_index + 1;
                if ((cs_len == first_string_len) || (cs_len == second_string_len)) {
                    find_no_more = 1;
                    break;
                }

            } // end of if some_cs_found == 1

        } // end of for j

        if (find_no_more == 1) {
            break;
        }

    } // end of for i

    if (lcsr->first_string_start_index == -1)
        return LCS_NOT_FOUND;
    
    return LCS_FOUND;

} // end of compute_lcs

longest_common_substring.h

#ifndef LONGEST_COMMON_SUBSTRING_H
#define LONGEST_COMMON_SUBSTRING_H

#define LCS_NOT_FOUND 0
#define LCS_FOUND 1

struct lcs_result {
    long first_string_start_index;
    long first_string_end_index;
    long second_string_start_index;
    long second_string_end_index;
};

enum {
    NO_ERROR = 0, // No error happened
    FIRST_STRING_IS_NULL = -1, // Argument 'first_string' is NULL
    SECOND_STRING_IS_NULL = -2, // Argument 'second_string' is NULL
    FIRST_STRING_IS_EMPTY = -3, // Argument 'first_string' is empty
    SECOND_STRING_IS_EMPTY = -4, // Argument 'second_string' is empty
    LCSR_IS_NULL = -5, // Argument 'lcsr' is NULL
};

/*
 * const char *get_error_string(int error_num):
 *
 * Function get_error_string() returns the error string corresponding to the
 * value in 'error_num' argument.
 */
const char *get_error_string(int error_num);

/*
 * int compute_lcs(char *first_string, char *second_string, struct lcs_result *lcsr, int *error_num_ptr):
 *
 * Fucntion compute_lcs() finds the longest common substring between 'first_string'
 * and 'second_string'.
 */
int compute_lcs(char *first_string, char *second_string, struct lcs_result *lcsr, int *error_num_ptr);

#endif

test_longest_common_substring.c

#include "longest_common_substring.h"

#include 
#include 
#include 

char *get_input_from_stdin_and_discard_extra_characters(char *str, long size);

#define ARRAY_SIZE 256

int main(void)
{

    struct lcs_result lcsr;
    char first_string[ARRAY_SIZE] = {0};
    char second_string[ARRAY_SIZE] = {0};
    int error_num = 0;
    char *arg_first_string = NULL;
    char *arg_second_string = NULL;
    struct lcs_result *arg_lcsr = NULL;
    int *arg_error_num_ptr = NULL;
    int ret_val = LCS_NOT_FOUND;
    char user_input_yes_no[2] = {0};

    while (1) {

        system("clear");

        lcsr.first_string_start_index = -1;
        lcsr.first_string_end_index = -1;
        lcsr.second_string_start_index = -1;
        lcsr.second_string_end_index = -1;

        error_num = 0;

        arg_first_string = first_string;
        arg_second_string = second_string;
        arg_lcsr = &lcsr;
        arg_error_num_ptr = &error_num;

        printf("\nPlease input first string (max 255 characters) (To enter NULL"
               " string, type NULL and press ENTER): ");
        get_input_from_stdin_and_discard_extra_characters(first_string, ARRAY_SIZE);
        if (strcmp(first_string, "NULL") == 0) {
            arg_first_string = NULL;
        }

        printf("\nPlease input second string (max 255 characters) (To enter NULL"
               " string, type NULL and press ENTER): ");
        get_input_from_stdin_and_discard_extra_characters(second_string, ARRAY_SIZE);
        if (strcmp(second_string, "NULL") == 0) {
            arg_second_string = NULL;
        }

        while (1) {
            printf("\nDo you want pass argument 'lcsr' as NULL? [y/n]: ");
            get_input_from_stdin_and_discard_extra_characters(user_input_yes_no, 2);
            if (strcmp(user_input_yes_no, "y") == 0) {
                arg_lcsr = NULL;
                break;
            } else if (strcmp(user_input_yes_no, "n") == 0) {
                break;
            }
        }

        user_input_yes_no[0] = 0; user_input_yes_no[1] = 0;
        while (1) {
            printf("\nDo you want pass argument 'error_num_ptr' as NULL? [y/n]: ");
            get_input_from_stdin_and_discard_extra_characters(user_input_yes_no, 2);
            if (strcmp(user_input_yes_no, "y") == 0) {
                arg_error_num_ptr = NULL;
                break;
            } else if (strcmp(user_input_yes_no, "n") == 0) {
                break;
            }
        }

        printf("\n");
        printf("\n-----------------");
        printf("\nInput parameters:");
        printf("\n-----------------\n");
        printf("first_string = \"%s\" (length = %zu)\n", arg_first_string ? arg_first_string : "(null string)", arg_first_string ? strlen(arg_first_string) : 0);
        printf("second_string = \"%s\" (length = %zu)\n", arg_second_string ? arg_second_string : "(null string)", arg_second_string ? strlen(arg_second_string) : 0);

        printf("\n-------");
        printf("\nResult:");
        printf("\n-------\n");
        ret_val = compute_lcs(arg_first_string, arg_second_string, arg_lcsr, arg_error_num_ptr);
        if (ret_val == LCS_FOUND) {
            long lcs_len = lcsr.first_string_end_index - lcsr.first_string_start_index + 1;
            printf("Longest common substring = \"%.*s\" (length = %ld)\n",
                   (int)(lcs_len), first_string + lcsr.first_string_start_index, lcs_len);
            printf("First string (Index starts from 0): start index of LCS = %ld, end index of LCS = %ld\n",
                   lcsr.first_string_start_index, lcsr.first_string_end_index);
            printf("Second string (Index starts from 0): start index of LCS = %ld, end index of LCS = %ld\n",
                   lcsr.second_string_start_index, lcsr.second_string_end_index);
            printf("\n");
        } else {
            printf("Longest common substring not found.");
            if (arg_error_num_ptr)
                printf(" Error: %s\n", get_error_string(error_num));
            else
                printf("\n");
            printf("\n");
        }

        printf("\n\nPlease press ENTER to continue..");
        // now clear the stdin input buffer
        get_input_from_stdin_and_discard_extra_characters(NULL, 0);

    } // end of while (1) loop

    return(0);

} // end of main

/*
 * get_input_from_stdin_and_discard_extra_characters(char *str, long size):
 *
 * Function get_input_from_stdin_and_discard_extra_characters() reads at most
 * 'size - 1' characters into 'str' from stdin and then appends the null
 * character ('\0'). If 'size' is 0 then this function will discard all input
 * and return NULL. So, to discard all input, this function can be called with
 * 'str' having value NULL and 'size' having value 0.
 * In all cases, reading input stops after encountering a newline ('\n') or EOF
 * even if 'size - 1' characters have not been read. If a newline ('\n') or EOF
 * is read then it is replaced by null character ('\0'). If there are extra
 * characters in input, they are read and discarded.
 * In all cases, 'str' or NULL is returned.
 */
char *get_input_from_stdin_and_discard_extra_characters(char *str, long size)
{

    int c = 0;
    long i = 0;

    // If size is 0 then this function will discard all input and return NULL.
    // No need to check str if size is 0.
    if (size == 0) {
        // discard all input
        while ((c = getchar()) && (c != '\n') && (c != EOF));
        return NULL;
    }

    if (!str)
        return str;

    if (size < 0)
        return NULL;

    for (i = 0; i < (size - 1); i = i + 1) {

        c = getchar();

        if ((c == '\n') || (c == EOF)) {
            str[i] = 0;
            return str;
        }

        str[i] = (char)(c);

    } // end of for loop

    str[i] = 0;

    // discard rest of input
    while ((c = getchar()) && (c != '\n') && (c != EOF));

    return str;

} // end of get_input_from_stdin_and_discard_extra_characters

Answer 1