Opis glavnog rešenja

Naivno rešenje ovog zadatka podrazumeva da za svaku podnisku niske \(S\) proverimo da li je palindrom i prebrojimo sve podniske koje jesu palindromi. Podniski neke niske ukupno ima \(O(n^2)\). Ako za svaku u linearnom vremenu proverimo da li je palindrom, ukupna složenost algoritma je \(O(n^3)\) što je prilično neefikasno.

Mnogo efikasnije rešenje možemo dobiti primenom Manacherovog algoritma. Prvo je za svaku poziciju potrebno odrediti dužinu najdužeg palindroma čija je sredina na toj poziciji, što radimo klasičnim Manacherovim algoritmom. Nakon toga, sve što treba da uradimo je da prođemo kroz dobijeni niz i vrednost na svakoj poziciji podelimo celobrojno sa 2. Kako se svaki palindrom dobija dodavanjem po 2 karaktera na početak i kraj u odnosu na centar, deljenjem sa 2 ćemo dobiti broj palindromskih podniski čiji je centar karakter koji se razmatra. Složenost Manacherovog algoritma je linearna. Imamo još i dodatan prolazak kroz niz za šta je takođe potrebno linerano vreme, pa je i ukupna složenost \(O(n)\).

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int manacher(const string &s)
{
   const int n = s.size();

   string tmp = "$";
   for (int i = 0; i < n; i++) {
      tmp += "#";
      tmp += s[i];
   }
   tmp += "#@";

   vector<int> d(tmp.size());

   int C = 1, R = 1;
   for (int i = 1; i < tmp.size() - 1; i++) {
      int i_ = 2 * C - i;

      if (i < R) {
         d[i] = min(R - i, d[i_]);
      }

      while (tmp[i + (d[i] + 1)] == tmp[i - (d[i] + 1)]) {
         d[i]++;
      }

      if (i + d[i] > R) {
         C = i;
         R = i + d[i];
      }
   }

   int sum = 0;

   for (int x : d) {
      sum += x / 2;
   }

   return sum;
}

int main ()
{
   string s; cin >> s;

   cout << manacher(s) << endl;

   return 0;
}