题解 | 查找两个字符串a,b中的最长公共子串

//
// Created by gs on 2026/3/6.
//

// HJ65 查找两个字符串a,b中的最长公共子串

#include <stdio.h>
#include <string.h>

int main() {
    char a1[303], a2[303];
    char* s_short, *s_long;
    int i = 0, j = 0, start_index = 0, count = 0, i_count = 0, i_start_index = 0;
    int max_count = 0, max_start_index = 0;
    int i_l, i_s;
    scanf("%s", a1);
    scanf("%s", a2);

    if (strlen(a1) > strlen(a2)) {
        s_long = a1;
        s_short = a2;
    } else {
        s_long = a2;
        s_short = a1;
    }

    for (i = 0; i < strlen(s_short); i++) {
        for (j = 0; j < strlen(s_long); j++) {
            i_s = i;
            i_l = j;

            start_index = 0;
            count = 0;
            i_count = 0;
            i_start_index = 0;

            for (; s_short[i_s] != '\0' && s_long[i_l] != '\0'; i_l++, i_s++) {
                if (s_short[i_s] - s_long[i_l] == 0) {
                    if (i_count == 0 ) {
                        i_start_index = i_s;
                    }
                    i_count++;
                } else {
                    if (i_count > count) {
                        count = i_count;
                        start_index = i_start_index;
                    } else if (i_count == count) {
                        if (i_start_index < start_index) {
                            count = i_count;
                            start_index = i_start_index;
                        }
                    }
                    i_count = 0;
                    i_start_index = 0;
                }
            }
            if (i_count != 0) {
                if (i_count > count) {
                    count = i_count;
                    start_index = i_start_index;
                } else if (i_count == count) {
                    if (i_start_index < start_index) {
                        count = i_count;
                        start_index = i_start_index;
                    }
                }
            }

            if (count > max_count) {
                max_count = count;
                max_start_index = start_index;
            } else if (count == max_count) {
                if (start_index < max_start_index) {
                    max_count = count;
                    max_start_index = start_index;
                }
            }
        }
    }

    for (i = max_start_index; i < max_start_index + max_count; i++) {
        printf("%c", s_short[i]);
    }
    printf("\n");


    return 0;
}