#HDU 1159 Common Subsequence

xiaoxiao2021-02-28  87

Common Subsequence

题意&分析:

对于给定的两个字符串,求最长公共子序列。直接用LCS算法,一个DP。

代码如下:

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define TEST cout<<"stop here"<<endl using namespace std; typedef long long ll; const ll mod = 1e9 + 7; int dp[1010][1010]; int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); string s1,s2; while(cin>> s1 >> s2){ memset(dp,0,sizeof(0)); int len1 = s1.size(); int len2 = s2.size();//cout<<len1<<" "<< len2<<endl; for(int i=1;s1[i-1];i++){ for(int j=1;s2[j-1];j++){ if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } cout<< dp[len1][len2] <<endl; } return 0; }

参考资料:

奇妙的LCS算法妙解 传送门

转载请注明原文地址: https://www.6miu.com/read-55093.html

最新回复(0)