Cod sursa(job #2791087)

Utilizator GrizzyProblemSolver79cNot telling GrizzyProblemSolver79c Data 30 octombrie 2021 05:35:36
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

int const NMAX = 1000000;
int n;
string input;
string s;
int dp[1 + 2 * NMAX + 1];

int main() {
  fin >> input;
  s.push_back('$');
  for(int i = 0; i < input.length(); i++) {
    s.push_back('*');
    s.push_back(input[i]);
  }
  s.push_back('*');
  s.push_back('#');
  //cout << s << "\n";
  n = s.length();
  dp[0] = 0;
  int c = 0;
  int right = c;
  //cout << 0 << " " << dp[0] << " " << c << " " << right << "\n";
  for(int i = 1; i < n; i++) {
    if(i < right) {
      dp[i] = min(dp[2*c-i], right-i);
    }

    while(s[i-dp[i]-1] == s[i+dp[i]+1]) {
      dp[i]++;
    }

    if(i + dp[i] > right) {
      c = i;
      right = i + dp[i];
    }
    //cout << i << " " << dp[i] << " " << c << " " << right << "\n";
  }
  int ans = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == '$' || s[i] == '#' || s[i] == '*') {
      ans += dp[i]/2;
    } else {
      ans += (dp[i]+1)/2;
    }
    //cout << (dp[i]+1)/2 << " ";
    //ans += dp[i]/2;
  }
  fout << ans;
}