Code Library Of Others/sgtlaugh/Palindrome Factorization.cpp
inline vector <int> factorize(const char* str){
        int g[32][3], gp[32][3], gpp[32][3];
        int i, j, k, l, d, u, r, x, pg = 0, pgp = 0, pgpp = 0, n = strlen(str);

        clr(g), clr(gp), clr(gpp);
        for (int i = 0; i < n; i++) gpl[i][0] = MAX, gpl[i][1] = MAX + 1;

        for (j = 0; j < n; j++){
            for (u = 0, pgp = 0; u < pg; u++){
                i = g[u][0];
                if ((i - 1) >= 0 && str[i - 1] == str[j]){
                    g[u][0]--;
                    copy(gp[pgp++], g[u]);
                }
            }

            pgpp = 0, r = -(j + 2);
            for (u = 0; u < pgp; u++){
                i = gp[u][0], d = gp[u][1], k = gp[u][2];
                if ((i - r) != d){
                    set(gpp[pgpp++], i, i - r, 1);
                    if (k > 1) set(gpp[pgpp++], i + d, d, k - 1);
                }
                else set(gpp[pgpp++], i, d, k);
                r = i + (k - 1) * d;
            }

            if (j - 1 >= 0 && str[j - 1] == str[j]){
                set(gpp[pgpp++], j - 1, j - 1 - r, 1);
                r = j - 1;
            }
            set(gpp[pgpp++], j, j - r, 1);

            int *ptr = gpp[0];
            for (u = 1, pg = 0; u < pgpp; u++){
                int *x = gpp[u];
                if (x[1] == ptr[1]) ptr[2] += x[2];
                else {
                    copy(g[pg++], ptr);
                    ptr = x;
                }
            }
            copy(g[pg++], ptr);

            pl[j + 1][(j & 1) ^ 1] = j + 1;
            pl[j + 1][j & 1] = MAX + (j & 1);
            for (u = 0; u < pg; u++){
                i = g[u][0], d = g[u][1], k = g[u][2];
                r = i + (k - 1) * d;

                update(pl, j + 1, pl[r][0] + 1);
                update(pl, j + 1, pl[r][1] + 1);
                if (k > 1) {
                    update(pl, j + 1, gpl[i + 1 - d][0]);
                    update(pl, j + 1, gpl[i + 1 - d][1]);
                }

                if (i + 1 >= d) {
                    if (k > 1) {
                        update(gpl, i + 1 - d, pl[r][0] + 1);
                        update(gpl, i + 1 - d, pl[r][1] + 1);
                    }
                    else{
                        set(gpl, i + 1 - d, pl[r][0] + 1);
                        set(gpl, i + 1 - d, pl[r][1] + 1);
                    }
                }
            }
        }

        vector <int> res(n, 0);
        for (i = 0; i < n; i++) res[i] = min(pl[i + 1][0], pl[i + 1][1]);
        return res;
    }
/// Returns a vector v such that,
/// v[i] is the minimum k so that the prefix string str[0:i] can be partitioned into k disjoint palindromes
Returns a vector v such that,
v[i] is the minimum k so that the prefix string str[0:i] can be partitioned into k disjoint palindromes
Returns a vector v such that v [ i ] is the minimum k so that the prefix string str [ 0 : i ] can be partitioned into k disjoint palindromes
inline vector <int> factorize(const char* str){
        int g[32][3], gp[32][3], gpp[32][3];
        int i, j, k, l, d, u, r, x, pg = 0, pgp = 0, pgpp = 0, n = strlen(str);
        clr(g), clr(gp), clr(gpp);
        for (int i = 0; i < n; i++) gpl[i][0] = MAX, gpl[i][1] = MAX + 1;
        for (j = 0; j < n; j++){
            for (u = 0, pgp = 0; u < pg; u++){
                i = g[u][0];
                if ((i - 1) >= 0 && str[i - 1] == str[j]){
                    g[u][0]--;
                    copy(gp[pgp++], g[u]);
                }
            }
            pgpp = 0, r = -(j + 2);
            for (u = 0; u < pgp; u++){
                i = gp[u][0], d = gp[u][1], k = gp[u][2];
                if ((i - r) != d){
                    set(gpp[pgpp++], i, i - r, 1);
                    if (k > 1) set(gpp[pgpp++], i + d, d, k - 1);
                }
                else set(gpp[pgpp++], i, d, k);
                r = i + (k - 1) * d;
            }
            if (j - 1 >= 0 && str[j - 1] == str[j]){
                set(gpp[pgpp++], j - 1, j - 1 - r, 1);
                r = j - 1;
            }
            set(gpp[pgpp++], j, j - r, 1);
            int *ptr = gpp[0];
            for (u = 1, pg = 0; u < pgpp; u++){
                int *x = gpp[u];
                if (x[1] == ptr[1]) ptr[2] += x[2];
                else {
                    copy(g[pg++], ptr);
                    ptr = x;
                }
            }
            copy(g[pg++], ptr);
            pl[j + 1][(j & 1) ^ 1] = j + 1;
            pl[j + 1][j & 1] = MAX + (j & 1);
            for (u = 0; u < pg; u++){
                i = g[u][0], d = g[u][1], k = g[u][2];
                r = i + (k - 1) * d;
                update(pl, j + 1, pl[r][0] + 1);
                update(pl, j + 1, pl[r][1] + 1);
                if (k > 1) {
                    update(pl, j + 1, gpl[i + 1 - d][0]);
                    update(pl, j + 1, gpl[i + 1 - d][1]);
                }
                if (i + 1 >= d) {
                    if (k > 1) {
                        update(gpl, i + 1 - d, pl[r][0] + 1);
                        update(gpl, i + 1 - d, pl[r][1] + 1);
                    }
                    else{
                        set(gpl, i + 1 - d, pl[r][0] + 1);
                        set(gpl, i + 1 - d, pl[r][1] + 1);
                    }
                }
            }
        }
        vector <int> res(n, 0);
        for (i = 0; i < n; i++) res[i] = min(pl[i + 1][0], pl[i + 1][1]);
        return res;
    }
