复读子串 Repeated Subsequences [EOlymp – 3624]题解
最长公共子列问题。
这个题的时限特别长，是10秒钟，看来似乎是可以枚举串的所有分组并逐一计算LCS。
先写能够计算最长公共子序列的函数，然后对每种切分方式（遍历所有可切分的点），分别计算两串的最长公共子序列，记下最长的长度和序列，然后输出最长的那个序列即可。此题思路不难，关键在于如何输出最长公共子序列以及如何适当的存储中间数据。
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
int LCS(char* s1, char* s2,char *res)
{
int i,j,M,N,k=0,upbd;
M=strlen(s1);
N=strlen(s2);
int **dp;
dp=new int* [M+2];
for(i=0;i<M+2;i++)
dp[i]=new int [N+2];
for(i=0;i<N+2;i++)
dp[0][i]=0;
for(i=1;i<M+1;i++)
{
dp[i][0]=0;
for(j=1;j<N+1;j++)
{
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
k=dp[M][N];
i=M;
j=N;
upbd=k;
res[k]='\0';
while(i>0 && j>0)
{
if(dp[i-1][j]==dp[i-1][j-1] && dp[i-1][j-1]==dp[i][j-1] )
{
if (dp[i][j]==dp[i-1][j-1]+1)
res[--upbd]=s1[i-1];
i--;
j--;
}
else
{
if(dp[i-1][j]==dp[i][j])
i--;
else
j--;
}
}
for(i=0;i<M+2;i++)
delete [] dp[i];
delete [] dp;
return k;
}
void solve(char *s)
{
char *s1,*s2,*res,*target;
int N=strlen(s),i,d,maxVal=-1;
s1=new char [N+1];
s2=new char [N+1];
res=new char [N+1];
target=new char [N+1];
for(i=1;i<N;i++)
{
strcpy(s1,s);
s1[i]=0;
strcpy(s2,s+i);
d=LCS(s1,s2,res);
if(d>maxVal)
{
maxVal=d;
strcpy(target,res);
}
}
printf("%s\n",target);
delete [] s1;
delete [] s2;
delete [] res;
delete [] target;
}
#define MAXLENGTH 303
int main(void)
{
char s[MAXLENGTH];
while(scanf("%s",s)!=EOF)
{
if(strcmp("#END",s)==0)
break;
solve(s);
}
return 0;
}