最长公共子序列、最长公共子串的输出

淩亂°似流年 2023-03-12 07:28 55阅读 0赞

**1、最长公共子序列：**  
举个例子，s1=“abcfde”，s2=“bcde”。那么s1与s2的最长公共子序列就是"bcde"，注意**不要求连续**。该问题是典型的动态规划问题。（i,j）从0开始，那么递推关系很容易找到，就是：(maxLen(i,j))表示s1字符串左边i个字符构成的子串与s2左边j个字符构成的子串的最长公共子序列长度，下同)

if(s1[i-1]==s2[j-1]) { 
        maxLen(i,j)=maxLen(i-1,j-1) + 1;
    }else { 
        maxLen(i,j)=max(maxLen(i,j-1),maxLen(i-1,j));
    }

最长公共子序列及输出：

#include<bits/stdc++.h>
    using namespace std;
    
    const int MAX=1e3;
    int flag[MAX+5][MAX+5];
    char s1[MAX+5],s2[MAX+5];
    int dp[MAX+5][MAX+5];
    
    void LCS() { 
        memset(dp,0,sizeof(dp));
        memset(flag,0,sizeof(flag));
        for(int i=1;i<=strlen(s1);i++) { 
            for(int j=1;j<=strlen(s2);j++) { 
                if(s1[i-1]==s2[j-1]) { 
                	dp[i][j]=dp[i-1][j-1]+1,flag[i][j]=0;
    			}else if(dp[i-1][j]>=dp[i][j-1]) { 
    				dp[i][j]=dp[i-1][j],flag[i][j]=1;
    			}else { 
    				dp[i][j]=dp[i][j-1],flag[i][j]=-1;
    			}      
            }
        }
    }
    void PrintLCS(int i,int j) { 
        if(i==0||j==0) { 
        	return ;
    	}
        if(flag[i][j]==0) { 
            PrintLCS(i-1,j-1);
            cout<<s1[i-1];
        }
        else if(flag[i][j]==1) { 
        	PrintLCS(i-1,j);
    	}else { 
    		PrintLCS(i,j-1);
    	}      
    }
    int main() { 
        while(cin>>s1>>s2) { 
            LCS();  
            PrintLCS(strlen(s1),strlen(s2));
            cout<<endl;
        }
    }

2、最长公共子串  
最长公共子串与上述最长公共子序列不一样，最长公共子串要求连续。  
例如s1=“asdfddsx”，s2=“asssdfed”，那么s1与s2的最长公共子串是：“as”。最长公共子串的输出比上面最长公共子序列简单，因为后者一定是连续的，我们只要保存最后一个两字符串字符相等的位置index，以及最长公共子串的长度length，然后从index位置往回倒推index个字符即可。  
递推关系为：

if(s1[i-1]==s2[j-1]) { 
        maxlen(i,j)=maxLen(i-1,j-1)+1
    }

求最长公共子串并输出：

#include<bits/stdc++.h>
    using namespace std;
    
    string str1,str2;
    int dp[1002][1002],ans=1,index;
    
    int main() { 
    	cin>>str1>>str2;
    	memset(dp,0,sizeof(dp));
    	int x=str1.length(),y=str2.length();
    	for(int i=1;i<=x;i++) { 
    		for(int j=1;j<=y;j++) { 
    			if(str1[i-1]==str2[j-1]) { 
    				dp[i][j]=dp[i-1][j-1]+1;
    				if(ans<=dp[i][j]) { 
    					ans=dp[i][j];   //公共子串长度 
    					index=i;    //保留当前位置 
    				}
    			}
    		}
    	}
    	cout<<ans<<endl;
    	for(int i=index-ans;i<index;i++) { 
    		cout<<str1[i];
    	}
    	return 0;
    }