笔试刷题-美团2018-08-02

题目描述：

/**
给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。
输入描述:
输入为两行字符串（可能包含空格），长度均小于等于50.
输出描述:
输出为一个整数，表示最长公共连续子串的长度。
输入例子1:
abcde
abgde
输出例子1:
2
*/

思路如下：

dp[i][j]表示str1以i结尾和str2以sj可以找出的这两个串的最长公共连续子列
更新过程具体见代码即可
只有在str1[i]==str2[j]时才更新
dp[i][j]=dp[i-1][j-1]+1
base case:
i==0 || j==0
且str1[i]==str2[j]
dp[i][j]==1;
下面平移了一下放下，不用麻烦初始判断i==0 j==0具体看代码
注意:
这题目可能包含空格要用getline

代码如下：

#include<stdio.h>
#include<iostream>
#include<string>
 
#define MAX_N 55
 
using namespace std;
 
int dp[MAX_N][MAX_N];
 
int main()
{
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);
    int res=0;
    for(int i=1; i<=str1.size(); i++){
        for(int j=1; j<=str2.size(); j++){
            if(str1[i-1]==str2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            res=max(res, dp[i][j]);
        }
    }
    printf("%d", res);
    return 0;
}