2021年1月22日20:48:41LCS问题

  

   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

       key to LCS problem
     
    
   

    

     

    
    

     

       bug1:当输入s1,s2长度不一致时，答案运行不出来 
     
    
   

    

     

    
    

     

       2020-1-22
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	
      char s1[
      100]={
      0},s2[
      100]={
      0};
     
    
   

    

     

    
    

     
	
      int x,y,max=
      0;
     
    
   

    

     

    
    

     
	
      printf(
      "please input s1:");
     
    
   

    

     

    
    

     

      	gets(s1);
     
    
   

    

     

    
    

     
	
      printf(
      "please input s2:");
     
    
   

    

     

    
    

     

      	gets(s2);
     
    
   

    

     

    
    

     
	
      printf(
      "waiting.....\n");
     
    
   

    

     

    
    

     

      	x=
      strlen(s1)+
      1;
      //col 列 
     
    
   

    

     

    
    

     

      	y=
      strlen(s2)+
      1;
      //line行 
     
    
   

    

     

    
    

     
	
      int **p=(
      int**)
      malloc(y*
      sizeof(
      int*));
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<y;i++)
     
    
   

    

     

    
    

     

      		p[i]=(
      int*)
      malloc(x*
      sizeof(
      int));
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<x;i++)
     
    
   

    

     

    
    

     

      		p[
      0][i]=
      0;
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<y;i++)
     
    
   

    

     

    
    

     

      		p[i][
      0]=
      0;
     
    
   

    

     

    
    

     
	
      for(
      int i=
      1;i<x;i++)
      //x->s1
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		
      for(
      int j=
      1;j<y;j++)
      //y->s2
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

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

    

     

    
    

     

      				p[i][j]=p[i
      -1][j
      -1]+
      1;
     
    
   

    

     

    
    

     
			
      else
     
    
   

    

     

    
    

     

      				p[i][j]=(p[i
      -1][j]>p[i][j
      -1])?p[i
      -1][j]:p[i][j
      -1];
     
    
   

    

     

    
    

     

      			max=(max>p[i][j])?max:p[i][j];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<y;i++)
     
    
   

    

     

    
    

     
		
      free(p[i]);
     
    
   

    

     

    
    

     
	
      free(p);
     
    
   

    

     

    
    

     
	
      printf(
      "the max length is: %d\n",max);
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

       improved version 滚动数组优化 
     
    
   

    

     

    
    

     

      */		
     
    
   

    

     

    
    

     
	
      int** q=(
      int**)
      malloc(
      sizeof(
      int*)*
      2);
     
    
   

    

     

    
    

     
	
      int Max=
      0;
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<
      2;i++)
     
    
   

    

     

    
    

     

      		q[i]=(
      int*)
      malloc(
      sizeof(
      int)*y);
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<
      2;i++)
     
    
   

    

     

    
    

     

      		q[i][
      0]=
      0;
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<y;i++)
     
    
   

    

     

    
    

     

      		q[
      0][i]=
      0;
     
    
   

    

     

    
    

     
	
      for(
      int i=
      1;i<x;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

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

    

     

    
    

     

      		{
     
    
   

    

     

    
    

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

    

     

    
    

     

      				q[i%
      2][j]=q[(i
      -1)%
      2][j
      -1]+
      1;
     
    
   

    

     

    
    

     
			
      else
     
    
   

    

     

    
    

     

      				q[i%
      2][j]=(q[(i
      -1)%
      2][j]>q[i%
      2][j
      -1])?q[(i
      -1)%
      2][j]:q[i%
      2][j
      -1];
     
    
   

    

     

    
    

     

      			Max=(Max>q[i%
      2][j])?Max:q[i%
      2][j];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      for(
      int i=
      0;i<
      2;i++)
     
    
   

    

     

    
    

     
		
      free(q[i]);
     
    
   

    

     

    
    

     
	
      free(q);
     
    
   

    

     

    
    

     
	
      printf(
      "the Max length is: %d\n",Max);
     
    
   

    

     

    
    

     
	
      return 
      0;
     
    
   

    

     

    
    

     

       }