1092 演算法

題目說明

Please find the length of a longest common subsequence of two given nonempty strings.

Input

Each test case contains two nonempty strings, separated by whitespace character(s)
and consisting of characters ‘a’ and ‘b’. Two consecutive test cases are separated by
whitespace character(s). The input terminates with EOF.

Output

For each test case, output the length of a longest common subsequence of the two
given strings.

Technical Specification

  1. There are at most 10 test cases.
  2. Each string to be processed is at most 100 in length.

參考解法

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <string>

using namespace std;

int lcs(string a, string b)
{
    int path[101][101];

    for (int i = 0; i <= a.length(); i++)
    {
        path[0][i] = 0;
    }
    for (int j = 0; j <= b.length(); j++)
    {
        path[j][0] = 0;
    }
    for (int j = 0; j < b.length(); j++)
    {
        for (int i = 0; i < a.length(); i++)
        {
            if (a[i] == b[j])
            {
                 path[j + 1][i + 1] = path[j][i] + 1;
            }
            else
            {
                if (path[j][i + 1] > path[j + 1][i])
                {
                    path[j + 1][i + 1] = path[j][i + 1];
                }
                else
                {
                    path[j + 1][i + 1] = path[j + 1][i];
                }
            }
        }
    }

    return path[b.length()][a.length()];
} 

int main()
{
    
    string a, b;
    while(cin >> a >> b)
    {
        
        cout << lcs(a, b) << endl;
    }
   
    return 0;
}