Pagini recente » Cod sursa (job #923868) | Cod sursa (job #2162733) | Cod sursa (job #2721752) | Cod sursa (job #2953058) | Cod sursa (job #2079244)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int NMAX = 1000000 + 100;
int n;
int lung[NMAX * 2];
long long res;
string s1, s;
int main()
{
in >> s1;
n = s1.size();
for(int i = 1; i <= n; i++) {
s[2 * i - 1] = '#';
s[2 * i] = s1[i - 1];
}
s[2 * n + 1] = '#';
n = n * 2 + 1;
int j = 0;
for(int i = 1; i <= n; i++) {
//cout << s[i] << ' ';
if(i < lung[j] + j)
lung[i] = min(lung[2 * j - i], j - i + lung[j]);
else
lung[i] = 1;
while(lung[i] < i && s[i - lung[i]] == s[i + lung[i]])
lung[i]++;
res += 1LL * (lung[i] / 2);
if(j + lung[j] < i + lung[i])
j = i;
}
//cout << "here";
out << res << '\n';
in.close();
out.close();
return 0;
}