Palindrome - URAL - 1297（求回文串）

题目大意：RT

 

分析：后缀数组求回文串，不得不说确实比较麻烦，尤其是再用线段数进行查询，需要注意的细节地方比较多，比赛实用性不高......不过练练手还是可以的。

 

线段数+后缀数组代码如下：

===========================================================================================================================================

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int MAXN = 1e4+;

struct SuffixArr

{

    int tempx[MAXN], tempy[MAXN], text[MAXN];

    int rank[MAXN], sa[MAXN], height[MAXN], sum[MAXN];

    int *x, *y, N, MaxId;

    void GetText(char s[])

    {

        N = strlen(s)*+, MaxId = ;

        x = tempx, y = tempy;

        int i;

        for(i=; s[i]; i++)

        {

            text[i] = text[N-i-] = x[i] = x[N-i-] = (int)s[i];

            y[i] = i, y[N-i-] = N-i-;

        }

        text[i] = x[i] = , y[i] = i;

        text[N-] = x[N-] = , y[N-] = N-;

       /// debug();

    }

    bool cmp(int i, int len)

    {

        if(sa[i]+len > N || sa[i-]+len > N)

            return false;

        if(y[sa[i]] != y[sa[i-]] || y[sa[i]+len] != y[sa[i-]+len])

            return false;

        return true;

    }

    void baseSort()

    {

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

            sum[i] = ;

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

            sum[ x[ y[i] ] ] += ;

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

            sum[i] += sum[i-];

        for(int i=N-; i>=; i--)

            sa[ --sum[ x[ y[i] ] ] ] = y[i];

    }

    void GetSa()

    {

        baseSort();

        for(int len=; len<=N; len<<=)

        {

            int id = ;

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

                y[id++] = i;

            for(int i=; i<N; i++)if(sa[i] >= len)

                y[id++] = sa[i] - len;

            baseSort();

            swap(x, y);

            x[ sa[] ] = id = ;

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

            {

                if(cmp(i, len) == true)

                    x[ sa[i] ] = id;

                else

                    x[ sa[i] ] = ++id;

            }

            MaxId = id + ;

            if(MaxId >= N)break;

        }

    }

    void GetHeight()

    {

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

            rank[ sa[i] ] = i;

        for(int k=, i=; i<N; i++)

        {

            if(!rank[i])

            {

                height[] = k = ;

                continue;

            }

            if(k)k--;

            int pre = sa[ rank[i]- ];

            while(text[i+k] == text[pre+k])

                k++;

            height[rank[i]] = k;

        }

       /// debug();

    }

    void debug()

    {

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

            printf("%d: %d\n", i, height[i]);

    }

};

struct segmentTree

{

    int val[MAXN], L[MAXN], R[MAXN];

    void Build(int root, int l, int r, int p[])

    {

        L[root] = l, R[root] = r;

        if(l == r)

        {

            val[root] = p[l];

            return ;

        }

        int Mid = (l+r)>>;

        Build(root<<, l, Mid, p);

        Build(root<<|, Mid+, r, p);

        val[root] = min(val[root<<], val[root<<|]);

    }

    int  Query(int root, int u, int v)

    {

        if(L[root] == u && R[root] == v)

            return val[root];

        int Mid = (L[root]+R[root]) / ;

        if(v <= Mid)

            return Query(root<<, u, v);

        else if(u > Mid)

            return Query(root<<|, u, v);

        else

            return min(Query(root<<, u, Mid), Query(root<<|, Mid+, v));

    }

};

SuffixArr suf;

segmentTree seg;

char s[MAXN];

int main()

{

    while(scanf("%s", s) != EOF)

    {

        int len = strlen(s)+;

        suf.GetText(s);

        suf.GetSa();

        suf.GetHeight();

        seg.Build(, , suf.N-, suf.height);

        int MaxLen=, k=, x, y;

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

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

        {

            if(j==)

                x = suf.rank[len*-i-];

            else

                x = suf.rank[len*-i-];

            if(i== && j)continue;

            y = suf.rank[i+];

            if(x > y)swap(x, y);

            int m = seg.Query(, x+, y) *  + j;

            if(MaxLen < m)

            {

                MaxLen = m;

                k = i-(m+j)/+;

            }

        }

        s[k+MaxLen] = ;

        printf("%s\n", s+k);

    }

    return ;

}