Pagini recente » Cod sursa (job #1096736) | Cod sursa (job #3177969) | Cod sursa (job #2067774) | Cod sursa (job #1152256) | Cod sursa (job #2335121)
/** 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>>t;
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(i-1-P[i] >= 0 && i+1+P[i] <l && s[i+1+P[i]] == s[i-1-P[i]])
P[i]++;
if(i + P[i] > R)
{
R = i + P[i];
C = i;
}
vm = vm + (P[i]+1)/2;
}
g<<vm;
return 0;
}