#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
	string str1, str2;
	while (getline(cin, str1),getline(cin,str2))
	{
		int max = 0;
		vector<vector<int>> dp(str1.size(),vector<int>(str2.size(),0));
		for (int i = 0; i < str1.size(); i++)
		{
			for (int j = 0; j < str2.size(); j++)
			{
				if (str1[i] == str2[j])
					if (i == 0 || j == 0)
						dp[i][j] = 1;
					else
						dp[i][j] = dp[i - 1][j - 1] + 1;					
				if (dp[i][j]>max)
					max = dp[i][j];
			}
		}
		cout << max << endl;
	}
	return 0;
}

  #include<iostream>

	#include<string>



	#include<vector>



	using namespace std;



	



	int solve(string& A, string& B)



	{



	int res = 0,n = B.size();



	vector<vector<int> > dp(A.size() + 1);



	for(int i = 0;i < A.size() + 1;i++)



	dp[i].resize(n + 1);



	for(int i = 1;i <= A.size();i++)



	{



	for(int j =  1; j <= n; j++)



	{



	if(A[i - 1] == B[j - 1])



	res = max(res,dp[i][j] = dp[i - 1][j - 1] + 1);



	}



	}



	return res;



	}



	



	int main()



	{



	string A, B;



	getline(cin, A);



	getline(cin, B);



	cout << solve(A, B) << endl;



	return0;



	}

 int LongestSubstr(string A,string B)
{     vector<int> dp(A.size() + 1);   
      int res = 0;      for (int i = 1; i <= A.size(); i++)    
      {       
          for (int j = 1; j <= B.size(); j++)        
          {         
              if (A[i - 1] == B[i - 1])      
              res = max(res, dp[j] = dp[j - 1] + 1);       
          }    
       }    
     return res;
}

int LongestSubstr(string A,string B)
{     int res = 0, len = 0, flag = 0;    
      for (int i = 1; i <= A.size(); i++)  
      {     
           for (int j = 1; j <= B.size(); j++)  
           {            
               if (A[i - 1] == B[j - 1])                  
      res = max(res, len += 1), flag = 1;   
           }       
            if (!flag) len = 0;   
           flag = 0;    
     }    
     return res;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1;
        while((str1 = br.readLine()) != null){
            String str2 = br.readLine();
            System.out.println(solve(str1, str2));
        }
    }
    
    private static int solve(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        // dp[i][j]是字符串str1.substring(0, i)和str2.substring(0, j)的最大公共子串的长度
        int[][] dp = new int[m + 1][n + 1];
        int result = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = str1.charAt(i - 1) == str2.charAt(j - 1)? dp[i - 1][j - 1] + 1: 0;
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }
}

//dp二维转一维，做法类似于第二题思路
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.nextLine();
		String b = sc.nextLine();
		int[] dp=new int[b.length()+1];
		for(int i=0;i<dp.length;i++) {
			dp[i]=0;
		}
		int res=0,index=1;
		for(int i=0;i<a.length();i++) {
			for(int j=index;j<dp.length;j++) {
				if(a.charAt(i)==b.charAt(j-1)) {
					dp[j]+=dp[j-1]+1;
					res=Math.max(res, dp[j]);
					index=++j;
					break;
				}else{
					for(int k=1;k<b.length();k++) {
						dp[k]=0;
					}
					index=1;
				}
			}
		}
		
		System.out.println(res);
	}
}

// 一个串在另一个串上从尾部进入直到串头滑出为止，时间复杂度为O（N^2）的.

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    char str1[51],str2[51];
    int lmax,l;
    while(fgets(str1,51,stdin)!=NULL){
        fgets(str2,51,stdin);
        int l1=0;
        int l2=0;
        while(str1[l1]!='\n'&&str1[l1]!='\0'){l1++;}
        while(str2[l2]!='\n'&&str2[l2]!='\0'){l2++;}
        lmax=0;
        // from front to back
        for(int i=0;i<l1;i++){
            int ii=i;
            int cnt=0;
            int size(i+1,l2);
            l=0;
            for(int j=l2-1;cnt<size;j--,ii--,cnt++){
                if(str1[ii]==str2[j])l+=1;
                else l=0;
                if(l>lmax)lmax=l;
            }
        }
        // from back to front
        for(int i=0;i<l2;i++){
            int ii=i;
            int cnt=0;
            int size(i+1,l1);
            l=0;
            for(int j=l1-1;cnt<size;j--,ii--,cnt++){
                if(str2[ii]==str1[j])l+=1;
                else l=0;
                if(l>lmax)lmax=l;
            }
        }
        // output result
        cout<<lmax<<endl;
    }
    return 0;
}
添加笔记

思路：
准备一个N+1 * N+1大小的二维数组dp，置0。
dp[i][j]代表s1的0-i位置与s2的0-j位置中连续公共子串的最大长度。
则有：
    如果s1[i] == s2[j]，dp[i][j] = dp[i-1][j-1] + 1;
    否则，dp[i][j] = 0;
记录最大长度即可。

C++源码：
#include <iostream>
#include <string.h>
using namespace std;

#define MAX_LENGTH 50

