Pagini recente » Cod sursa (job #2815316) | Cod sursa (job #1773335) | Cod sursa (job #773926) | Cod sursa (job #1288762) | Cod sursa (job #2335071)
/** Cel mai lung subsir palindrom**/
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
char s[200010];
int l;
int P[200010]; /// p[i] retine lungimea palindroamelor centrate pe i
int C, R, simi;
char t[100010];
ifstream f("pscpld.in");
ofstream g("pscpld.out");
void add_hashes()
{
f.getline(t, 100010);
int p = strlen(t);
for(int i=0; i<p; i++)
{
s[2*i] = '#';
s[2*i+1] = t[i];
}
s[2*p] = '#';
l = 2*p+1;
}
int main()
{
add_hashes(); /// se adauga elemente care nu se gasesc (pt subsiruri de lungime para);
C = 0;
R = 0;
long long vm=0;
for(int i=1; i<l; i++)
{
simi = C-(i-C);
P[i] = 0;
if(R >= i){
P[i] = min(R-i, P[simi]); /// intr-un fel, maximul pe care il poate sustine
}
while(s[i+1+P[i]] == s[i-1-P[i]] && i-1-P[i] >= 0 && i+1+P[i] <l)
{
P[i]++;
}
if(i + P[i] > R)
{
C = i;
R = i + P[i];
}
vm = vm + (P[i]+1)/2;
}
g<<vm;
return 0;
}