最大公共子序列c++

🕗 发布于 2024-10-17 14:00 最大公共子序列c++

最大公共子序列c++

概念
- 基本的概念
递归

概念

基本的概念

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

递归

算法

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;
}

原文地址：https://blog.csdn.net/qq_37755459/article/details/142983498

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Unity Vision Pro 保姆级开发教程- 打开开发者选项，XCode WiFi 无线调试发布
下一篇：linux系统账号安全应该如何设置

Spring MVC实现高效文件上传及优化案例
基于SSM实现springmvc文件上传功能
阅读更多2024-10-17
CTFHUB技能树之HTTP协议——响应包源代码
点击“开始”没有抓取到报文，先看看网页源代码是什么情况。居然直接给出flag了，不知道这题的意义何在。是个贪吃蛇小游戏，看不出来有什么特别的地方。
阅读更多2024-10-17
嵌入式面试——FreeRTOS篇（九）内存管理
FreeRTOS内存管理介绍：在使用 FreeRTOS 创建任务、队列、信号量等对象的时，一般都提供了两种方法：•动态方法创建：自动地从 FreeRTOS 管理的内存堆中申请创建对象所需的内存，并且
阅读更多2024-10-17
基于遥感技术的碳储量、碳收支、碳循环等多领域监测与模拟实践技术应用
卫星遥感具有客观、连续、稳定、大范围、重复观测的优点，已成为监测全球碳盘查不可或缺的技术手段，卫星遥感也正在成为新一代、国际认可的全球碳核查方法。本次目的就是梳理碳中和与碳达峰对卫星遥感的现实需求，
阅读更多2024-10-17
旋转花键材质及运用场景
旋转花键的材质有很多种，其材质选择是一个涉及多方面因素的重要决策，‌主要取决于应用场景的具体要求，包括设备的运行环境、负载大小、运行速度以及所需的耐磨性和耐腐蚀性等因素。
阅读更多2024-10-17
记bean对象之间的转换Orika使用（二）
A对象属性值转换到B对象，然后B再转换到A两个对象中的属性名不同的处理方法集合对象映射、对象中包含对象的映射
阅读更多2024-10-17
传输层协议UDP详解
传输层协议 ———— UDP，一篇即懂
阅读更多2024-10-17
2018年计算机网络408真题解析
协议是数据传输服务，的数据传输服务，的数据连接服务。和使用。而使用的是。TCP/IP应用层协议中，各个协议使用的传输层服务依次如下图所示：答案选。
阅读更多2024-10-17
OpenCV人脸检测与识别：构建智能识别系统
OpenCV进行简单的人脸检测与识别。我们通过读取并预处理图像、准备训练数据、训练人脸识别模型、进行预测以及显示结果等步骤，实现了基本的人脸识别功能。
阅读更多2024-10-17
Bug剖析
•所有的Bug报告有以下的基本要求：•标题。要简略。•指派。谁来处理这个问题。•重现步骤。问题再次出现的相关步骤。•优先级别。问题的紧迫性与重要性。•严重程度。问题所产生的后果。•解决方
阅读更多2024-10-17

最大公共子序列c++

最大公共子序列c++

概念

基本的概念

递归

算法

代码

优化

map基础

优化代码

相关文章