Light OJ: 1347 – Aladdin and the Magical Lamp

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1347


Solution Idea:
###############
Solution idea for this problem is following-
1. Concatenate 3 input string one after another and make one single string.
2. Build Suffix array and store every step rank.
3. Run sliding window or two pointer on sorted suffix array and find the range in which 3 string presents. and determine the LCP of beginning and ending string of that range segment.
4. Largest LCP value find during step 3 is the answer.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


#define mx 30005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int c[mx];
//int LCP[mx],PLCP[mx],Phi[mx];
int P[18][mx],stp;
string str;
char s1[mx];
int n;

void counting_sort(int k)
{
    int maxi=max(300,n);
    ms(c,0);
    for(int i=0; i<n; i++)
    {
        int a=i+k<n?RA[i+k]:0;
        c[a]++;
    }
    for(int i=0,sum=0; i<maxi; i++)
    {
        int x=c[i];
        c[i]=sum;
        sum+=x;
    }

    for(int i=0; i<n; i++)
    {
        int a=SA[i]+k<n?RA[SA[i]+k]:0;
        int b=c[a];
        c[a]++;
        tempSA[b]=SA[i];
    }

    for(int i=0; i<n; i++)
        SA[i]=tempSA[i];
}

void build_Suffix_Array()
{
    stp=0;
    for(int i=0; i<n; i++)
    {
        RA[i]=str[i];
        SA[i]=i;
        P[stp][i]=RA[i];
    }

    stp++;

    for(int k=1; k<n; k*=2)
    {
        counting_sort(k);
        counting_sort(0);
        int r=0;
        tempRA[SA[0]]=r=0;
        for(int i=1; i<n; i++)
        {
            if(RA[SA[i]]==RA[SA[i-1]] && RA[SA[i]+k]==RA[SA[i-1]+k])
                tempRA[SA[i]]=r;
            else
                tempRA[SA[i]]=++r;
        }
        for(int i=0; i<n; i++)
        {
            RA[i]=tempRA[i];
            P[stp][i]=RA[i];
        }
        stp++;
        if(RA[SA[n-1]]==n-1) break;
    }
    stp--;
}


int find_lcp(int x, int y)
{
    int ret=0;
    if(x==y) return n-x;
    for(int k=stp; k>=0 && x<n && y<n; k--)
    {
        if(P[k][x]==P[k][y])
        {
            x+=(1<<k);
            y+=(1<<k);
            ret+=(1<<k);
        }
    }
    return ret;
}


int vis[5];

int getRange(int idx, int pos1, int pos2)
{
    if(idx<pos1) return 1;
    if(idx<pos2) return 2;
    return 3;
}



int main()
{

//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        str.clear();
        scanf("%s",s1);
        str+=string(s1);
        str+="@";
        int pos1=SZ(str)-1;
        scanf("%s",s1);
        str+=string(s1);
        str+="$";
        int pos2=SZ(str)-1;
        scanf("%s",s1);
        str+=string(s1);
        str+="#";
        n=SZ(str);
//        cout<<str<<endl;
        build_Suffix_Array();

//        for(int i=0; i<n; i++)
//            cout<<str.substr(SA[i])<<endl;

        int ans=0;

        int i=3,j=3;
        ms(vis,0);
        int cnt=0;
        while(j<n)
        {
            int a=getRange(SA[j],pos1,pos2);
            if(vis[a]==0)
            {
                cnt++;
            }
            vis[a]++;
            if(cnt==3)
            {
                int temp=find_lcp(SA[i],SA[j]);
                ans=max(ans,temp);
            }
            while(cnt>=3)
            {
                a=getRange(SA[i],pos1,pos2);
                vis[a]--;
                i++;
                if(vis[a]==0)
                    cnt--;
                if(cnt==3)
                {
                    int temp=find_lcp(SA[i],SA[j]);
                    ans=max(ans,temp);
                }
            }
            j++;
        }
        PRINT_CASE;
        pf("%d\n",ans);
    }


    return 0;
}


Advertisements