AOJ2644 - Longest Match

ratingを上げるために新しい問題を解こうと思ったら、ちょうど練習したかったsuffix arrayの問題がありました。例外処理(文字列が存在しない場合)が難しく、とりあえず思いつく限りの条件を列挙したのでコードは汚いです。

問題：
Longest Match | Aizu Online Judge

問題概要：
文字列Sとm個のクエリが与えられる。それぞれのクエリについて文字列xと文字列yが与えられ、xで始まりyで終わるSの部分文字列の長さの最大値を求める。

解法：
suffix arrayとsegment treeを用いました。

コード：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#define mp make_pair
#define pb push_back
#define INF 100000005
#define rep(i,n) for(int i = 0;i < n;i++)
using namespace std;
int sa[200005],rk[200005],tmp[200005];

string S,T;
int kk;
int len;

int sg[2][1<<19];//[0]が最小値、[1]が最大値を保持

bool compare_sa(int i,int j){
    if(rk[i]!=rk[j]){
        return rk[i]<rk[j];
    }else{
        int ri = (i+kk<len)?rk[i+kk]:-1;
        int rj = (j+kk<len)?rk[j+kk]:-1;
        return ri<rj;
    }
}

void construct_sa(){
    len=(int)S.length();
    rep(i,len+1){
        sa[i]=i;
        rk[i]=(i<len)?S[i]:-1;
    }
    for(kk=1;kk<=len;kk*=2){
        sort(sa,sa+len+1,compare_sa);
        tmp[sa[0]]=0;
        for(int i = 1;i<=len;i++){
            tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
        }
        rep(i,len+1){
            rk[i]=tmp[i];
        }
    }
}

void update(bool f,int p,int x){//sg[f]のp番目にxを挿入
    p+=(1<<18)-1;
    sg[f][p]=x;
    while(p>0){
        p=(p-1)/2;
        sg[f][p]=(f?max(sg[f][p],x):min(sg[f][p],x));
    }
}

int query(bool f,int a,int b,int k,int l,int r){
    if(r<=a||b<=l)return f?-INF:INF;
    if(a<=l&&r<=b)return sg[f][k];
    else{
        int mid = (l+r)/2;
        int vl=query(f,a,b,k*2+1,l,mid);
        int vr=query(f,a,b,k*2+2,mid,r);
        int ret=(f?max(vl,vr):min(vl,vr));
        return ret;
    }
}

int query(bool f,int a,int b){
    return query(f,a,b,0,0,(1<<18));
}

int search(string t){
    int a=0,b=len+1;
    while(b-a>1){
        int c=(a+b)/2;
        if(S.compare(sa[c],T.length(),T)<0)a=c;
        else b=c;
    }
    return b;
}

int main(){
    cin>>S;
    rep(i,1<<19){
        sg[0][i]=INF;
        sg[1][i]=-INF;
    }
    construct_sa();
    rep(i,len+1){
        update(0,i,sa[i]);
        update(1,i,sa[i]);
    }

    int testcase;
    cin>>testcase;
    while(testcase--){
        int checkl;
        bool flag = 1;
        int ansl,ansr;
        int right,left;
        cin>>T;
        checkl=(int)T.length();
        left = search(T);
        T[T.length()-1]+=1;
        right=search(T);
        if(left==right)flag=0;
        ansl=query(0,left,right);

        cin>>T;
        left = search(T);
        T[T.length()-1]+=1;
        right=search(T);
        if(left==right)flag=0;
        ansr=query(1,left,right)+(int)T.length();
        if(ansl>len||ansl>=ansr)flag=0;
        if(ansr-ansl<checkl)flag=0;
        if(flag){
            cout<<ansr-ansl<<endl;
        }else{
            cout<<0<<endl;
        }
    }
}