POJ 1458

给出两个字符串，求它们最长的公共子字符串长度。

如abfgc  acbfefc

最长的公共子字符串为abfc   长度为4

思路：找到s1[i]与s2[j]的时候，相等的话，dp[i+1][j+1]=dp[i][j]+1;

　　　　不等的话dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);

 

 

#include

#include

#include

using namespace std;

int dp[300][300];

int main()

{   string s1,s2;

    while(cin>>s1>>s2){

    　　memset(dp,0,sizeof(dp));

   　　 for(int i=0;i
     　　   for(int j=0;j
     　　       if(s1[i]==s2[j]){

      　　          dp[i+1][j+1]=dp[i][j]+1;

      　　      }

       　　     else {

      　　          dp[i+1][j+1]=dp[i][j+1];

      　　          if(dp[i+1][j]>dp[i][j+1])dp[i+1][j+1]=dp[i+1][j];

      　　      }

    　　    }

  　　  }

  　　  cout<
　　}

   　return 0;

}