inline vector < int > factorize ( const char * str ) { int g [ 32 ] [ 3 ] , gp [ 32 ] [ 3 ] , gpp [ 32 ] [ 3 ] ; int i , j , k , l , d , u , r , x , pg = 0 , pgp = 0 , pgpp = 0 , n = strlen ( str ) ; clr ( g ) , clr ( gp ) , clr ( gpp ) ; for ( int i = 0 ; i < n ; i ++ ) gpl [ i ] [ 0 ] = MAX , gpl [ i ] [ 1 ] = MAX + 1 ; for ( j = 0 ; j < n ; j ++ ) { for ( u = 0 , pgp = 0 ; u < pg ; u ++ ) { i = g [ u ] [ 0 ] ; if ( ( i - 1 ) >= 0 && str [ i - 1 ] == str [ j ] ) { g [ u ] [ 0 ] -- ; copy ( gp [ pgp ++ ] , g [ u ] ) ; } } pgpp = 0 , r = - ( j + 2 ) ; for ( u = 0 ; u < pgp ; u ++ ) { i = gp [ u ] [ 0 ] , d = gp [ u ] [ 1 ] , k = gp [ u ] [ 2 ] ; if ( ( i - r ) != d ) { set ( gpp [ pgpp ++ ] , i , i - r , 1 ) ; if ( k > 1 ) set ( gpp [ pgpp ++ ] , i + d , d , k - 1 ) ; } else set ( gpp [ pgpp ++ ] , i , d , k ) ; r = i + ( k - 1 ) * d ; } if ( j - 1 >= 0 && str [ j - 1 ] == str [ j ] ) { set ( gpp [ pgpp ++ ] , j - 1 , j - 1 - r , 1 ) ; r = j - 1 ; } set ( gpp [ pgpp ++ ] , j , j - r , 1 ) ; int * ptr = gpp [ 0 ] ; for ( u = 1 , pg = 0 ; u < pgpp ; u ++ ) { int * x = gpp [ u ] ; if ( x [ 1 ] == ptr [ 1 ] ) ptr [ 2 ] += x [ 2 ] ; else { copy ( g [ pg ++ ] , ptr ) ; ptr = x ; } } copy ( g [ pg ++ ] , ptr ) ; pl [ j + 1 ] [ ( j & 1 ) ^ 1 ] = j + 1 ; pl [ j + 1 ] [ j & 1 ] = MAX + ( j & 1 ) ; for ( u = 0 ; u < pg ; u ++ ) { i = g [ u ] [ 0 ] , d = g [ u ] [ 1 ] , k = g [ u ] [ 2 ] ; r = i + ( k - 1 ) * d ; update ( pl , j + 1 , pl [ r ] [ 0 ] + 1 ) ; update ( pl , j + 1 , pl [ r ] [ 1 ] + 1 ) ; if ( k > 1 ) { update ( pl , j + 1 , gpl [ i + 1 - d ] [ 0 ] ) ; update ( pl , j + 1 , gpl [ i + 1 - d ] [ 1 ] ) ; } if ( i + 1 >= d ) { if ( k > 1 ) { update ( gpl , i + 1 - d , pl [ r ] [ 0 ] + 1 ) ; update ( gpl , i + 1 - d , pl [ r ] [ 1 ] + 1 ) ; } else { set ( gpl , i + 1 - d , pl [ r ] [ 0 ] + 1 ) ; set ( gpl , i + 1 - d , pl [ r ] [ 1 ] + 1 ) ; } } } } vector < int > res ( n , 0 ) ; for ( i = 0 ; i < n ; i ++ ) res [ i ] = min ( pl [ i + 1 ] [ 0 ] , pl [ i + 1 ] [ 1 ] ) ; return res ; }
Returns a vector v such that,
v[i] is the minimum k so that the prefix string str[0:i] can be partitioned into k disjoint palindromes
Returns a vector v such that v [ i ] is the minimum k so that the prefix string str [ 0 : i ] can be partitioned into k disjoint palindromes