首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最长公共子串

最长公共子串

作者头像
喜欢ctrl的cxk
发布2019-11-08 10:41:41
7420
发布2019-11-08 10:41:41
举报
文章被收录于专栏:Don的成长史Don的成长史

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/90575252

题目描述:

有两个字符串(可能包含空格),请找出其中最长的公共连续子串,输出其长度。

输入描述:

给定两行字符串(长度在1000以内)

输出描述:

输出这两个字符串的最长公共连续子串的长度。

输入样例:

abcde
bcd

输出样例:

3

解题思路:

一个简单的动态规划问题。设ans为最长公共连续子串的长度,用cnt来临时记录公共连续子串的长度。当str1和str2的字符相等就循环累加,不断更新ans最后输出即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str1,str2;
    getline(cin,str1);
    getline(cin,str2);
    int ans = 0, cnt = 0;    //ans为最大公共连续子串的长度
    for(int i = 0; i < str1.length(); i++)
    {
        for(int j = 0; j < str2.length(); j++)
        {
            cnt = 0;
            int k = i;
            while(str1[k] == str2[j])  //相等就循环累加
            {
                cnt++;
                k++;
                j++;
            }
            ans = max(ans,cnt);   //ans取最大值
        }
    }
    cout << ans << endl;    
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-05-26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 输入描述:
  • 输出描述:
  • 输入样例:
  • 输出样例:
  • 解题思路:
  • AC代码:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档