poj의 가장 긴 공통 서열과 가장 긴 공통 문자열
2480 단어 동적 기획poj최대 공통 하위 문자열최대 공통 하위 시퀀스
Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, x
ij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
사고방식: 제목의 뜻은 두 문자열을 정해서 그들의 가장 긴 공공 서열을 구하는 것이다. 그 중성자 서열은 연속되지 않을 수 있다.이 문제는 전형적인 동적 기획 문제로 dp[i][j]가 s1의 전 i 문자와 s2의 전 j 문자의 가장 긴 공통 서브 서열을 나타낸다. s1[i]==s2[j]일 때 dp[i+1][j+1]=dp[i][j]+1이고 같지 않으면 dp[i+1][j+1]=max{dp[j+1], dp[i+1][j]}이고 구체적인 코드는 다음과 같다.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int LCS(string s1,string s2)
{
int length1 = s1.size(),length2 = s2.size(),i,j;
vector<vector<int> > dp(length1+1);
for(i = 0;i <= length1;++i)
{
vector<int> tmp(length2+1,0);
dp[i] = tmp;
}
for(i = 0;i < length1;++i)
{
for(j = 0;j < length2;++j)
{
if(s1[i] == s2[j])dp[i+1][j+1] = dp[i][j]+1;
else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
}
}
return dp[length1][length2];
}
int main()
{
string s1,s2;
while(cin >> s1 >> s2)
{
cout << LCS(s1,s2) << endl;
}
return 0;
}최대 공통 하위 문자열
사고방식: 양자의 차이는 서브열이 연속을 요구하고 서브 서열은 연속을 필요로 하지 않기 때문에 상태 이동 방정식에서의 표현은 바로 s1[i]이다!=s2[j]시, d[i][j]=0.구체적으로 다음과 같다.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int LCS(string s1,string s2)
{
int length1 = s1.size(),length2 = s2.size(),i,j,res = 0;
vector<vector<int> > dp(2);// ， ，
for(i = 0;i < 2;++i)
{
vector<int> tmp(length2+1,0);
dp[i] = tmp;
}
for(i= 0;i < length1;++i)
{
int k = (i+1) & 1;
for(j = 0;j < length2;++j)
{
if(s1[i] == s2[j])// 0
{
dp[k][j+1] = dp[k^1][j]+1;
if(dp[k][j+1] > res)res = dp[k][j+1];
}
}
}
return res;
}
int main()
{
string s1,s2;
while(cin >> s1 >> s2)
{
cout << LCS(s1,s2) << endl;
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
