[BZOJ1014/Luogu4036][JSOI2008]火星人prefix(字符串Hash,Splay,二分)

发布于 2018-04-01  95 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1014/Luogu4036][JSOI2008]火星人prefix(字符串Hash,Splay,二分)

Description

火星人最近研究了一种操作:求一个字串两个后缀的公共前缀。比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在,火星人定义了一个函数LCQ(x, y),表示:该字符串中第x个字符开始的字串,与该字符串中第y个字符开始的字串,两个字串的公共前缀的长度。比方说,LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程中,火星人发现了这样的一个关联:如果把该字符串的所有后缀排好序,就可以很快地求出LCQ函数的值;同样,如果求出了LCQ函数的值,也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速算法,但不甘心认输的地球人又给火星人出了个难题:在求取LCQ函数的同时,还可以改变字符串本身。具体地说,可以更改字符串中某一个字符的值,也可以在字符串中的某一个位置插入一个字符。地球人想考验一下,在如此复杂的问题中,火星人是否还能够做到很快地求取LCQ函数的值。

Tag

字符串Hash,Splay,二分

解决思路

想要求两个字符串的lcp,一种方法是把字符串后缀排序后,借助Height数组来求解。但是这样的缺点是不能支持修改操作。另一种就是二分长度+Hash判断。由于这里有对字符的修改和插入,所以采用二分+Hash的方式。
具体来说,相当于用Splay维护一个无序区间,对每一个点维护一个它子树内这段字符串的Hash值,每一次更改Splay形状的时候,顺便维护。那么,插入就把位置旋转到根再在后面插入,查询则把左端点的前一个转到根,右端点的后一个转到根的儿子,这样根的右儿子的左儿子就保存了需要的字符串Hash值。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ull unsigned long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100*4;
const ull hashbase=233;
const int inf=2147483647;

class SplayData
{
public:
    int size;
    int fa,ch[2];
    ull hash,key;
};

int n,nodecnt,root;
ull Hash[maxN];
SplayData S[maxN];
char Input[maxN];

void Update(int now);
void Rotate(int x);
void Splay(int x,int goal);
int Find(int kth);
void Insert(int pos,int key);
ull GetHash(int ql,int qr);

int main()
{
    ios::sync_with_stdio(false);
    Hash[0]=1;for (int i=1;i<maxN;i++) Hash[i]=Hash[i-1]*hashbase;

    cin>>(Input+1);
    int len=strlen(Input+1);
    //初始化Splay,直接把原字符串以一条链的形式放在Splay中。其实有更好的平衡方式,但是不想写啦
    //注意,这里为了方便操作,在两边分别加入了哨兵节点
    S[1].key=0;S[1].ch[1]=1;
    for (int i=1;i<=len;i++)
    {
        S[i+1].key=Input[i];
        S[i+1].fa=i;
        S[i].ch[1]=i+1;
    }
    S[len+2].key=0;S[len+1].ch[1]=len+2;S[len+2].fa=len+1;
    Splay(len+2,0);nodecnt=len+2;

    int m;cin>>m;//回答询问
    int L=strlen(Input+1);
    while (m--)
    {
        char opt;cin>>opt;
        if (opt=='Q')
        {
            int x,y;cin>>x>>y;
            if (x>y) swap(x,y);
            int l=1,r=L-y+1;
            int Ans=0;
            do//二分长度
            {
                int mid=(l+r)>>1;
                if (GetHash(x,x+mid-1)==GetHash(y,y+mid-1)) Ans=mid,l=mid+1;//截取Hash值判断
                else r=mid-1;
            }
            while (l<=r);
            cout<<Ans<<endl;
        }
        if (opt=='R')//修改
        {
            int x;char ch;cin>>x>>ch;
            x=Find(x+1);
            Splay(x,0);
            S[x].key=ch;Update(x);
        }
        if (opt=='I')//插入
        {
            int x;char ch;cin>>x>>ch;
            Insert(x,ch);L++;
        }
    }
    return 0;
}

void Update(int now)//Splay更新
{
    S[now].hash=S[S[now].ch[0]].hash*Hash[S[S[now].ch[1]].size+1]+S[now].key*Hash[S[S[now].ch[1]].size]+S[S[now].ch[1]].hash;
    S[now].size=S[S[now].ch[0]].size+S[S[now].ch[1]].size+1;
    return;
}

void Rotate(int x)
{
    int y=S[x].fa,z=S[y].fa;
    int sx=(x==S[y].ch[1]),sy=(y==S[z].ch[1]);
    S[x].fa=z;if (z) S[z].ch[sy]=x;
    S[y].ch[sx]=S[x].ch[sx^1];if (S[x].ch[sx^1]) S[S[x].ch[sx^1]].fa=y;
    S[y].fa=x;S[x].ch[sx^1]=y;
    Update(y);return;
}

void Splay(int x,int goal)
{
    while (S[x].fa!=goal)
    {
        int y=S[x].fa,z=S[y].fa;
        if (z!=goal)
            ((x==S[y].ch[0])^(y==S[z].ch[0])?(Rotate(x)):(Rotate(y)));
        Rotate(x);
    }
    Update(x);
    if (goal==0) root=x;
    return;
}

int Find(int kth)
{
    int now=root;
    while (1)
    {
        int l=S[now].ch[0];
        if (S[l].size>=kth) now=l;
        else if (S[l].size+1==kth) return now;
        else kth=kth-S[l].size-1,now=S[now].ch[1];
    }
}

void Insert(int pos,int key)
{
    int l=Find(pos+1),r=Find(pos+2);
    Splay(l,0);Splay(r,l);
    nodecnt++;
    S[nodecnt].key=key;S[nodecnt].fa=r;S[r].ch[0]=nodecnt;
    Splay(nodecnt,0);return;
}

ull GetHash(int ql,int qr)//得到[ql,qr]段内的hash值
{
    int l=Find(ql),r=Find(qr+2);
    Splay(l,0);Splay(r,l);
    return S[S[r].ch[0]].hash;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1014/Luogu4036][JSOI2008]火星人prefix(字符串Hash,Splay,二分)


HNCJ OIer