Cod sursa(job #2847309)

Utilizator euyoTukanul euyo Data 10 februarie 2022 16:41:55
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

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

const int MAXN = 1000005; 

string transform( const string &s ); 

int ext[2 * MAXN + 1];
string s, t;

void Manacher( const string &s ) {
  t = transform(s);
  int l = 0, r = 0, n = t.length();
	
  ext[0] = 1;
  for ( int i = 1; i < n; i++ ) {
	if ( i <= r ) {  
      ext[i] = min( r - i + 1, ext[l + (r - i)] );
	}
	while ( i + ext[i] < n && i - ext[i] >= 0 && t[i - ext[i]] == t[i + ext[i]] ) {
      ++ext[i];
    }
	if ( i + ext[i] - 1 > r ) {
      l = i - ext[i] + 1;
      r = i + ext[i] - 1;
    }
  }  
}

int main() {
  long long res = 0;
  fin >> s;
  Manacher(s);
  for ( int i = 0; i < t.length(); ++i ) {
    res += ext[i] / 2;
  }
  fout << res;
  fin.close();
  fout.close();
  return 0;
}

string transform( const string &s ) {
  string st;
  st.push_back('#');
  for ( auto ch : s ) {
	st.push_back(ch);
	st.push_back('#');
  }
  return st;
}