程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> URAL 1297 後綴數組：求最長回文子串

URAL 1297 後綴數組：求最長回文子串

編輯：C++入門知識

URAL 1297 後綴數組：求最長回文子串

思路：這題下午搞了然後一直WA，後面就看了Discuss，裡面有個數組：ABCDEFDCBA，這個我輸出ABCD，所以錯了。

然後才知道自己寫的後綴數組對這個回文子串有bug，然後就不知道怎麼改了。

然後看題解，裡面都是用RMQ先預處理任意兩個後綴的最長公共前綴，因為不太知道這個，所以又看了一下午，嘛嘛……

然後理解RMQ和後綴一起用的時候才發現其實這裡不用RMQ也可以，只要特殊處理一下上面這個沒過的例子就行了，哈哈……機智……

不過那個國家集訓隊論文裡面正解是用RMQ做的，自己還得會和RMQ一起使用才得，在別的題目裡面也是要用的。

這個是不用RMQ做的：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 4010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
void radix(int *str,int *a,int *b,int n,int m)
{
    static int count[maxn];
    mem(count,0);
    for(int i=0; i=0; i--) b[--count[str[a[i]]]]=a[i];
}
void suffix(int *str,int *sa,int n,int m) 
{
    static int rank[maxn],a[maxn],b[maxn];
    for(int i=0; i=n?0:rank[j+(1<>s)
    {
        string str;
        for(int i=s.size()-1; i>=0; i--)
            str+=s[i];
        str=s+"#"+str;
        copy(str.begin(),str.end(),a);
        int n=str.size();
        suffix(a,sa,n,n+256);
        calcHeight(a,sa,height,n);
        int len=0,pos=1;
        for(int i=1; ilen)
                {
                    len=height[i];
                    pos=min(sa[i],sa[i-1]);
                }
                else if(height[i]==len)
                    pos=min(pos,min(sa[i],sa[i-1]));
            }
        if(len>1) cout<