c++最长公共子序列
时间: 2023-11-18 18:52:00 浏览: 34
最长公共子序列问题是指给定两个字符串s1和s2,求它们的最长公共子序列(LCS)的长度。
解决该问题可以采用动态规划的思想,具体过程如下:
1. 定义状态:dp[i][j]表示s1的前i个字符与s2的前j个字符的LCS长度。
2. 初始化状态:dp[j]=dp[i]=0,表示空串与任意字符串的LCS长度都为0。
3. 状态转移方程:
当s1[i-1] = s2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1;
当s1[i-1] ≠ s2[j-1]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
4. 最终结果:dp[m][n],其中m和n分别为s1和s2的长度。
以下是C++代码实现:
```
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i=1; i<=m; ++i) {
for(int j=1; j<=n; ++j) {
if(text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
```