字符串回文算法超时问题

总是超过限定的1000ms

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char dst[2000000];
char s[1000000];
long P[2000000];

long kp(char *d, long dlen){
    long mid = 1, mx = 1,i = 0, j = 0, k = 0,ans = 0;
    P[0] = -1;
    P[1] = 1;
    for(i = 1;i < dlen;i++){
        j = 2*mid - 1;
        mx = mid + P[mid] - 1;
        if(mx > i){
            P[i] = (P[j]<(mx-mid+1))?(P[j]):(mx-mid+1); 
        }
        else{
            P[i] = 1;
        }
        k = P[i];
        for(;d[i+k] == d[i-k];k++){P[i]++;}
        if(ans < P[i]){
            ans = P[i];
        }
        if(P[i] + i > mx){
            mx = P[i] + i;
            mid = i;
        }
    }

    return ans-1;
}

int main(){
    long n,i,j,t;
    long len[30];
    long dlen;
    long slen;
    char tmp = ' ';
    scanf("%ld",&n);
    for(i = 0; i < n; i++){
        scanf("%s",s);
        dst[0] = '$';
        dst[1] = '#';
        slen = strlen(s);
        for(j = 0; j < slen; j++){
            dst[2*j+2] = s[j];
            dst[2*j+3] = '#';
        } 
        dlen = slen*2 + 2;
        t = kp(dst,dlen);   
        printf("%ld\n",t);
    }
    return 0;
}