题库 软件开发 题目列表 以下代码是计算最长公共子串的一个算法,试分析它的...
单选题
以下代码是计算最长公共子串的一个算法,试分析它的时间复杂度是多少?
int findLongest(string A, string B)
{
    int n=A.size();
    int m=B.size();
    //相当于生成一个二维数组int dp[n][m];
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int max = -1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (A[i] == B[j])
            {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                if (dp[i + 1][j + 1] > max)
                {
                    max = dp[i + 1][j + 1];
                }
            }
        }
    }
    return max;
}


A.

O(n)

B.

O(m)

C.

O(n+m)

D.

O(n*m)

题目信息
校招真题
-
正确率
0
评论
17
点击