假设以顺序存储结构表示串，试设计一个算法，求串s和串t的一个最长公共子串，并分析算法的时间复杂度

### 回答1：
这道题要求我们设计一个算法，根据给定的顺序存储结构表显示字符串，求两个字符串s和t的一个最长公共子串，并分析算法的时间复杂度。

对于这个问题，可以使用动态规划算法来解决。先构造一个二维矩阵，行数为s的长度加1，列数为t的长度加1。矩阵中的每个元素表示以该位置作为结尾的最长公共子串的长度。

然后，进行如下动态规划转移：如果s[i-1]等于t[j-1]，则matrix[i][j] = matrix[i-1][j-1]+1；否则，matrix[i][j] = 0。转移完成后，最长公共子串的长度为矩阵中最大的元素值，同时可以通过倒推过程得到最长公共子串。

该算法的时间复杂度为O(n^2)，其中n为字符串的长度。

### 回答2：
对于这道问题，我们可以采用动态规划的思想来解决。具体地，我们定义一个二维数组dp，其中dp[i][j]表示以字符串s的第i个字符和字符串t的第j个字符为结尾的最长公共子串的长度。

我们可以根据以下的状态转移方程来更新dp数组：

当s[i]==t[j]时，dp[i][j] = dp[i-1][j-1]+1。

当s[i]!=t[j]时，dp[i][j]=0。

我们可以在每次更新dp数组时，判断dp[i][j]是否大于当前最长公共子串的长度，如果是，则更新最长公共子串。

具体地，我们可以从dp数组中找到最大的值，然后从dp[i][j]开始往左推导，得到最长公共子串。

那么如何判断dp[i][j]是否大于当前最长公共子串的长度呢？我们可以定义两个变量：maxlen表示当前已经求出的最长公共子串的长度，以及start表示最长公共子串在字符串s中的起始位置。我们在每次更新dp数组时，判断dp[i][j]是否大于maxlen，如果是，则更新maxlen和start。

时间复杂度分析：

因为每次遍历dp数组都需要O(1)时间，所以总时间复杂度为O(n^2)，其中n为字符串的长度。因此，该算法的时间复杂度为O(n^2)。

代码如下：

def find_lcs(s: str, t: str) -> str:
    n1 = len(s)
    n2 = len(t)
    dp = [[0 for _ in range(n2)] for _ in range(n1)]
    maxlen = 0
    start = 0
    for i in range(n1):
        for j in range(n2):
            if s[i] == t[j]:
                if i==0 or j==0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > maxlen:
                    maxlen = dp[i][j]
                    start = i - maxlen + 1
            else:
                dp[i][j] = 0
    return s[start:start+maxlen]

### 回答3：
本题的最长公共子串问题可以用动态规划来解决，具体步骤如下：

1. 定义状态：设dp[i][j]表示以串s中第i个字符和串t中第j个字符为结尾的最长公共子串长度，若s[i] ≠ t[j]，则dp[i][j] = 0。

2. 状态转移：若s[i] = t[j]，则dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0。

3. 最大值判断：在dp数组中取最大值，即max(dp[i][j])，记下此时的i和j。

4. 输出结果：从dp[i][j]开始向左依次扫描，直到dp[i][j] = 0，依次输出即为最长公共子串。

对于时间复杂度，最坏情况下每个状态都需要计算一次，所以总时间复杂度为O(mn)，其中m和n分别为两个串的长度。