当前位置：编程学习 > C/C++ >>

HDU1159——Common Subsequence


		没什么多说的，LCS问题盲打过，但我CE了两次，因为把I和J搞混了。。另外注意LCS是中间可以有间隔的，KMP则没有。另外别忘了前两天博客中曾经提到的二分法。
[cpp]  
#include <iostream>  
#include <cstring>  
#include <string>  
using namespace std;  
  
int max(int a,int b)  
{  
    return a>b?a:b;  
}  
  
int dp[3400][3400];  
int main()  
{  
    string a,b;  
    while(cin>>a>>b)  
    {  
        int as=a.size();  
        int bs=b.size();  
        for(int i=0;i<as;i++)  
        {  
            for(int j=0;j<bs;j++)  
            {  
                dp[i][j]=0;  
            }  
        }  
        //dp[0][0]=1;  
          
        for(int i=0;i<=as;i++)  
        {  
            for(int j=0;j<=bs;j++)  
            {  
                if(a[i]==b[j])  
                {  
                    dp[i+1][j+1]=dp[i][j]+1;  
                }  
                else  
                {  
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);  
                }  
            }  
        }  
        cout<<dp[as][bs]<<endl;  
          
    }  
      
    return 0;  
}