题目：

提取两个字符串中最大的公共子串，并输入（先考虑求出最大子串）

动态规划思路：

1、先简单后复杂都是解题的常规思路，首先想到两个字符串都很小的情况，比如字符串长度为1，然后考虑复杂的情况。如果两个字符串都在变，思考起来肯定很乱，那我们先固定一个，比如x串的长度固定为1，y串长度未知，可能为1到n。

//场景一
String x = "a";
String y = "acabcaefabc"

假如情况如上，那么最大子串，结果是在y串索引为0，2，5，8长度为1的串。不管y串有多长，这个求解过程就是把y串中每个字符与a比较（因为x的子串就只有a一个）。

2、现在加入a不固定了，它长度可能是1，2，3.......n中的一个，那我们该怎么求，假设如下场景二

//场景二
String x = "ab";
String y = "acabcaefabb"

那么这个情况怎么求呢？x串的子串有a，ab，b三种情况，如果是穷举，那么就太耗性能了，我们可以结合上一个场景考虑。

a串和b串的求解方法用场景一的就可以，这里就不考虑。

ab串才是关键，因为它是x中拿的一个子串，所以只要去y串找，就知道是不是公共子串。方式呢？其实只需要在y串中找b字符，找到了看一下它前面是不是a,如果是那么ab是公共子串。那关键来了，怎么知道b的位置前面是不是a呢？

   //动态推导
	//假设在场景一的时候给y串找到位置打上一个标记，1代表找到了a，同时也表示现在的最大子串是1
   a-c-a-b-c-a-e-f-a-b-b
   1-0-1-0-0-1-0-0-1-0-0 
   
 	//先找到b
   a-c-a-b-c-a-e-f-a-b-b
   0-0-0-1-0-0-0-0-0-1-1
 	//在找到的b时，去加上前一个位置的标记值，如果为2，那么说明前一个位置是a
     1-0-1-0-0-1-0-0-1-0-0 
+    0-0-0-1-0-0-0-0-0-1-1
=	 1-0-1-2-0-1-0-0-1-2-1
	//其实就是找b,找到b时打个标记1，这个标记需要加上前一个位置上的值（这个值是找a时打上的标记值）
	//如果还有c,就是找c,找到c后打个标记1，然后加上前一个位置的值（这个值是找b时打上的标记）

3、状态转移方程

假设f[i][j]表示x串的前i个字符，和y串的前j个字符，之间的最大公共子串长度值。

那么根据前面分析的，找不到，那不管，f[i][j] = 0；也就不处理（数组初始化为0）；

找的到，那么它就是 1 加上找前一个字符时的标记值。这个值其实最大长度。

状态转移方程就是：f[i][j] = f[i-1][j-1]

例如刚才找b时，b = 1,表示前面一个字符不是a,如果子串包括这个b的话，子串最大长度只能是1；

b = 2,表示前一个字符为a,如果子串包括当前这个b的话，子串最大是2。

 for(int i = 1;i < x.length; i++){
            for(int j = 1;j < y.length; j++){
                if(x[i] == y[j]){
				  
                    num[i][j] = 1 + num[i -1][j- 1];
				  
				   //下面这步是收集最大长度值，只有大于上一次存的最大值才处理
                    if(num[i][j]>max){
                        max = num[i][j];
                        start = i-max;
                    }
                }
            }
        }