Nu aveti permisiuni pentru a descarca fisierul grader_test8.in
Cod sursa(job #1580281)
| Utilizator | Data | 25 ianuarie 2016 18:57:52 | |
|---|---|---|---|
| Problema | PScPld | Scor | 30 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.72 kb |
#include <fstream>
#include <iostream>
using namespace std;
char A[1000001];
char S[2000005];
int P[2000005];
int n,i;
int id,mx,j,rez;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
int main()
{
fi>>A;
S[0]='$';
n=0;
for (i=0;A[i]!='\0';i++)
{
S[++n]='#';
S[++n]=A[i];
}
S[++n]='#';
S[++n]='\0';
n--;
// se va construi sirul P
P[0]=1;
id=0;
mx=0;
for (i=1;i<=n;i++)
// se determina P[i]
{
if (mx>i)
{
j=2*id-i;
P[i]=min(P[j],mx-i);
}
else
P[i]=1;
while (S[i + P[i]] == S[i - P[i]])
P[i]++;
if (i+P[i]>mx)
{
mx=i+P[i];
id=i;
}
}
rez=0;
for (i=1;i<=n;i++)
rez=rez+P[i]/2;
fo<<rez;
fi.close();
fo.close();
return 0;
}