* 最长公共子序列

---

名词解释：

sadstory与adminsorry的最长公共子序列是adsory，长度为6。

dp的值代表在该(i,j)串中已匹配的个数。

---

走过来的路径：

对A与B两个字符串，取A[i]，B[j]为例：

1. 若A[i]==B[j]：

A[i]与B[j]可以组成一对新的公共子序列，所以dp[i][j]==dp[i-1][j-1]+1

2. 若A[i]!=B[j]：

i或者j中至少有一个不能成为公共子序列的成员，因为i!=j，所以i必须跟j之前的配对，那么j就凉了，所以dp[i][j]==dp[i][j-1]，或者dp[i][j]==dp[i-1][j]，看谁更大（配对多）就选哪个。

但是如果出现相等的话怎么办？-->走两边都能得出正确的解

image.png

求过来的路径：

image.png

如果a[i]，b[j]处字符相等，打印点，x--，y--

if(a[x-1]==b[y-1]){
  cout<<a[x-1]<<">>";
  x--;
  y--;
}

如果字符不相等，则选择dp大的一边走，如果dp[x-1][y]与dp[x][y-1]相等，则会有两种走法进而演化出多种不同的可能，如果考这个的话可以用DFS递归解。

else{
  if(dp[x-1][y]>dp[x][y-1]){
    x--;
  }
  else{
    y--;
  }
}

遍历所有可能子序列的解法:

void tracefullpath(int i,int j,vector<int>vv){
  if(i>=1&&j>=1){
    if(a[i-1]==b[j-1]){
      //cout<<"-->";
      vv.push_back(i-1);
      tracefullpath(i-1,j-1,vv);
    }
    else if(dp[i-1][j]==dp[i][j-1]){
        tracefullpath(i-1,j,vv);
        tracefullpath(i,j-1,vv);
    }
    else if(dp[i-1][j]>dp[i][j-1]){
      tracefullpath(i-1,j,vv);
    }
    else{
      tracefullpath(i,j-1,vv);
    }
  }
  else{
    print(vv);
    return;
  }
}

---

测试数据：

abcfbc abfcab
programming contest
abcd mnp

4
2
0

示例代码：

#include <bits/stdc++.h>
using namespace std;
#define N 1000
int points,edges;
char a[N];
char b[N];
// i是从1到n的，所以字符串匹配是a[i-1]而不是a[i]
// char数组从0开始，dp从1开始，要注意
int dp[N][N]={0};
// 根据原操作逆向出原路径。
void chase_path(int x,int y){
  cout<<"path: ";
  while(y>=1&&x>=1){
    if(a[x-1]==b[y-1]){
      cout<<a[x-1]<<">>";
      x--;
      y--;
    }
    else{
      if(dp[x-1][y]>dp[x][y-1]){
        x--;
      }
      else{
        y--;
      }
    }
  }
}
int main() {
  int i,j;
  scanf("%s %s",&a,&b);
  int len_a=strlen(a);
  int len_b=strlen(b);
  // 获取字符串长度

  for(i=1;i<len_a+1;i++){
    for(j=1;j<len_b+1;j++){
      if(a[i-1]==b[j-1]){
        // char数组从0开始，所以要a/b要-1
        dp[i][j]=dp[i-1][j-1]+1;
        // 在ij未放入的时候最优基础上+1
      }
      else{
        dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        // 如果i，j放了跟没放一样，那么就跟dp[i][j-1]/dp[i-1][j]一样了
      }
    }
  }
  cout<<"\nCommon Length:"<<dp[len_a][len_b];
  return 0;
}