LCS——最长公共子序列“连续”与“不连续”版本

分手后的思念是犯贱 2022-12-28 14:16 129阅读 0赞

### 文章目录 ###

*  最长公共子序列（非连续）
 *   *  状态转移方程
     *  核心代码
 *  最长公共子序列（连续）
 *   *  状态转移方程
     *  核心代码

--------------------

# 最长公共子序列（非连续） #

这一类LCS问题是最常见的。

给定两个字符串a,b，求a,b的最长公共子序列的长度

## 状态转移方程 ##

![1][]

## 核心代码 ##

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    int LCS_Len(string a, string b)
    {
        
        int dp[1000][1000];
        for(int i = 1; i <= a.size(); i++)
            for(int j = 1; j <= b.size(); j++){
        
                if(a[i - 1] == b[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[a.size()][b.size()];
    }

--------------------

# 最长公共子序列（连续） #

给定两个字符串a,b，求a,b的最长公共**连续**子序列的长度

这里要保证最长公共子序列一定要是**连续的**。

## 状态转移方程 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

最后在dp数组中寻找一次最大值，这个值就是最大长度

## 核心代码 ##

#include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
    
    int Similar(string a, string b)
    {
        
    	int dp[100][100];
    
    	for(int i = 1; i <= a.size(); i++){
        
    		for(int j = 1; j <= b.size(); j++){
        
    			if(a[i - 1] == b[j - 1])
    				dp[i][j] = dp[i - 1][j - 1] + 1;
    			else{
        
    				dp[i][j] = 0;
    			}
    		}
    	}
    	
    	int max = -1;
    	for(int i = 1; i <= a.size(); i++)
    		for(int j = 1; j <= b.size(); j++)
    			if(max <= dp[i][j])
    				max = dp[i][j];
    
    	return max;
    }

[1]: /images/20221120/c94cf942280a447c9a0328206aba86e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/875bc083ae814a56a0afb13d27dccf2f.png