Pagini recente » Clasament kontrollarbeit3 | Cod sursa (job #2017396) | Cod sursa (job #2247805) | Cod sursa (job #1685414) | Cod sursa (job #2847579)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <vector>
#define pb push_back
using namespace std;
const int NMAX = 2000005;
string s;
vector<char>v;
long long dp[NMAX];
long long st , dr , answer , k ;
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
cin >> s;
int length = s.size();
v.pb('*');
for(int i = 0 ; i < s.size() ; i++)
{
v.push_back(s[i]);
v.push_back('*');
}
for(int i = 0 ; i < v.size() ; i++)
{
if(i > dr)
k = 0;
else
k = min(dp[st+dr-i],dr-i);
while(i + k < v.size() && i - k >= 0 && v[i + k] == v[i - k])
k++;
dp[i] = k--;
if(i + k > dr)
{
dr = i + k;
st = i - k;
}
}
answer = length;
for(int i = 0; i < v.size(); i++)
answer += (dp[i] - 1) / 2;
cout << answer;
return 0;
}