Morris' Blog

2011-07-21 17:54:49Morris

d978. 最长回文字串 (TLE)

留言 1 收藏 0 推薦 0

d978. 最长回文字串
內容：

今天，你的任务是快速地找出一个字串的最长回文字串。

輸入說明：

第一行有一個整數 T ，代表接下來有幾組測試資料。

每一組測試資料有一個字串，字串是由小寫的英文字母所組成，每個字串的長度不會超過 500000 。

輸出說明：

對每筆測試資料輸出字串中最長的迴文長度。

範例輸入：

4
radar
hollow
cat
enhance

範例輸出：

提示：

鉴于NPSC 2010 高中组初赛 C.小丹妮与英文单字的测试数据较弱，故有了此题。

出處：

d945 NPSC 加强版 (管理：liouzhou_101)

先說以下做法會拿 TLE
作法 : SA + 高度數組 + ST
時間是 O(LlogL), 但是很不幸的, 通過不了
不過在我心中它已經AC了, 默哀

/*****************************************************************************/
/* Problem: d978 "最长回文字串" from d945 NPSC 加强版                   */
/* Language: C                                                                   */
/* Result: TLE (1) on ZeroJudge                                                 */
/* Author: morris1028 at 2011-07-21 17:42:51                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxL 1048576
void Merge(int, int, int);
void MergeSort(int, int);
int Build_Height(int);
void MergeSort(int, int);
void Merge(int, int, int);

struct xy_change_rank{
   int index, v;
}Data[MaxL], X[MaxL];
char S[MaxL], base_rank[256], Mask[MaxL];
int s2[30]={1}, rank[MaxL], SA[MaxL], Queue[MaxL] = {-1};
int height[MaxL];
int ST[MaxL*2];
void Doubling_Algorithm() {
    int a, b, C, temp;
    int L=strlen(S);
    for(a = 0; a < L; a++)
        rank[a] = base_rank[S[a]], Mask[a] = 0,
       Data[a].v = rank[a], Data[a].index = a;
    MergeSort(0, L-1);
    for(a = 0; s2[a] < L; a++) {
        temp = Data[0].v, C = 1;
        for(b = 0; b < L; b++) {
            if(Data[b].v != temp || Mask[b] == 1)
                Queue[C] = b-1, temp = Data[b].v, C++, Mask[b] = 1;
            rank[Data[b].index] = C;
        }
        Queue[C] = L-1, C++;
        for(b = 0; b < L; b++) {
            if(Data[b].index + s2[a] < L) Data[b].v = rank[Data[b].index + s2[a]];
            else Data[b].v = 0;
        }
        for(b = 1; b < C; b++)
            MergeSort(Queue[b-1]+1, Queue[b]);
    }
    for(a = 0; a < L; a++)
        SA[a] = Data[a].index;
}
int Build_Height(int L) {
   int a, b, k = 0;
   for(a = 0; a < L; a++)   rank[SA[a]] = a;
   for(a = 0; a < L; a++) {
       if(rank[a] == 0) {height[rank[a]] = 0; continue;}
       if(a == 0 || height[rank[a-1]] <= 1) k = 0;
       else k = height[rank[a-1]] - 1;
       while(S[SA[rank[a]-1]+k] == S[SA[rank[a]]+k])   k++;
       height[rank[a]] = k;
   }
}
int min(int x, int y) {
   return x < y ? x : y;
}
void initST(int l, int r, int k) {
    if(l == r) ST[k] = height[l];
    else {
         int m = (l + r)/2;
         initST(l, m, 2*k);
         initST(m+1, r, 2*k+1);
         ST[k] = min(ST[2*k], ST[2*k+1]);
    }
}
int Getmin(int l, int r, int k, int x, int y) {
    if(l == x && r == y) return ST[k];
    else {
         int m = (l + r)/2;
         if(m >= y) return Getmin(l, m, 2*k, x, y);
         else if(m < x) return Getmin(m+1, r, 2*k+1, x, y);
         else return min(Getmin(l, m, 2*k, x, m), Getmin(m+1, r, 2*k+1, m+1, y));
    }
}
int LCP(int i, int j, int L) {
   i = rank[i], j = rank[j];
   if(i > j) {
       int t;
       t = i, i = j, j = t;
   }
   return Getmin(0, L-1, 1, i+1, j);
}
main() {
    int a, T, C = 0;
    for(a = 1; a < 30; a++)   s2[a] = s2[a-1]*2;
    for(a = 'a'; a <= 'z'; a++)   base_rank[a] = a - 'a' + 1;
    scanf("%d", &T);
    getchar();
    while(T--) {
       gets(S);
       int L = strlen(S), a, b, n;
       S[L] = '#';
       for(a = L+1, b = 0; b < L; a++, b++)
           S[a] = S[L-b-1];
       S[2*L+1] = '$', S[2*L+2] = '\0';
       L = strlen(S);
       Doubling_Algorithm(), Build_Height(L);
       initST(0, L-1, 1), n = L/2-1;
       int max = 0, st, k;
       for(a = 0; a < n; a++) {
           k = LCP(a, L-a-1, L);
           if(k<<1 > max) {
               max = k<<1;
               st = a-k;
           }
           k = LCP(a, L-a-2, L);
           if((k<<1)-1 > max)   {
               max = (k<<1) - 1;
               st = a-k+1;
           }
       }
       printf("%d\n", max);
       /*printf("%s %d\n", S, L);
       for(a = 0; a < L; a++)
           printf("%s\n", S+SA[a]);
       puts("");
       for(a = 0; a < L; a++)
           printf("%2d ", a);
       puts("");
       for(a = 0; a < L; a++)
           printf("%2d ", SA[a]);
       puts("");
       for(a = 0; a < L; a++)
           printf("%2d ", height[a]);
       puts("");
       for(a = 0; a < L; a++)
           printf("%2d ", rank[a]);
       puts("");*/
   }
    return 0;
}
void MergeSort(int l, int h) {
   if(l < h) {
        int m=(l+h)/2;
        MergeSort(l ,m);
        MergeSort(m+1,h);
        Merge(l,m,h);
    }
}
void Merge(int l, int m, int h) {
    int In1 = l, In2 = m+1;
    int a, b, Top = 0;
    while(In1 <= m && In2 <= h)
        if(Data[In1].v <= Data[In2].v)
             X[Top++] = Data[In1++];
       else X[Top++] = Data[In2++];
    while(In1 <= m)   X[Top++] = Data[In1++];
    while(In2 <= h)   X[Top++] = Data[In2++];
    for(a = 0, b = l; a < Top; a++, b++)
        Data[b] = X[a];
}

上一篇：d243. 圖論專家 ( A* 版本)

下一篇：a064. SPOJ 4580.ABCDEF (Hash 版本)