最长公共子序列问题

Time Limit: 1000MS  Memory Limit: 65536KB
Submit  Statistic

Problem Description

 给定两个序列X=

Input

输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

Output

每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

Example Input

ABCBDAB
BDCABA

Example Output

4

Hint

 

Author


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char a[505], b[505];
    int s[505][505], i, j;
    while(~scanf("%s%s",a, b))
    {
        int n, m;
        n = strlen(a);
        m = strlen(b);
        memset(s,0,sizeof(s));
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < m; j++)
            {
                if(a[i] == b[j])
                    s[i+1][j+1] += s[i][j] + 1;
                else
                {
                    if(s[i][j+1] > s[i+1][j])
                        s[i+1][j+1] = s[i][j+1];
                    else
                        s[i+1][j+1] = s[i+1][j];
                }
            }
        }
        printf("%d\n", s[n][m]);
    }
    return 0;
}