HDU 3613 扩展KMP

暴力枚举大水题，判断回文，扩展KMP

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = ;

int a[];

char str[];

char str1[];

int s[];

int _next[maxn],_extend[maxn];

int next1[maxn],extend1[maxn];

void getnext(char *T) {

    int a = ;

    int Tlen = strlen(T);

    _next[] = Tlen;

    while(a<Tlen-&&T[a]==T[a+]) a++;

    _next[] = a;

    a = ;

    for(int k=; k < Tlen; k++) {

        int p = a + _next[a] - ,L = _next[k-a];

        if((k-)+L>=p) {

            int j = (p-k+) >  ? p - k +  : ;

            while(k+j<Tlen&&T[k+j]==T[j])

                j++;

            _next[k] = j;

            a = k;

        }

        else _next[k] = L;

    }

}

void getextend(char *S,char *T) {

    int a = ;

    getnext(T);

    int Slen = strlen(S);

    int Tlen = strlen(T);

    int Minlen = Slen < Tlen ? Slen : Tlen;

    while(a<Minlen&&S[a]==T[a]) a++;

    _extend[] = a;

    a = ;

    for(int k = ; k < Slen; k++) {

        int p = a + _extend[a] - ,L = _next[k-a];

        if((k-)+L>=p) {

            int j = (p-k+) >  ? p - k +  : ;

            while(k+j<Slen&&j<Tlen&&S[k+j]==T[j]) j++;

            _extend[k] = j;

            a = k;

        }

        else

            _extend[k] = L;

    }

}

void getnext1(char *T) {

    int a = ;

    int Tlen = strlen(T);

    next1[] = Tlen;

    while(a<Tlen-&&T[a]==T[a+]) a++;

    next1[] = a;

    a = ;

    for(int k=; k < Tlen; k++) {

        int p = a + next1[a] - ,L = next1[k-a];

        if((k-)+L>=p) {

            int j = (p-k+) >  ? p - k +  : ;

            while(k+j<Tlen&&T[k+j]==T[j])

                j++;

            next1[k] = j;

            a = k;

        }

        else next1[k] = L;

    }

}

void getextend1(char *S,char *T) {

    int a = ;

    getnext1(T);

    int Slen = strlen(S);

    int Tlen = strlen(T);

    int Minlen = Slen < Tlen ? Slen : Tlen;

    while(a<Minlen&&S[a]==T[a]) a++;

    extend1[] = a;

    a = ;

    for(int k = ; k < Slen; k++) {

        int p = a + extend1[a] - ,L = next1[k-a];

        if((k-)+L>=p) {

            int j = (p-k+) >  ? p - k +  : ;

            while(k+j<Slen&&j<Tlen&&S[k+j]==T[j]) j++;

            extend1[k] = j;

            a = k;

        }

        else

            extend1[k] = L;

    }

}

int main() {

    int T;

    scanf("%d",&T);

    while(T--) {

        for(int i = ; i < ; i++)

            scanf("%d",&a[i]);

        scanf("%s",str);

        int len = strlen(str);

        s[] = a[ str[] - 'a' ];

        for(int i = ; i < len; i++)

            s[i] = s[i-] + a[ str[i]-'a' ];

        for(int i = ; i < len; i++)

            str1[i] = str[len-i-];

        getextend(str1,str);

        getextend1(str,str1);

        int ans = ;

        for(int i = ; i < len-; i++)

        {

            if(_extend[len-i-]==i+&&extend1[i+]==len-i-)

                ans = max(ans,s[len-]);

            else if(_extend[len-i-]==i+)

                ans = max(ans,s[i]);

            else if(extend1[i+]==len-i-)

                ans = max(ans,s[len-]-s[i]);

        }

        printf("%d\n",ans);

    }

    return ;

}