//autor:baker //time:25/5/06 //email:baker1203@sina.com /*    求两个字符串的最长公共子序列。 X的一个子序列是相应于X下标序列{1, 2, …, m}的一个子序列，求解两个序列的所有子序列中长度最大的，例如输入：pear, peach输出：pea。   分析：    次题可用动态规划算法解决。 首先定义一个二维数组：A【】【】； A[i][j] M G D D G 0 1 0 0 g 0 1 0 0 d 0 0 2 1 d 0 0 0 3   如上，A[I][J]表示在此字符以前互相匹配的字符数目，当MAX=MAX(MAX,A[I][J])为最大时，即求得最大匹配子串。 当STR1[I]=STR2[J]时，A[I][J]=A[I-1][J-1]+1，即左上方最大匹配字符数目加一。 当MAX为最大时，记录下当前扫描STR1的位置为TAG （2）源代码如下： */ #include"iostream" #include"conio.h" #include"string" using namespace std;   void maxstring(string str1,string str2) {      int max=0,tag,i,j;      int length1=str1.size();      int length2=str2.size();      int a[length1+1][length2+1];               for(i=0;i<=length1;i++)         for(j=0;j<=length2;j++)         a[i][j]=0;              for(i=1;i<=length1;i++)         for(j=1;j<=length2;j++)           if(str1[i]==str2[j])           {             a[i][j]=a[i-1][j-1]+1;             if(max<a[i][j])             {              max=a[i][j];              tag=i;             }           }      if(max==0){cout<<"no found same string!";return ;}      cout<<"output the max same string:";      for(i=tag-max;i<=tag;i++)                      cout<<str1[i];             cout<<endl<<"the length is:"<<max<<endl;   }   int main() {     string str1,str2;     cout<<"enter the two strings!"<<endl;     cout<<"string 1:";     cin>>str1;     cout<<"string 2:";     cin>>str2;     maxstring(str1,str2);     getch();     return 0; }     /*（4）程序截图：         */

评论