HJ65 查找两个字符串a,b中的最长公共子串

这篇具有很好参考价值的文章主要介绍了HJ65 查找两个字符串a,b中的最长公共子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Powered by:NEFU AB-IN

Link

HJ65 查找两个字符串a,b中的最长公共子串

  • 题意

    查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。

  • 思路

    参考这篇我之前写的文章 blog,使用字符串哈希和二分实现的

    这里用dp实现:

    • f[i][j]表示 1~ai,1~bj且ai,bj为结尾的所有公共子串
    • 属性:最长公共串长度
    • 转移:
      • 如果ai==bj且ai,bj都是字母,则f[i][j]=f[i-1][j-1]+1
      • 其他,f[i][j]=0

    优化:类似01背包问题,考虑i: 1~alen枚举,j: blen~1倒序枚举,即可优化一维

    这里引文要输出较短串中最先出现,所以要先辨别出短的串文章来源地址https://www.toymoban.com/news/detail-702802.html

  • 代码

    #include <any>
    #include <bits/stdc++.h>
    #include <utility>
    using namespace std;
    #define int long long
    #undef int
    
    #define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \
        ios::sync_with_stdio(false);                                                                                       \
        cin.tie(nullptr);                                                                                                  \
        cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;
    
    const int N = 1e5 + 10, INF = 0x3f3f3f3f;
    
    int dp[N];
    
    signed main()
    {
        //freopen("Tests/input_1.txt", "r", stdin);
        IOS;
    
        string a, b;
        cin >> a >> b;
    
        int n = SZ(a), m = SZ(b);
    
        if (n > m){
            swap(a, b);
            swap(n, m);
        }    
    
        a = " " + a;
        b = " " + b;
    
        int mx = 0, end = -1;
        for(int i = 1; i <= n; ++ i){
            for(int j = m; j >= 1; -- j){
                if(a[i] == b[j]){
                    dp[j] = dp[j - 1] + 1;
                    if(dp[j] > mx){
                        mx = dp[j];
                        end = i;
                    }
                }
                else dp[j] = 0;
            }
        }
    
        cout << a.substr(end - mx + 1, mx);
    
    
        return 0;
    }
    

到了这里,关于HJ65 查找两个字符串a,b中的最长公共子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣热门算法题 349. 两个数组的交集,387. 字符串中的第一个唯一字符,394. 字符串解码

    349. 两个数组的交集,387. 字符串中的第一个唯一字符,394. 字符串解码,每题做详细思路梳理,配套PythonJava双语代码, 2024.04.02 可通过leetcode所有测试用例。 目录 349. 两个数组的交集 解题思路 完整代码 Python Java 387. 字符串中的第一个唯一字符 解题思路 完整代码 Python Java

    2024年04月08日
    浏览(43)
  • 2023-08-15 LeetCode每日一题(字符串中的查找与替换)

    点击跳转到题目位置 你会得到一个字符串 s (索引从 0 开始),你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出:indices, sources, targets。 要完成第 i 个替换操作: 检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。 如果没有出现, 什么

    2024年02月12日
    浏览(42)
  • 华为OD机试 - 提取字符串中的最长合法简单数学表达式(Java & JS & Python & C)

    题目描述 提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 0 。 简单数学表达式只能包含以下内容: 0-9数字,符号+-* 说明: 所有数字,计算结果都不超过long 如果有多个长度一样的,请返回第一个表达式的结果 数学表达

    2024年02月02日
    浏览(50)
  • 提取字符串中的最长数学表达式并计算(67%用例) C卷(Java&&Python&&C++&&Node.js&&C语言)

    提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回0 简单数学表达式只能包含以下内容 0-9数字,符号+-* 说明: 1.所有数字,计算结果都不超过long 2.如果有多个长度一样的,请返回第一个表达式的结果 3.数学表达式,必须是最

    2024年04月13日
    浏览(37)
  • C语言学习:输入一行字符串,输出字符串中最长的单词。

    输入一行字符,编写一个函数,将此字符串中最长的单词输出。 代码示例如下: 一、输出字符串中第一个最长单词 测试结果:  二、输出字符串中所有最长单词 评论区指出上述程序不能输出同样最长的两个单词,修改后该程序能输出所有最长单词,即如果有多个同样最长的

    2024年02月05日
    浏览(57)
  • 题目:2609.最长平衡子字符串

    ​​ 题目来源:         leetcode题目,网址:2609. 最长平衡子字符串 - 力扣(LeetCode) 解题思路:        按要求进行模拟即可。 解题代码: 总结:         注意,当 1 的数量小于等于 0 的数量,可以组成一个长度为 1 的数量两倍的平衡字符串。         无官方题解。

    2024年02月12日
    浏览(35)
  • 【算法训练-字符串 三】最长公共子串、最长公共子序列

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【】,使用【】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两个地方都出现过才做

    2024年02月09日
    浏览(38)
  • 【算法题】2745. 构造最长的新字符串

    给你三个整数 x ,y 和 z 。 这三个整数表示你有 x 个 “AA” 字符串,y 个 “BB” 字符串,和 z 个 “AB” 字符串。你需要选择这些字符串中的部分字符串(可以全部选择也可以一个都不选择),将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 “AAA” 或者

    2024年02月12日
    浏览(50)
  • 【字符串 简单】LeetCode 14. 最长公共前缀 Java

    我的思路: 给字符串数组按照字符串的长度从长到短排序,因为最长公共前缀最长的话,也只能是字符串数组中最短的那一个字符串 设置一个index变量,表示当前正在检查字符数组中所有字符串的index位置 循环遍历字符串数组n遍,n也就是最长公共前缀的长度 其他思路,方法

    2024年02月15日
    浏览(40)
  • 剑指Offer48.最长不含重复字符的子字符串 C++

    请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1 : 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2 : 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为

    2024年02月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包