普通网友 2021-11-11 12:33 采纳率: 42.9%
浏览 115
已结题

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

查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。
注:子串的定义:将一个字符串删去前缀和后缀(也可以不删)形成的字符串。请和“子序列”的概念分开!

本题含有多组输入数据!
数据范围:字符串长度,
进阶:时间复杂度:,空间复杂度:

img

  • 写回答

1条回答 默认 最新

  • 从善若水 5G/6G通信领域优质创作者 2021-11-11 12:34
    关注
    
    //思路:动态规划经典问题,加一个start标记即可,注意将较短子串最先出现的那个输出
    #include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    void findMaxCommonStr(string s1,string s2)
    {
        if(s1.length()>s2.length())
                swap(s1,s2);//s1用于保存较短的子串
        int len1=s1.length(),len2=s2.length();
        int maxLen=0,start=0;
        vector<vector<int> >dp(len1+1,vector<int>(len2+1,0));
        for(int i=1;i<=len1;++i)
            for(int j=1;j<=len2;++j)
            {
                if(s1[i-1]==s2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>maxLen)
                    {
                        maxLen=dp[i][j];
                        start=i-maxLen;//记录最长公共子串的起始位置
                    }
                }
            }
       cout<<s1.substr(start,maxLen)<<endl;
    }
    int main()
    {
       string s1,s2;
       while(cin>>s1>>s2)
       {
           findMaxCommonStr(s1,s2);
       }
       return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

问题事件

  • 系统已结题 11月19日
  • 已采纳回答 11月11日
  • 创建了问题 11月11日

悬赏问题

  • ¥15 点云密度大则包围盒小
  • ¥15 nginx使用nfs进行服务器的数据共享
  • ¥15 C#i编程中so-ir-192编码的字符集转码UTF8问题
  • ¥15 51嵌入式入门按键小项目
  • ¥30 海外项目,如何降低Google Map接口费用?
  • ¥15 fluentmeshing
  • ¥15 手机/平板的浏览器里如何实现类似荧光笔的效果
  • ¥15 盘古气象大模型调用(python)
  • ¥15 传人记程序做的plc 485从机程序该如何写
  • ¥15 已知手指抓握过程中掌指关节、手指各关节和指尖每一帧的坐标,用贝塞尔曲线可以拟合手指抓握的运动轨迹吗?