求最长连续字串

时间：2011-05-24 来源：我们一直在努力

题目链接：http://59.69.128.200/JudgeOnline/problem.php?pid=308

#include <iostream>
#include <cstring>
using namespace std;
#define Max_len 1000
char sz1[Max_len];
char sz2[Max_len];
int maxlen[Max_len][Max_len];
int main()
{
int i,j,n,k1,k2;
cin>>n;
while (n--)
{
  memset(sz1,'\0',sizeof(sz1));
  memset(sz2,'\0',sizeof(sz1));
        memset(maxlen,0,sizeof(maxlen));
  k1=1;
  cin>>sz1+1;
  int length1=strlen(sz1+1);
  for (i=length1;i>=1;i--)
  {
   sz2[k1++]=sz1[i];
  }

  int length2=strlen(sz2+1);
  for (i=0;i<=length1;i++)
   maxlen[i][0]=0;
  for (i=0;i<=length2;i++)
   maxlen[0][i]=0;
  for (i=1;i<=length1;i++)
  {
   for (j=1;j<=length2;j++)
   {
    if(sz1[i]==sz2[j])
     maxlen[i][j]=maxlen[i-1][j-1]+1;

   }
  }
  int ma=k1=k2=0;
  for (i=1;i<=length1;i++)
  {
   for (j=1;j<=length2;j++)
   {
    if(maxlen[i][j]>ma)
    {
     ma=maxlen[i][j];
     k2=i;
    }

   }
  }
  for(i=k2-ma+1;i<=k2;i++)
   cout<<sz1[i];
  cout<<endl;
}
return 0;
}