UVA-13092-Fold the String ( Manacer+DP )

Prob: UVA-13092-Fold the String (Manacer+DP)
IDEA:
    According to problem, we have given a string,starting from last position
of string,we have to fold the string into even palindrome mirror with cost
of "Y" or we may erase last char with cost of "X".
First, Observation to solve this problem is that , from each point we should
try to fold a string with maximum length possible.
So, Using manacer, we find from each position , minimum possible index to
which it can be folded. For this, Initially, put a minimum index to each end
index of palindrome centered at some position.
Then, update this minimum values to each valid index coming from backside of
string.
Now, finally a simple DP with two options whether to erase last char or
to go to min index.

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     2000115
#define inf    2000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

char s[MX+2],ss[MX+2];
int n,m,p[MX+2];

void Manacher( ) {
    m=n*2+2;
    ss[0]='*';
    for(int i=1,j=0; i<m; i+=2,j++)ss[i]=s[j],ss[i+1]='*';
    ss[m-1]='\0';
    int c=0,r=0,len;
    for(int i=1; i<m-1; i++) {
        int mi=2*c-i;
        len=(r>i)?min(r-i,p[ mi ]):0;
        while(i-1-len>=0 && i+1+len<m && ss[i-1-len]==ss[i+1+len] )++len;
        p[ i ]=len;
        if( i+len>r )c=i,r=i+len;
    }
}

int Mn[MX+2];
int x,y,dp[MX+2];

int go(int p) {
    if(p<=0)return 0;
    int &ret=dp[p];
    if(ret!=-1)return ret;
    ret=x+go(p-1);
    if( Mn[p]<p ) {
        ret=min( ret,y+go(Mn[p]) );
    }
    return ret;
}

int main() {
    int tc,cs=1,i,j,k;
    S(tc);
    while(tc--) {
        S2(x,y);
        scanf("%s",s);
        n=strlen(s);
        Manacher();
        for(int i=0; i<m; i++) {
            Mn[i]=inf;
        }
        for(i=0; i<m-1; i++) {
            if(i%2==0 && p[i] ) {
                int nx=( i+p[i] )/2; ///1-Based EndPos in mainString of Pal having mirror at i
                Mn[ nx ]=min( Mn[nx],i/2 );
            }
        }
        int pv=inf;
        for(i=n; i>=1; i--) {
            pv=min(pv,Mn[i]);
            if( pv<i )Mn[i]=pv;
        }
        SET(dp);
        int ans=go(n);
        printf("Case %d: %d\n",cs++,ans);
    }
    return 0;
}