最大公共子序列c++

概念
- 基本的概念
递归
- 算法
- 代码
- 优化
- map基础
- 优化代码

概念

基本的概念

子序列：由原序列中若干个元素组成，元素可以不连续，但和原序列的顺序一致。
最长公共子序列：一个序列即是甲序列的子序列，也是乙序列的子序列，则该序列称为为甲和乙的公共子序列。长度最长的公共子序列，即最长公共子序列。
两个序列的公共子序列不一定是唯一的。

递归

算法

lcs(s1,s2)表示：串s1和s2的最大公共子序列长度，并返回其值
先比较两个串的首字符，如果相等，递归实现lcs(s1+1,s2+1)+1即可
如果不相等，则返回lcs(s1,s2+1),lcs(s1+1,s2)中较大的。
由上图可以看出，最大公共子序列的值为3，但不唯一，abc,bca的长度都是3。

代码

#include<iostream>
using namespace std;
int lcs(const char* a,const char* b){
	if(*a == 0 || *b==0) 
		return 0;
	if(*a==*b)
		return lcs(a+1,b+1)+1;
	return max(lcs(a,b+1),lcs(a+1,b));
} 
int main(){
	cout<<lcs("axbcydz","xayybcxd")<<endl;
	return 0;
}

优化

递归的优点是思路简单，但是耗费资源，重复递归调用。
如下图，草拟相同圈处是重复递归计算的地方，如果串长些，那么这种重计划量将非常繁巨，以致电脑无法计算。
所以需改进，改进的方法是，相同的串相互比较求最大公共子序列时，就将其存储起来，放入map，下次再遇到相同的2个串比较时，直调从map中取值。
因为加入了参递，所以递归函数需要增参。
递归函数f(m,s1,k1,s2,k2)
参数说明。m是map记录着2个子串的最大公共子序列，s1、s2是子串，k1、k2是从子串的哪个下标开始比较。
即只需以k1\k2的位置作为键，递归函数的返回值(最大公共子序列的长度)作为值，存入map中即可。

map基础

头文件，#include
map存取键-值对，查找速度快。键需能比较，此应用中键为2个int，int。
stl中的pair可以保存<int,int>。定义为

#include <utility> // 包含 std::pair 的头文件
#include <iostream>
using namespace std;
int main() {
    // 直接初始化 std::pair
    pair<int, double> pair1(1, 3.14);
    // 使用 std::make_pair 函数初始化 std::pair
    pair<string, int> pair2 = make_pair("Kimi", 2024);
    // 访问 pair 的元素
    cout << "pair1: " << pair1.first << ", " << pair1.second << endl;
    cout << "pair2: " << pair2.first << ", " << pair2.second << endl;
    // 修改 pair 的元素
    pair1.first = 2;
    pair2.second = 2025;

    return 0;
}

map中统计键pair出现的次数

#include <iostream>
#include <map>
using namespace std;
int main() {
    map<pair<int, int>, string> map;
    // 插入键值对
    map[make_pair(1, 2)] = "12";
    map[make_pair(1, 2)] = "21"; // 注意：这实际上是更新了键(1, 2)的值
    map[make_pair(3, 4)] = "34";
    // 要查找的键
    pair<int, int> key_to_count(1, 2);
    // 使用count查找键
    size_t count = map.count(key_to_count);
    cout << "The key (" << key_to_count.first << ", " << key_to_count.second << ") appears " << count << " times." << endl;
    return 0;
}

map中查找pair对

#include <iostream>
#include <map>
#include <utility> // For std::pair
using namespace std;
int main() {
    // 创建一个map，键为pair<int, int>，值为string
    map<pair<int, int>, string> map;
    // 插入键值对
    map[make_pair(1, 2)] = "12";
    map[make_pair(3, 4)] = "34";
    // 要查找的键
    pair<int, int> key_to_find(1, 2);
    // 使用find查找键
    auto it = map.find(key_to_find);
    if (it != map.end()) {
        cout << "Found key: (" << it->first.first << ", " << it->first.second << ") with value: " << it->second << endl;
    } else {
        cout << "Key not found." << endl;
    }
    return 0;
}

map遍历

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    // 插入一些键值对
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";
    // 使用 begin() 获取指向第一个元素的迭代器
    auto it = myMap.begin();
    // 检查迭代器是否不是 end()（即检查 map 是否不为空）
    if (it != myMap.end()) {
        // 使用迭代器访问并打印第一个元素
        std::cout << "The first key-value is: " << it->first << " => " << it->second << std::endl;
    }
    // 使用范围基于的 for 循环遍历 map
    for (const auto& pair : myMap) {
        std::cout << pair.first << " => " << pair.second << '\n';
    }
    return 0;
}

自定义pair对

#include <iostream>
#include <map>
using namespace std;
// 定义一个结构体作为键
struct IntPair {
    int first;
    int second;
    // 必须定义比较运算符，以便map可以比较键
    bool operator<(const IntPair& other) const {
        return first < other.first || (first == other.first && second < other.second);
    }
};
int main() {
    // 定义一个map，键为IntPair，值为string
    std::map<IntPair, std::string> map;
    // 插入键值对
    map[{1, 2}] = "12";
    map[{3, 4}] = "34";
    // 访问键值对
    for (const auto& kv : map) {
        cout << "Key: (" << kv.first.first << ", " << kv.first.second << ") Value: " << kv.second << endl;
    }

    return 0;
}

优化代码

#include<iostream>
#include<map>
using namespace std;
int f(map<pair<int,int>,int>& m,const char* s1,int k1,const char* s2,int k2){
	if(s1[k1]==0 || s2[k2]==0)
		return 0;
	pair<int,int> p(k1,k2); //构建子串pair对 
	if(m.count(p))//查找map中是否有相应的子串最大公共子序列值
		return m[p];//如果存储了，则直接返回子序列长度，不必再递归计算 
	//map中未记录，才计算最大公共子序列的长度 
	if(s1[k1]==s2[k2]){ 
		int t=f(m,s1,k1+1,s2,k2+1)+1;
		m[make_pair(k1,k2)]=t;
		return t;
	}
	int t1=f(m,s1,k1+1,s2,k2);
	int t2=f(m,s1,k1,s2,k2+1);
	int t=max(t1,t2);
	m[make_pair(k1,k2)]=t;
	return t;
}
int lcs(const char* s1,const char* s2){
//	map<int,int>ma;
	map<pair<int,int>,int> m;//定义一个map，键为pair<int,int>,值为int。 
	return f(m,s1,0,s2,0);
} 
int main(){
	cout<<lcs("axbcydz","xayybcxd")<<endl;
	cout<<lcs("axbcydzaxbcydz","xayybcxdaaaaabbbxxccc")<<endl;
	return 0;
}