//得到两个任意长度字符串的公共最长子字符串，这里的子串可以不连续

/*

分析假设，如果串x,y的公共子串z,x.len=m,y.len=n,z.len=l;

如果z[l-1] = x[m-1] = y[n-1],那么z(0...l-2)也是x(0...m-2)和y(0...n-2)的最长子串

如果z[l-1] = x[m-1] ！= y[n-1],那么z(0...l-2)是x(0...m-2)和y(0...n-1)的最长子串

如果z[l-1] != x[m-1] = y[n-1],那么z(0...l-2)是x(0...m-1)和y(0...n-2)的最长子串

可以确定这是一个动态规划的问题，问题可能有多解,后期选择的时候需要比较大小

用b[i][j]表示当前位置是否为公共点用于指示构造最长序列，其中0代表命中，1代表向上，2代表向左

c[i][j]表示当前的最大公共长度

*/

#include 
     
      //#include 
      
       using namespace std;class solution{public:    int max_sub_string(string& x,string& y)    {        int i,j;        int m = x.size()+1;        int n = y.size()+1;        int** b = new int*[m-1];        int** c = new int*[m];        for(i=0;i
       
        = c[i][j-1])            {                c[i][j] = c[i-1][j];                b[i-1][j-1] = 1;            }            else            {                c[i][j] = c[i][j-1];                b[i-1][j-1] = 2;            }        }        print_route(b,x.size()-1,y.size()-1,x);        return c[m-1][n-1];    }    void print_route(int** b,int row,int col,string& x)    {        if(row==-1||col==-1)        {            return;        }        if(b[row][col]==0)        {            print_route(b,row-1,col-1,x);            cout<
        
         >a>>b)        cout<
         
          <