c语言找出两个字符串的相同子串

在C语言中，找出两个字符串的相同子串可以使用KMP（Knuth-Morris-Pratt）算法或Rabin-Karp（Rabin-Scott）算法。这里我们重点讲解KMP算法，因为它相对简单且适合查找字符串间的最长公共前缀。

KMP 算法的主要思想是通过构建一个部分匹配表（也叫失配表），预先计算好模式串中每个位置发生错误时需要跳过的字符数，避免了不必要的回溯操作。

以下是KMP算法的基本步骤：

1. **创建部分匹配表**：对于模式串S，从前往后扫描，如果当前字符和目标字符相等，则继续；如果不等，记录下当前位置i和上次匹配失败的位置j，然后在表中查找j的新值，即S[j+1]对应的索引，使得S[i-j..i] == S[j+1..j+i]。如果没有这样的新值，就将j设置为新的值。

2. **主循环**：对目标串T进行遍历，每次尝试匹配模式串的下一个字符。如果匹配成功，继续；如果不成功，根据部分匹配表更新目标指针。

3. **找到公共子串**：当模式串和目标串完全匹配时，返回它们的起始位置，即为相同子串的起始点。如果无法完全匹配，返回最长的部分公共前缀。

下面是一个简单的C语言版本的KMP函数示例：

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

void compute_lps(char* pat, int len, int lps[]) {
    int i = 0, j = -1;
    while (i < len) {
        if (pat[i] == pat[j + 1]) {
            lps[i++] = ++j;
        } else {
            if (j == -1)
                lps[i++] = 0;
            else
                j = lps[j];
        }
    }
}

int kmp_search(char* txt, char* pat) {
    int m = strlen(pat), n = strlen(txt);
    int lps[m], i = 0, j = 0;

    compute_lps(pat, m, lps);

    while (i < n && j < m) {
        if (txt[i] == pat[j])
            i++, j++;
        else if (j != 0)
            j = lps[j - 1];
        else
            i++;
    }

    if (j == m)
        return i - m; // 返回子串起始位置

    return -1;
}

int main() {
    char str1[] = "ABCBDAB";
    char str2[] = "BDCAB";
    int pos = kmp_search(str1, str2);
    if (pos != -1)
        printf("最长公共子串是 '%s'，起始位置 %d\n", &str1[pos], pos);
    else
        printf("没有相同的子串。\n");
    return 0;
}