extra.cpp

这是动态规划中

#include<iostream.h>
#include<stdio.h>
#include<string.h>

void LCS(char *str1,char *str2);

  void main()
 {  char arr1[100],arr2[100];
   //input the arbitrary string;
   cout<<"input the arbitrary two strings:"<<endl;
        gets(arr1); 
        gets(arr2);
    LCS(arr1,arr2);  // utilize the function
 }
  void LCS(char *str1, char *str2) // definite the function
 { 
  char samestring[100]=" ";
  char label[100][100]={' '};
 int len1= strlen(str1),len2=strlen(str2),i=0,j=0,h=0;
 int  array[100][100]; //store the table
   //init the fist column and row array
  for(i=0;i<=len1;i++)
	  array[i][0]=0;
  for(j=0;j<=len2;j++)
	  array[0][j]=0;

  for (i=1;i<=len1;i++)  // begin the dynamic-programming
    	for(j=1;j<=len2;j++)
           if(str1[i-1]==str2[j-1])
		   {   array[i][j]=array[i-1][j-1]+1;
               label[i][j]='\S' ;  //set label information about the common string
		   }
       
               else if (array[i-1][j]>array[i][j-1])
			   {  array[i][j]=array[i-1][j];
                  label[i][j]='\G';
			   }
			   else {array[i][j]=array[i][j-1];
			           label[i][j]='\L';
			   }

    i=len1, j=len2;	
			   
  while(1)
  {
	  if(i==0||j==0)
		 break;
     switch (label[i][j])
	 {
	 case'\S': {samestring[h++]=str1[i-1]; // distract the common string
				   i=i-1,j=j-1;
			   break;}
	 case'\G':i=i-1; break;
	 case'\L':j=j-1; break;
	 default:break;
	 }
     
  /*switch(label[i][j])
	   {
		   case'\S':  {
			      samestring[h++]=str1[i];
		          i++;
				  j++;
		          break;}
		   case'\G': i++; break;
		   case'\L': j++; break;
	   default : break;
	   
	   }
	  
	   
     if(label[i][j]=='\S')
	  { 
		  samestring[h++]=str1[i];
		  i++;
		  j++;
	  
	  }

      
    
	     if(label[i][j]=='\G')
		   i++;
		    if(label[i][j]=='\L')
				j++; 
     if(i>len1||j>len2)

              break;		    
  */
  }
  //output the table value;
  cout<<endl<<"output the table values:"<<endl;
  for (i=0;i<=len1;i++)
  {
	  for(j=0;j<=len2;j++)
         cout<<array[i][j];
         cout<<endl;
  }
    
  cout <<"output  the longest common subsequence string:  ";
     for (i=h-1;i>=0;i--)
	    	 cout<<samestring[i];
			 cout<<endl;
  cout<<"the length of LCS: ";
		   cout<<array[len1][len2]<<endl;

 
  }