【挑战程序设计竞赛】 最长公共子序列

发表于

描述
给定字符串S和T，求最长公共子串的长度
假设S = "kabc",T = "abcd" 则长度应该为3

思路
比较两个字符串的每一个字符，可能会产生以下情况：

  1. S[i+1] = T[j+1] –> dp[i+1][j+1] = dp[i][j]+1
  2. S[i+1] = T[j] –> dp[i+1][j+1] = dp[i+1][j]
  3. S[i] = T[j+1] –> dp[i+1][j+1] = dp[i][j+1]
    第二种情况和第三种情况均没有产生新的值，只是传递而已。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxCommonString(const string & S, const string & T) {
    int lenS = S.size();
    int lenT = T.size();
    vector<vector<int> >dp(lenS + 1, vector<int>(lenT + 1, 0));
    for (int i = 0; i < lenS; i++) {
        for (int j = 0; j < lenT; j++) {
            if (S[i] == T[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            }
            else {
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }
    return dp[lenS][lenT];
}