专栏首页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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【PAT乙级】结绳

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

    喜欢ctrl的cxk
  • Python 位运算

    程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

    喜欢ctrl的cxk
  • 【PAT乙级】A + B和C

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

    喜欢ctrl的cxk
  • Q67 Add Binary

    Given two binary strings, return their sum (also a binary string). For example, ...

    echobingo
  • 将2N个整数分成两组,每组有N个数,并且满足,这两组的差的绝对值最小。

    有人提议说模拟 背包算法....背包算法大概可以表示为给你一个包,然后你让这个包尽可能的有价值,对应的就是,这个包的大小就是 sum(c)/2 (这样就可以让他...

    forxtz
  • 你写的字符(串)忽略大小写比较函数真的严谨吗?

    有时我们比较两个字符串时不考虑它们是大写还是小写;举个例子,在这种情况下我们认为“BanAna”和“baNaNA”是等价的。

    xiaoxi666
  • Python 社区有了新治理模式

    随着 Python 之父 Guido van Rossum 逐步卸任 BDFL,Python(CPython)的未来之路牵动了万千开发者的心。没了首领,Pyth...

    Debian中国
  • 详解:Java的重载方法与示例

    方法重载是一项功能,如果一个类的参数列表不同,则它允许一个类拥有多个具有相同名称的方法。它类似于Java中的构造函数重载,它允许一个类具有多个具有不同参数列表的...

    陈哈哈
  • 直接插入排序 希尔排序

    【1 2 3 4  7 8 9】 6 插入3, 3和 9 交换,3和8交换, 3和7交换, 3和4交换

    用户2965768
  • android 自定义gallerey并实现预览功能

    自从Gallery被谷歌废弃以后,Google推荐使用ViewPager和HorizontalScrollView来实现Gallery的效果。的确Horizon...

    xiangzhihong

扫码关注云+社区

领取腾讯云代金券