河北大学程序设计训练营

[TOC]

day22 最长公共子序列长度

求两个字符串的最长公共子序列长度。

输入格式:

输入长度≤100的两个字符串。

输出格式:

输出两个字符串的最长公共子序列长度。

输入样例1:

ABCBDAB
BDCABA

输出样例1:

4

输入样例2:

ABACDEF
PGHIK

输出样例2:

0

分析：

最长公共子序列(LCS)只需要保证两个字符串中字符位置一样。

两个字符串:串A和串B。已知两字符串:A0,A1…Ai…An-1 和 B0,B1…Bj…Bm-1。

有以下递推关系:
(1)当Ai = Bj时:A0,A1…Ai-1,Ai 和 B0,B1…Bj-1,Bj的LCS长度 等于 A0,A1…Ai-1 和 B0,B1…Bj-1的LCS长度+1。
(2)当Ai != Bj时:A0,A1…Ai-1,Ai 和 B0,B1…Bj-1,Bj的LCS长度 等于 max(A0,A1…Ai-1 和 B0,B1…Bj-1,Bj的LCS长度 , A0,A1…Ai-1,Ai 和 B0,B1…Bj-1的LCS长度)。

DP思路：

1、数组array[i][j]用来表示 两个字符串A0,A1…Ai…An-1 和 B0,B1…Bj…Bm-1的LCS长度。
2、根据递推关系:
(1) Ai = Bj 时, array[i+1][j+1] = array[i][j]+1。
(2) Ai != Bj 时,array[i+1][j+1] = max(array[i][j+1] , array[i+1][j])。

AC code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstring>
using namespace std;

string a,b;
int array[110][110];
int al,bl;

void DP()
{
    for(int i=0 ; i<al ; i++)
    {
        for(int j=0 ; j<bl ; j++)
        {
            if(a[i]==b[j])
                array[i+1][j+1]=array[i][j]+1;
            else
                array[i+1][j+1]=max(array[i][j+1],array[i+1][j]);
        }
    }
}

int main()
{
    cin>>a>>b;
    memset(array,0,sizeof(array));
    al=a.length();
    bl=b.length();
    DP();
    cout<<array[al][bl]<<endl;
    return 0;
}