11-伪代码详解

4.3.4　伪代码详解

（1）最长公共子序列求解函数

首先计算两个字符串的长度，然后从i=1开始，s₁[0]与s₂中的每一个字符比较。

如果当前字符相同，则公共子序列的长度为c[i−1][j−1]+1，并记录最优策略来源b[i][j] = 1。

如果当前字符不相同，则公共子序列的长度为c[i][j−1]和c[i−1][j]中的最大值，如果c[i][j−1]c[i−1][j]，则最优策略来源b[i][j]=2；如果c[i][j−1]<c[i−1][j]，则最优策略来源b[i][j]=3。直到i> len1时，算法结束，这时c[len1][len2]就是我们要的最长公共序列长度。

Void LCSL()
{
    int I,j;
    for(I = 1;I <= len1;i++)    //控制s1序列
      for(j = 1;j <= len2;j++)  //控制s2序列
      {
        if(s1[i-1]==s2[j-1])    //字符下标从0开始
        {   //如果当前字符相同，则公共子序列的长度为该字符前的最长公共序列+1
            c[i][j] = c[i-1][j-1]+1;
            b[i][j] = 1;
        }
        else
        {
            if(c[i][j-1]>=c[i-1][j]) //两者找最大值，并记录最优策略来源
            {
                  c[i][j] = c[i][j-1];
                  b[i][j] = 2;
            }
            else
            {
                  c[i][j] = c[i-1][j];
                  b[i][j] = 3;
            }
        }
     }
}

（2）最优解输出函数

输出最优解仍然使用倒推法。因为我们在求最长公共子序列长度c[i][j]的过程中，用b[i][j]记录了c[i][j]的来源，那么就可以根据b[i][j]数组倒推最优解。

如果b[i][j]=1，说明s1[i−1]=s2[j−1]，那么我们就可以递归输出print(i−1，j−1)；然后输出s1[i−1]。

如果b[i][j]=2，说明s1[i−1]≠s2[j−1]且最优解来源于c[i][j]=c[i][j−1]，递归输出print(i，j−1)。

如果b[i][j]=3，说明s1[i−1]≠s2[j−1]且最优解来源于c[i][j]=c[i−1][j]，递归输出print(i−1，j)。当i==0||j==0时，递归结束。

Void print(int I, int j)//根据记录下来的信息构造最长公共子序列（从b[i][j]开始递推）
{
    if(i==0 || j==0) return;
    if(b[i][j]==1)
    {
        print(i-1,j-1);
        cout<<s1[i-1];
    }
    else if(b[i][j]==2)
              print(I,j-1);
          else print(i-1,j);
}