当前位置:网站首页>(POJ - 1458) common subsequence (longest common subsequence)
(POJ - 1458) common subsequence (longest common subsequence)
2022-07-06 16:23:00 【AC__ dream】
Topic link :http://poj.org/problem?id=1458
The question : Give you two strings at a time , Find the length of the longest common subsequence
This is a template problem for finding the longest common subsequence , This model is classic , Let me introduce the solution of this problem
This problem is solved by dynamic programming , set up dp[i][j] Represents the first string i Characters and the first... Of the second string j The length of the longest common subsequence of characters , Now let's start to analyze the state transition
If s1[i]==s2[j] that dp[i][j]=dp[i-1][j-1]+1( The default is... In the first string i Characters and the second string Of the j Match characters )
If not satisfied s1[i]==s2[j], that dp[i][j]=max(dp[i-1][j],dp[i-1][j]), How to understand this equation , Imagine , If dp[i][j] The last bit in the longest public string of the contained result corresponds to s1[m] and s2[n], Then it must be satisfied m!=i perhaps n!=j, because s1[i]!=s2[j], Now if n!=j Well , Then there must be dp[i][j-1]=dp[i][j], Because at this time, the second string j Characters do not belong to the characters in the longest common subsequence , So there is dp[i][j-1]=dp[i][j], Similarly, you can get if m!=i, At this time there is dp[i-1][j]=dp[i][j], therefore dp[i][j]=max(dp[i-1][j],dp[i-1][j])
At this time, some students may have doubts , Why to be s1[i]==s2[j] when dp[i][j]=dp[i-1][j-1]+1, Don't dp[i-1][j-1]+1>=max(dp[i-1][j],dp[i-1][j]), In fact, this inequality is true , According to our definition of state, we can get dp[i-1][j-1]+1>=dp[i-1][j] as well as dp[i-1][j-1]+1>=dp[i][j-1], Therefore, the above inequality will hold
The implementation is relatively simple , Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1003;
char a[N],b[N];
int dp[N][N];//dp[i][j] Express a Middle front of string i Characters and b Middle front of string j The number of elements in the longest common subsequence of characters
int main()
{
while(scanf("%s%s",a+1,b+1)!=EOF)
{
int lena=strlen(a+1),lenb=strlen(b+1);
for(int i=1;i<=lena;i++)
for(int j=1;j<=lenb;j++)
{
if(a[i]==b[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
printf("%d\n",dp[lena][lenb]);
}
return 0;
}
边栏推荐
- Problem - 922D、Robot Vacuum Cleaner - Codeforces
- Programmers, what are your skills in code writing?
- 树莓派4B64位系统安装miniconda(折腾了几天终于解决)
- JS call camera
- 409. Longest palindrome
- Problem - 922D、Robot Vacuum Cleaner - Codeforces
- Problem - 1646C. Factorials and Powers of Two - Codeforces
- 1605. Sum the feasible matrix for a given row and column
- 快速转 TypeScript 指南
- Frida hook so layer, protobuf data analysis
猜你喜欢
Codeforces Round #802(Div. 2)A~D
Determine the Photo Position
The concept of C language array
Maximum product (greedy)
921. Minimum additions to make parentheses valid
Sword finger offer II 019 Delete at most one character to get a palindrome
Write web games in C language
Codeforces Round #801 (Div. 2)A~C
力扣:第81场双周赛
QT按钮点击切换QLineEdit焦点(含代码)
随机推荐
C language must memorize code Encyclopedia
Codeforces round 797 (Div. 3) no f
Borg maze (bfs+ minimum spanning tree) (problem solving report)
OneForAll安装使用
F - birthday cake (Shandong race)
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
921. Minimum additions to make parentheses valid
QT realizes window topping, topping state switching, and multi window topping priority relationship
Acwing - game 55 of the week
Advancedinstaller installation package custom action open file
1005. Maximized array sum after K negations
Maximum product (greedy)
Configuration du cadre flask loguru log Library
Codeforces Round #799 (Div. 4)A~H
875. Leetcode, a banana lover
Li Kou - 298th weekly match
Determine the Photo Position
Bidirectional linked list - all operations
409. Longest palindrome
JS call camera