2021秋季《数据结构》_EOJ 1039.最长公共子序列

题目

单点时限: 2.0 sec
内存限制: 256 MB
给你 2 个字符串（可能包括数字以及标点），长度不超过50124 ，请你求出最长的连续的公共子序列。

思路

方法1

构造len1*len2的二元二维数组，a[i][j]表示s1[i]和s2[j]是否相等，通过遍历对角线寻找最长连续1串得到结果。

方法2

二维数组dp，a[i][j]表示s1的前i个字符和s2的前j个字符组成的字符串的最长连续公共子序列长度，状态转移方程为a[i][j]= s1[i]==s2[j]? a[i-1][j-1]+1:0

以上两种方法都会爆内存

方法3

由于题目不要求输出策略，且数组状态更新仅与上一行有关，于是考虑滚动数组

代码

方法1

#include<bits/stdc++.h>
using namespace std;int main()
{
    string s1, s2;cin>>s1>>s2;int len1 = s1.length();int len2 = s2.length();// 申请二维数组并初始化int **a = new int *[len1];for(int i = 0; i < len1; i++){
    a[i] = new int[len2];memset(a[i], 0, sizeof(int)*len2);}// 比对二维数组for(int i = 0; i < len1; i++){
    char nowCh1 = s1[i];for(int j = 0; j < len2; j++){
    char nowCh2 = s2[j];if(nowCh1==nowCh2)a[i][j] = 1;}}// for(int j = 0; j < len2; j++)// {
    // for(int i = 0; i < len1; i++)// {
    // cout<<a[i][j]<<' ';// }// cout<<endl;// }// 遍历对角线int LCCS = 0;for(int b = 1-len1; b <= len2-1; b++){
    // cout<<"b="<<b<<endl;int tmpLCCS = 0;int tmpRecLCCS = 0;for(int i = 0; i<len1; i++){
    int j = i+b;if(j>=0 && j<len2){
    if(a[i][j]==1)tmpRecLCCS++;else if(a[i][j]==0){
    if(tmpRecLCCS>tmpLCCS)tmpLCCS = tmpRecLCCS;tmpRecLCCS = 0;}}}if(tmpRecLCCS>tmpLCCS)tmpLCCS = tmpRecLCCS;// cout<<"tmpLCCS="<<tmpLCCS<<endl;if(tmpLCCS>LCCS) LCCS = tmpLCCS;tmpLCCS = 0;}cout<<LCCS<<endl;for(int i = 0; i < len1; i++){
    delete[] a[i];}delete[] a;system("pause");return 0;
}

方法2

#include<bits/stdc++.h>
using namespace std;int main()
{
    string s1, s2;cin>>s1>>s2;int len1 = s1.length();int len2 = s2.length();// 申请二维数组并初始化int **a = new int *[len1];for(int i = 0; i < len1; i++){
    a[i] = new int[len2];memset(a[i], 0, sizeof(int)*len2);}int res = 0;for(int i = 0; i < len1; i++){
    for(int j = 0; j < len2; j++){
    if(i==0||j==0){
    if(s1[i]==s2[j]) a[i][j] = 1;else a[i][j] = 0; }else{
    a[i][j] = s1[i]==s2[j]? a[i-1][j-1]+1:0;}if(a[i][j]>res) res = a[i][j];}}cout<<res<<endl;for(int i = 0; i < len1; i++){
    delete[] a[i];}delete[] a;system("pause");return 0;
}

方法3

注意从后往前遍历，避免覆盖

#include<bits/stdc++.h>
using namespace std;int main()
{
    string s1, s2;cin>>s1>>s2;int len1 = s1.length();int len2 = s2.length();int* a = new int[len1+1];memset(a, 0, sizeof(int)*len1);int res = 0;for(int j = 0; j < len2; j++){
    for(int i = len1-1; i >= 0; i--){
    if(s1[i]==s2[j])a[i+1] = a[i]+1;else a[i+1] = 0;if(res<a[i+1]) res = a[i+1];}// cout<<s2[j]<<' ';// for(int i = 1; i <= len1; i++)// cout<<a[i]<<' ';// cout<<endl;}cout<<res<<endl;system("pause");return 0;
}