xtu oj 共同的子串代码怎么写C语言

XTU Online Judge (简称XTU OJ) 提供的编程题通常涉及到算法编程，对于查找两个字符串的公共子串，你可以使用KMP（Knuth-Morris-Pratt）算法或者滑动窗口法来解决。以下是使用C语言实现KMP算法的一个简单示例：

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

// KMP表辅助函数
void compute_lps(char *pattern, int lps[], int len) {
    int index = 0;
    lps[0] = 0;

    for (int i = 1; i < len; i++) {
        if (pattern[i] == pattern[index]) {
            index++;
            lps[i] = index;
        } else {
            if (index != 0)
                index = lps[index - 1];
            else
                lps[i] = 0;
        }
    }
}

// 查找公共子串
char* find_common_substring(char* str1, char* str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    // 计算最长公共前缀
    char* lps1 = (char*)malloc(sizeof(char) * len1);
    compute_lps(str1, lps1, len1);

    // 使用LPS寻找最大公共子串
    int i = 0, j = 0;
    while (i < len1 && j < len2) {
        if (str1[i] == str2[j])
            i++, j++;
        else if (j != 0)
            j = lps1[j - 1];
        else
            i++;
    }

    // 如果找到了公共子串，返回子串；否则返回空指针
    if (i > 0)
        return &str1[i - lps1[j - 1]];
    else
        return NULL;
}

int main() {
    char str1[] = "hello world";
    char str2[] = "world is round";
    char *common = find_common_substring(str1, str2);

    if (common)
        printf("Common substring: %s\n", common);
    else
        printf("No common substring found.\n");

    free(common); // 释放内存
    return 0;
}