Palindromic Partitions - CEOI 2017

palindromic.cpp

// Palindromic Partitions - CEOI 2017
// Complexidade O(N)

#include <bits/stdc++.h>
#define X 145443351LL
#define mod 1000000007LL
using namespace std;
typedef long long ll;

ll Hash[1000010], n, pot[1000010];

inline bool compare(int i, int j, int ii, int jj)
{
	ll dx = (i > 0 ? Hash[i - 1] : 0);

	ll A = (mod + Hash[j] - dx)%mod;

	ll dx2 = (ii > 0 ? Hash[ii - 1] : 0);

	ll A2 = (mod + Hash[jj] - dx2)%mod;

	return (((A*pot[ii])%mod) == ((A2*pot[i])%mod));
}

string s;

int solve(int ini)
{
	int fim = s.size() - 1 - ini;

	if(ini == fim) return 1;

	if(ini > fim) return 0;

	int best = 1;

	for(int p = ini; p <= (ini + fim)/2; p++)
	{
		if(compare(ini, p, fim - p + ini, fim))
		{
			best = max(best, 2 + solve(p + 1));

			break;
		}
	}

	return best;
}

int T;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>T;

	pot[0] = 1;

	for(int i = 1; i < 1000010; i++) pot[i] = (pot[i - 1]*X)%mod;

	while(T--)
	{
		cin>>s;

		n = s.size();

		Hash[0] = 0;

		for(int i = 0; i < n; i++)
		{
			if(i > 0) Hash[i] = Hash[i - 1];

			Hash[i] = (Hash[i] + s[i]*pot[i])%mod;
		}

		cout<<solve(0)<<"\n";
	}
}