int main(){
	string s1, s2;

	getline(cin, s1);
	getline(cin, s2);

	int len1 = s1.size();
	int len2 = s2.size();

	int maxLength = 0;
	int dp[MAX_LENGTH+1][MAX_LENGTH+1];
	memset(dp, 0, sizeof(dp));

	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] > maxLength)
					maxLength = dp[i][j];
			}else{
				dp[i][j] = 0;
			}
		}
	}
	cout << maxLength << endl;
	
	return 0;
}

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	string s1, s2;
	while (getline(cin, s1), getline(cin, s2)){
		int l1 = s1.size();
		int l2 = s2.size();
		vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));
		int result = 0;
		for (int i = 1; i <= l1; i++){
			for (int j = 1; j <= l2; j++){
				if (s1[i - 1] == s2[j - 1]){
					dp[i][j] = dp[i - 1][j - 1] + 1;
					result = max(dp[i][j], result);
				}
				else{
					dp[i][j] = 0;
				}
			}
		}
		cout << result << endl;
	}
	return 0;
}

import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String s1 = sc.nextLine();
			String s2 = sc.nextLine();
			int l1 = s1.length();
			int l2 = s2.length();
			int result = 0;
			int[][] dp = new int[l1 + 1][l2 + 1];
			for (int i = 1; i <= l1; i++){
				for (int j = 1; j <= l2; j++){
					if (s1.charAt(i - 1) == s2.charAt(j - 1)){
						dp[i][j] = dp[i - 1][j - 1] + 1;
						result = Math.max(dp[i][j], result);
					}
					else{
						dp[i][j] = 0;
					}	
				}
			}
			System.out.println(result);
		}
		sc.close();
	}
}

    var str1 = readline();
    var str2 = readline();
    var arr = [];
    for (var i = 0; i < str1.length; i++) {
        arr[i] = [];
        for (var j = 0; j < str2.length; j++) {
            arr[[i]][j] = 0;
        }
    }
    var max = 0;
    for(var i=0;i<str1.length;i++){
        for (var j = 0; j < str2.length; j++) {
            if (str1[i] == str2[j]) {
                if(i==0 || j==0){
                    arr[i][j] = 1;
                }else{
                    arr[i][j] = arr[i-1][j-1] + 1;
                }
            }
            if(arr[i][j]>max){
                max = arr[i][j];
            }
        }
    }
    print(max);

	#include<iostream>



	#include<string>



	using namespace std;



	 



	#define N 51



	int main()



	{



	    string s1, s2;



	    getline(cin, s1);



	    getline(cin, s2);



	    intdp[N][N]={0};



	    if(!s1.length() || !s2.length())



	        return -1;



	    int maxLength = 0;



	    for(int i=0; i<s1.length(); ++i)



	    {



	        for(int j=0; j<s2.length(); ++j)



	        {



	            if(s2[j]==s1[i])



	                dp[i+1][j+1] = dp[i][j]+1;



	            else



	                dp[i+1][j+1] = 0;



	            if(maxLength<dp[i+1][j+1])



	                maxLength = dp[i+1][j+1];



	        }



	    }



	    cout<<maxLength<<endl;



	    return 0;



	}

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[55][55],Max=0,i,j;
int main(){
    string x,y;
    getline(cin,x);getline(cin,y);
    for(i=1;i<=x.length();i++)
        for(j=1;j<=y.length();j++){
            if(x[i-1]==y[j-1]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=0;
            Max=max(Max,dp[i][j]);
        }
    printf("%d\n",Max);
}

	#按照小的字符串顺序和逆序各遍历一遍取最大值



	str1 = raw_input()



	str2 = raw_input()



	iflen(str1) > len(str2):



	    str1,str2 = str2,str1



	res = 0



	start = 0



	fori in range(1,len(str1)+1):



	    ifstr1[start:i] in str2:



	        res = max(res,i-start)



	    else:



	        start = i



	end = len(str1)



	fori in range(len(str1)-1,0,-1):



	    ifstr1[i:end] in str2:



	        res = max(res,end - i)



	    else:



	        end = i



	print res

一个超级简单超级短的方法并且全过
s1 = input()
s2 = input()
if len(s1) < len(s2):
    ss = s1 # 较短的字符串
    ls = s2 # 较长的字符串
else:
    ss = s2
    ls = s1
re = 0
for i in range(len(ss)):
    j = 0
    while j <= i:
        if ss[j:i + 1] in ls:
            re = max(re, i - j + 1)
        j += 1
print(re)

美团2017 JAVA

[编程题]大富翁游戏
[编程题]拼凑钱币
[编程题]最大矩形面积
[编程题]最长公共连续子串

这道题其实我以前做过，但是这次碰到却一直想不起来，非常难受，交卷后看评论里的动态规划就立马明白了，下面是代码。
stream特性是真的好用，一旦拥有，爱不释手。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    int max=0;
    public static void main(String[] args){
        Main s=new Main();
        Scanner in=new Scanner(System.in);
        String s1=in.nextLine();
        String s2=in.nextLine();
        int len1=s1.length();
        int len2=s2.length();
        int dp[]=new int[len2+1];
        for (int i=1;i<=len1;i++){
            for(int j=len2;j>=1;j--){
                if (s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[j]=dp[j-1]+1;
                }else{
                    dp[j]=0;
                }
            }
            int cur = Arrays.stream(dp).max().getAsInt();
            if (cur>s.max) s.max=cur;
        }
        System.out.println(s.max);
    }
}