美图 2018校招 后端研发工程师在线考试-编程题二

题目 最长公共子串

描述

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

输入

给定两行字符串

输出

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

Example

Input

abcde
bcd

Output

3

题解

动态规划

• 定义 len(i,j) 为串 1 在位置 i 处结尾与串 2 在位置 j 出结尾的公共子串的长度
• 动态更新最大长度
• 状态转移方程

len(I,j) = |-> 0  (str1[i]!=str2[i])
           |-> len(i-1,j-1)+1  (str1[i]==str2[i])

#include <bits/stdc++.h>

using namespace std;

char str1[2005],str2[2005];
int commLen[2005];

int main()
{
    while(cin>>str1>>str2)
    {
        int len1=strlen(str1),len2=strlen(str2),maxLen=0;;
        memset(commLen,0,sizeof commLen);
        for(int i=1;i<=len1;++i)
        {
            for(int j=len2;j>0;--j)
            {
                if(str1[i-1]==str2[j-1])
                {
                    commLen[j]=commLen[j-1]+1;
                    maxLen=max(maxLen,commLen[j]);
                }
                else
                    commLen[i][j]=0;
            }
        }
        cout<<maxLen<<endl;
    }
}