Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

BCSTR - Xâu con chung dài nhất

 

Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.
Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.

Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.

Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.

 

Input

Dòng 1: chứa xâu A

Dòng 2: chứa xâu B

 

Output

Chỉ gồm một dòng ghi độ dài xâu C tìm được

Example

Input:
abc1def2ghi3
abcdefghi123

Output:
10
Submit solution!
Được gửi lên bởi:adm
Ngày:2016-07-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
hide comments
2020-12-02 08:22:46
#include<bits/stdc++.h>
using namespace std;
long long m,n,f[1005][1005];
string a,b;
void doc()
{
getline(cin,a);
getline(cin,b);
n=a.size()-1;
m=b.size()-1;
}
void xuly()
{
if(a[0]==b[0])f[0][0]=1;
else f[0][0]=0;
for (int j=1;j<=m;j++)
if(a[0]==b[j]) f[0][j]=1;
else f[0][j]=f[0][j-1];
for (int i=1;i<=n;i++)
if(b[0]==a[i]) f[i][0]=1;
else f[i][0]=f[i-1][0];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i]==b[j]) f[i][j]=1+f[i-1][j-1];
else f[i][j]=max (f[i-1][j],f[i][j-1]);
cout<<f[n][m];
}
from nguyên tín 10 Tin THPT chuyên Lê Khiết
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.