int process(string& str1, string& str2, int i, int j) {//以i，j为结尾下标
  if (dp[i][j])//如果该位置的答案已经被求解出来，那么直接返回答案
  {
    return dp[i][j];
  }
  if (i == 0 || j == 0) {//分析各种边界条件（当两字符串其中一个或者都只剩下一个字符时，分析两者相等与不等的情况），找递归出口
    if (str1[i] == str2[j]) {
      dp[i][j] = 1;
    }
    return dp[i][j];
  }
  int p3 = 0, p1 = 0, p2 = 0;
  if (str1[i] == str2[j]) {
    p1 = process(str1, str2, i, j - 1);//找该位置的最大值
    p2 = process(str1, str2, i - 1, j);
    p3 = process(str1, str2, i - 1, j - 1) + 1;
  }
  else
  {
    process(str1, str2, i, j - 1);
    process(str1, str2, i - 1, j);
  }
  dp[i][j] = max(p1, max(p2, p3));//其实如果不求具体值，递归里面就可以去找最大值，但是因为要找i，j下标，所以最后去遍历dp表
  return dp[i][j];
}
int longestCommonSubsequence(string text1, string text2) {
  dp.resize(text1.size(), vector<int>(text2.size())); flag.resize(text1.size(), vector<int>(text2.size()));
  int ana = process(text1, text2, text1.size() - 1, text2.size() - 1);
  return ana;
}
int main() {
longestCommonSubsequence("WOAINIyishengyishi", "WOAINI") ;
  for (vector<int>t : dp) {
    for (int i : t)cout << i << " ";
    cout << endl;
  }
  return 0;
}

int main() {
  string s1 = "yongwangzhiqian", s2 = "yong"; int len1 = s1.size(), len2 = s2.size();
  vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1));
  int max = 0, path1 = 0, path2 = 0;
  for (int i = 1; i <= len1; i++) {
    for (int j = 1; j <= len2; j++) {
      if (s1[i - 1] == s2[j - 1])
      {//int t=max(dp[i][j-1],dp[i-1][j]);如果直接改是这样的，但是优化一下就是如下了
        dp[i][j] = dp[i - 1][j - 1] + 1;// dp[i][j] = max(dp[i - 1][j - 1] + 1,t);
        if (dp[i][j] > max) {
          max = dp[i][j];
          path1 = i - 1; path2 = j - 1;//得到下标
        }
      }
    }
  }
  cout << max << " " << path1 << " " << path2 << endl; string ans((s1.begin() + path1 + 1 - max), (s1.begin() + path1 + 1));
  cout << ans << endl;//左闭右开，末尾取不到，所以加1
  return 0;
}