Nu aveti permisiuni pentru a descarca fisierul grader_test2.ok
Cod sursa(job #989141)
Utilizator | Gabriela Moldovan gbi250 | Data | 24 august 2013 23:10:48 |
---|---|---|---|
Problema | PalM | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.98 kb |
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[512], aux[512];
int i, l, r, p[1024], n, MAX, pz;
inline void expand(int &l, int &r)
{
while(s[l-1]==s[r+1] && l>=2 && r<=n-1)
++p[i], ++r, --l;
}
inline void manacher()
{
int len=strlen(aux)-1;
for(i=0;i<=len;++i)
{
s[++n]=aux[i];
s[++n]='#';
}
for(i=2;i<=n;++i)
{
if(i<=r)
{
p[i]=min(p[r-i+l], r-i);
if(p[i]==r-i)
{
l=i-p[i];
expand(l, r);
}
}
else
{
r=l=i;
expand(l, r);
}
if(p[i]>MAX)
{
MAX=p[i];
pz=i;
}
}
}
int main()
{
freopen("palm.in", "r", stdin);
freopen("palm.out", "w", stdout);
scanf("%s", aux);
manacher();
for(i=pz;i<=n && i-pz<=MAX;i+=2)
if(s[i]<s[i+2])
MAX--;
printf("%d\n", MAX);
return 0;
}