HDU 4295 4 substrings problem(狀態壓縮)

[cpp]
/*
內存超了，這道題原來不想做，後來打算只要把數據過了就行
結果內存超了，狀態壓縮，
*/ 
 
#include <cstdio> 
#include <cstring> 
const int INF = 4100; 
int d1[4096][16][64], d2[4100][16][64]; 
char S[4100], a[4][70]; 
int can[4100][4]; 
int next[70]; 
 
void getNext(char *s, int len) 
{ 
    next[0] = -1; 
    int i, j; 
    for(i = 0, j = -1; i < len; ++ i) 
    { 
        if(j == -1 || s[i] == s[j]) 
        { 
            i ++; 
            j ++; 
            if(s[i] == s[j]) 
                next[i] = next[j]; 
            else 
                next[i] = j; 
        } 
        else 
            j = next[j]; 
    } 
} 
 
void match(int c, char *S, char *s, int len_S, int len_s) 
{ 
    int i, j; 
    for(i = 0, j = 0; i < len_S;) 
    { 
        if(j == -1 || S[i] == s[j]) 
        { 
            i ++; 
            j ++; 
            if(j == len_s) 
            { 
                can[i - len_s][c] = 1; 
                i = i - len_s + 1; 
                j = 0; 
            } 
        } 
        else 
            j = next[j]; 
    } 
} 
 
int min(int a, int b) 
{ 
    return a < b ? a : b; 
} 
 
int max(int a, int b) 
{ 
    return a > b ? a : b; 
} 
 
int main() 
{ 
    //freopen("e://data.in", "r", stdin); 
    int up = (1 << 4); 
    while(scanf("%s%s%s%s%s", S, a[0], a[1], a[2], a[3]) != EOF) 
    { 
        int i, j, k, l, m, kk; 
        int len_S, len_a[4]; 
        len_S = strlen(S); 
        for(i = 0; i < 4; ++ i)   
            len_a[i] = strlen(a[i]); 
        memset(can, 0, sizeof(can)); 
        for(i = 0; i < 4; ++ i) 
        { 
            getNext(a[i], len_a[i]); 
            match(i, S, a[i], len_S, len_a[i]); 
        } 
         
        int _max = 0, _min = 4100; 
        memset(d1, -1, sizeof(d1)); 
        for(i = 0; i < 4096; ++ i) 
            for(j = 0; j < 16; ++ j) 
                for(k = 0; k < 64; ++ k) 
                    d1[i][j][k] = INF; 
        memset(d2, -1, sizeof(d2)); 
        for(j = 0; j < 4; ++ j) 
        { 
            if(can[0][j]) 
                d1[0][1 << j][len_a[j]] = d2[0][1 << j][len_a[j]] = len_a[j]; 
        } 
        for(i = 1; i < len_S; ++ i) 
        { 
             
            for(j = 0; j < 4; ++ j) 
            { 
                if(can[i][j]) 
                { 
                    for(k = 0; k < up; ++ k) 
                    { 
                        if(k & (1 << j)) 
                        { 
                            kk = k; 
                            for(l = max(0, i - 64); l < i; ++ l) 
                            { 
                                for(m = 0; m <= 64; ++ m) 
                                { 
                                    if(d1[l][k][m] != INF && l + m >= i) 
                                        d1[i][k][len_a[j]] = min(d1[i][k][len_a[j]], d1[l][k][m]); 
                                    if(d2[l][k][m] != -1 && l + m >= i) 
                                        d2[i][k][len_a[j]] = max(d2[i][k][len_a[j]], d2[l][k][m]); 
                                } 
                            } 
                        } 
                        else 
                        { 
                            kk = (k | (1 << j)); 
                            for(l = max(0, i - 64); l < i; ++ l) 
                            { 
                                for(m = 0; m <= 64; ++ m) 
                                { 
                                    if(d1[l][k][m] != INF && l + m >= i) 
                                        d1[i][kk][len_a[j]] = min(d1[i][kk][len_a[j]], d1[l][k][m] + len_a[j]); 
                                    if(d2[l][k][m] != -1 && l + m >= i) 
                                        d2[i][kk][len_a[j]] = max(d2[i][kk][len_a[j]], d2[l][k][m] + len_a[j]); 
                                } 
                            } 
                        } 
                        if(i + len_a[j] >= len_S) 
                        { 
                            _min = min(_min, d1[i][kk][len_a[j]]); 
                            _max = max(_max, d2[i][kk][len_a[j]]); 
                        } 
                    } 
                } 
            } 
        } 
        printf("%d %d\n", _min, _max); 
    } 
    return 0; 
}