Pagini recente » Istoria paginii runda/testround3b/clasament | Monitorul de evaluare | Cod sursa (job #1220519) | Cod sursa (job #1483176) | Cod sursa (job #2260548)
#include <vector>
#include <cstring>
#include <fstream>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const long long Dim = 1e6 + 5;
long long n,LC[Dim * 2],l = 0,r = -1,k;
char T[Dim];
vector < char > b;
int main() {
fin >> ( T + 1 );
long long n = strlen( T + 1 );
for ( long long i = 1; i <= n; ++i) {
b.push_back('*');
b.push_back(T[i]);
} b.push_back('*');
for ( long long i = 0; i < b.size(); ++i) {
if ( i > r)
k = 0;
else
k = min(LC[l +r - i],r - i);
while ( i + k < b.size()and i - k >= 0 and b[i+k] == b[i-k])
k++;
LC[i] = k--;
if ( i + k > r)
l = i - k , r = i + k;
}
long long ans = strlen(T + 1);
for ( long long i = 0; i < b.size(); ++i)
ans += (LC[i] - 1) / 2LL;
fout << ans;
}