7D - Palindrome Degree

7D - Palindrome Degree .cpp

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <math.h>
#include <fstream>
#include <stack>
#include <list>
using namespace std;
#define LL long long

//#define LOCAL

string preProcess(string s) {
    int n = s.length();
    if (n == 0) return "^$";
    string ret = "^";
    for (int i = 0; i < n; i++)
        ret += "#" + s.substr(i, 1);

    ret += "#$";
    return ret;
}


int main()
{
#ifdef LOCAL
    std::ifstream in("in.txt");
    std::streambuf *cinbuf = std::cin.rdbuf(); //save old buf
    std::cin.rdbuf(in.rdbuf()); //redirect std::cin to in.txt!
#endif

    string s;
    cin >> s;
    int n = s.size();
    int *t = new int[n]();

    //Manacher's algorithm
    //http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
    string T = preProcess(s);
    int nt = T.size();
    int *P = new int[nt];
    int C = 0, R = 0;
    for (int i = 1; i < nt - 1; ++i) {
        int i_mirror = 2*C-i; // equals to i' = C - (i-C)

        P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;

        // Attempt to expand palindrome centered at i
        while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
            P[i]++;

        // If palindrome centered at i expand past R,
        // adjust center based on expanded palindrome.
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
    }

    //set t[i] = 1 if s[0..i] is palindrome
    for (int i = 1; i < nt - 1; i++) {
        if (P[i] == i - 1) {
            t[i - 2] = 1;
        }
    }

    int res = 1;
    for (int i = 1; i < n; ++i)
    {
        //compute palindrome degree for s[0..i]
        if (t[(i - 1) / 2] && t[i])
        {
            t[i] = t[(i - 1) / 2] + 1;            
        }        
        res += t[i];
    }

    cout << res;

    return 0;
}