最长公共子序列问题

PRoblem Description

Input

Output

Example Input

ABCBDABBDCABA
Example Output
4
Hint
 
Author
01
#include<stdio.h>
02
#include<string.h>
03
int max(int a, int b);
04
int main()
05
{
06
    char a[555], b[555];
07
    int i, n, d[555][555], m, j;
08
    while(scanf("%s%s", a, b) != EOF)
09
    {
10
        memset(d, 0, sizeof(d));
11
        n = strlen(a);
12
        m = strlen(b);
13
        for(i = 1; i <= n; i++)
14
        {
15
            for(j = 1; j <= m; j++)
16
            {
17
                if(a[i-1] == b[j-1])
18
                    d[i][j] = d[i-1][j-1] + 1;
19
                else
20
                    d[i][j] = max(d[i][j-1], d[i-1][j]);
21
            }
22
        }
23
        printf("%d/n", d[n][m]);
24
    }
25
    return 0;
26
}
27
int max(int a, int b)
28
{
29
    return a > b? a:b;
30
}
31
 
 
我舍友的“高级”做法：
01
#include <stdio.h>
02
#include <string.h>
03
int main()
04
{
05
    char a[510], b[510];
06
    int n, m, c[510][510], i, j;
07
    while(~scanf("%s %s", a, b))
08
    {
09
        memset(c, 0, sizeof(c));
10
        n = strlen(a);
11
        m = strlen(b);
12
        for(j=0; j<m; j++)
13
        {
14
            if(a[0]==b[j])
15
            {
16
                for(i=j; i<m; i++)
17
                {
18
                    c[0][i] = 1;
19
                }
20
                break;
21
            }
22
 
23
        }
24
        for(j=0; j<n; j++)
25
        {
26
            if(a[j]==b[0])
27
            {
28
                for(i=j; i<n; i++)
29
                {
30
                    c[i][0] = 1;
31
                }
32
                break;
33
            }
34
        }
35
        for(i=1; i<n; i++)
36
            for(j=1; j<m; j++)
37
            {
38
                if(a[i]==b[j])
39
                {
40
                    c[i][j] = c[i-1][j-1] + 1;
41
                }
42
                else
43
                {
44
                    if(c[i-1][j]>=c[i][j-1])
45
                        c[i][j] = c[i-1][j];
46
                    else
47
                        c[i][j] = c[i][j-1];
48
                }
49
            }
50
        printf("%d/n", c[n-1][m-1]);
51
    }
52
    return 0;
53
}