C语言采用顺序结构存储串,设计一个算法,求串s和串t的一个最长公共子串

C语言可以使用动态规划(Dynamic Programming)的策略来寻找两个字符串`s`和`t`的最长公共子串(LCS - Longest Common Substring)。这里是一个简单的基于二维数组的算法：

1. 定义一个大小为`(m+1) x (n+1)`的二维字符数组`dp`，其中`m`和`n`分别是`s`和`t`的长度。这个数组的每个元素`dp[i][j]`表示字符串`s`的前i个字符和`t`的前j个字符之间的最长公共子串的长度。

2. 初始化第一行和第一列，因为单个字符不可能是它们之间共同的子串，所以`dp[0][j] = dp[i][0] = 0`，表示没有匹配。

3. 遍历`dp`矩阵，对于每个位置`(i, j)`，如果`s[i]`等于`t[j]`，则`dp[i][j] = dp[i-1][j-1] + 1`，因为它找到了一个新的匹配字符，最长公共子串长度加一。如果`s[i]`不等于`t[j]`，则`dp[i][j] = 0`，意味着当前字符无法构成新的公共子串。

4. 当遍历结束后，`dp[m][n]`即为最长公共子串的长度。为了获取实际的子串，从`s`的末尾开始，向前回溯`dp`矩阵，记录下每个匹配的位置，直到找到`dp[m][n]`步长的子串。

下面是伪代码形式的实现：

function longest_common_substring(s, t):
    m = length(s)
    n = length(t)
    dp = array(m+1, n+1, 0)

    max_len = 0
    end_index = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_index = i
            else:
                dp[i][j] = 0

    return s[end_index-max_len:end_index]

# 示例：s = "ABCDGH", t = "AEDFHR"
lcs = longest_common_substring("ABCDGH", "AEDFHR")