Pagini recente » Cod sursa (job #185857) | Cod sursa (job #738812) | Cod sursa (job #141509) | Cod sursa (job #433976) | Cod sursa (job #1312529)
//manarcher's: http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
#include <stdio.h>
#define MAXN 1000
int p[MAXN][2*MAXN+2], stiva[MAXN+1], st[MAXN], t[2*MAXN+3];
int max, n, m, k;
FILE *fin;
inline void update(int a){
if(max<a){
max=a;
}
}
inline void manacher(int l){
int c, r, i, j;
t[0]=-2;
m=1;
for(i=0; i<k; i++){
t[m++]=-1;
fscanf(fin, "%d", &t[m++]);
}
t[m]=-1;
t[m+1]=-3;
c=0;
r=0;
for(i=1; i<=m; i++){
j=2*c-i;
if(r>i){
if(p[l][j]<=r-i){
p[l][i]=p[l][j];
}else{
p[l][i]=r-i;
}
}
while(t[i+p[l][i]+1]==t[i-p[l][i]-1]){
p[l][i]++;
}
if(i+p[l][i]>r){
c=i;
r=i+p[l][i];
}
}
}
inline void skyline(int c){
int e, i;
stiva[0]=-1;
e=1;
for(i=0; i<n; i++){
while((e>1)&&(p[stiva[e-1]][c]>=p[i][c])){
e--;
}
st[i]=stiva[e-1];
stiva[e++]=i;
}
stiva[0]=n+1;
e=1;
for(i=n-1; i>=0; i--){
while((e>1)&&(p[stiva[e-1]][c]>=p[i][c])){
e--;
}
update(p[i][c]*(stiva[e-1]-st[i]-1));
stiva[e++]=i;
}
}
int main(){
int i;
FILE *fout;
fin=fopen("dreptpal.in", "r");
fout=fopen("dreptpal.out", "w");
fscanf(fin, "%d%d ", &n, &k);
for(i=0; i<n; i++){
manacher(i);
}
for(i=1; i<=m; i++){
skyline(i);
}
fprintf(fout, "%d\n", max);
fclose(fin);
fclose(fout);
return 0;
}