最長共通サブシーケンス(LCS)
入力
第1行は、測定対象データ群数を表す整数N(0次に、各データのセットの2行が、測定対象の2つの文字列になります.各文字列の長さは1000以下である.
しゅつりょく
各テストデータのセットは、最長の共通サブシーケンス長を表す整数を出力します.各グループの結果が1行を占めます.
サンプル入力
2
asdf
adfsd
123abc
abc123abc
サンプル出力
3
6
コードは次のとおりです.
もう一つの考え方:
スクロール配列の最適化:
第1行は、測定対象データ群数を表す整数N(0
しゅつりょく
各テストデータのセットは、最長の共通サブシーケンス長を表す整数を出力します.各グループの結果が1行を占めます.
サンプル入力
2
asdf
adfsd
123abc
abc123abc
サンプル出力
3
6
コードは次のとおりです.
#include<cstdio>
#include<string.h>
#define max(a, b) a > b ? a : b
int dp[1010][1010];
char str1[1010], str2[1010];
int main()
{
int n, len1, len2, i, j, len;
scanf("%d", &n);
while(n--)
{
scanf("%s%s", str1, str2);
len1 = strlen(str1);
len2 = strlen(str2);
len = max(len1, len2);
for(i = 0; i < len; ++i)
{
dp[0][i] = 0;
dp[i][0] = 0;
}
for(i = 1; i <= len1; ++i)
{
for(j = 1; j <= len2; ++j)
{
if(str1[i - 1] == str2[j - 1]) //
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
printf("%d
", dp[len1][len2]);
}
return 0;
}もう一つの考え方:
#include<iostream>
#include<string>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010][1010];
string str1, str2;
int main()
{
int n, i, j, len;
scanf("%d", &n);
while(n--)
{
cin>>str1>>str2;
str1 = "0" + str1; // ， ,
str2 = "0" + str2;
for(i = 1; i < str1.length(); ++i)
{
for(j = 1; j < str2.length(); ++j)
{
if(str1[i] == str2[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
", dp[str1.length() - 1][str2.length() - 1]);
}
return 0;
}スクロール配列の最適化:
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int main()
{
char s1[1000],s2[1000]; //
int r[1000],s[1000],L1,L2,i,j,k,t; //DP ， ，L1 L2
scanf("%d",&t);
while(t--)
{
scanf("%s%s",s1,s2);
L1=strlen(s1);L2=strlen(s2);
for(i=0;i<=L2;++i)r[i]=0;
for(i=0;i<=L1;++i)s[i]=0;
for(i=0;i<L1;++i)
{
for(j=0;j<L2;++j)
{
if(s1[i]==s2[j]) //
s[j+1]=r[j]+1;
else
s[j+1]=r[j+1]>s[j]?r[j+1]:s[j]; // ，
}
for(k=1;k<=L2;++k)
r[k]=s[k]; //
}
printf("%d
",r[L2]);
//
}
return 0;
}