1159 common subsequence.cpp

来自「威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。」· C++ 代码 · 共 44 行

/*
1159 Common Subsequence
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 5120 K

125 MS 2288 KB 963 B 
GUN C++
*/
#include <iostream.h>
#include <string.h>
using namespace std;
const int Max=500;

int main()
{
    char str1[Max],str2[Max];
    short record[Max][Max]={0};
    int len1,len2,i,j;
    while(cin>>str1>>str2)
    {
        len1=strlen(str1);  len2=strlen(str2);
        for(i=1;i<=len1;i++)
        {
            for(j=1;j<=len2;j++)
            {
                if(str1[i-1]==str2[j-1])
                {   record[i][j]=record[i-1][j-1]+1;}
                else
                {
                    if(record[i-1][j]>=record[i][j-1])
                    {   record[i][j]=record[i-1][j];}
                    else
                    {   record[i][j]=record[i][j-1];}
                }
            }
        }
        cout<<record[len1][len2]<<endl;
        for(i=1;i<=len1;i++)
            for(j=1;j<=len2;j++)
				record[i][j]=0;
    }
    return 0;
}