Light OJ: 1347 – Aladdin and the Magical Lamp

0

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;
}


Light OJ: 1314 – Names for Babies

0

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


Solution Idea:

Build Suffix array and LCP array. Then find the distinct substring using LCP arrray by the formula (Length of the suffix – LCP of this and the previous suffix). But in this problem we need to calculate the length which lie in the given range. Think about it.


#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 100005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int c[mx];
int LCP[mx],PLCP[mx],Phi[mx];
//int P[18][mx];
char str[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()
{
    for(int i=0; i<n; i++)
    {
        RA[i]=str[i];
        SA[i]=i;
    }

    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];
        }
        if(RA[SA[n-1]]==n-1) break;
    }
}

void build_LCP()
{
    Phi[SA[0]]=-1;
    for(int i=1; i<n; i++)
        Phi[SA[i]]=SA[i-1];
    for(int i=0,L=0; i<n; i++)
    {
        if(Phi[i]==-1)
        {
            PLCP[i]=0;
            continue;
        }
        while(str[i+L]==str[Phi[i]+L]) L++;
        PLCP[i]=L;
        L=max(L-1,0);
    }

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



int main()
{

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

    int t;
    sf(t);
    TEST_CASE(t)
    {
        scanf("%s",str);
        strcat(str,"$");
        n=strlen(str);
        build_Suffix_Array();
        build_LCP();


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

        int a,b;
        sff(a,b);

        int ans=0;
        for(int i=1;i<n;i++)
        {
            int len=n-SA[i]-1;
            int temp=len-LCP[i];
            if(len>b)
                temp-=(len-b);
            if(LCP[i]<a)
                temp-=(a-LCP[i]-1);
            temp=max(temp,0);
            ans+=temp;
        }

        PRINT_CASE;
        pf("%d\n",ans);

    }

    return 0;
}


SPOJ: LCS – Longest Common Substring

0

Problem Link : http://www.spoj.com/problems/LCS/


Solution Idea:

This is the problem no 6 on Suffix array paper .
The question need to find the maximum value of LCP[] array between two consecutive suffixes where this two consecutive suffixes are from different input string.


#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 500005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int c[mx];
int Phi[mx],PLCP[mx],LCP[mx];
char str[mx],str1[mx];
int n;

void counting_sort(int k)
{
    int maxi=max(n,300);
    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_SA()
{
    for(int i=0; i<n; i++)
    {
        RA[i]=str[i];
        SA[i]=i;
    }

    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];

        if(RA[SA[n-1]]==n-1) break;
    }
}

void build_LCP()
{
    Phi[SA[0]]=-1;
    for(int i=1; i<n; i++)
        Phi[SA[i]]=SA[i-1];
    for(int i=0,L=0; i<n; i++)
    {
        if(Phi[i]==-1)
        {
            PLCP[i]=0;
            continue;
        }
        while(str[i+L]==str[Phi[i]+L]) L++;
        PLCP[i]=L;
        L=max(L-1,0);
    }

    for(int i=0; i<n; i++)
        LCP[i]=PLCP[SA[i]];

}

int main()
{

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

    int pos;

    scanf("%s %s",str,str1);
    strcat(str,"$");
    pos=strlen(str)-1;
    strcat(str,str1);
    strcat(str,"#");
    n=strlen(str);
    build_SA();
    build_LCP();
//    string ss=str;
//    for(int i=0;i<n;i++)
//        cout<<SA[i]<<" ";
//    cout<<endl;
//    for(int i=0;i<n;i++)
//        cout<<LCP[i]<<" ";
//    cout<<endl;
//    for(int i=0;i<n;i++)
//        cout<<ss.substr(SA[i])<<endl;

    int ans=0;

    for(int i=1; i<n; i++)
    {
        if((SA[i]<pos && (SA[i-1]>pos)) || ((SA[i]>pos && SA[i-1]<pos)))
        {
            ans=max(ans,LCP[i]);
        }
    }

    pf("%d\n",ans);

    return 0;
}


UVa 760 – DNA Sequencing

0

Problem Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=701


Solution Idea:
1. Concatenate two string then build suffix array and LCP array.
1. Now find those position in LCP array where two consecutive suffix is from two
different input string.
3. Now take the maximum of LCP[these indexes]
4. After that generate string from this position with the determined maximum
length value.
5. Print the distinct strings from these strings.


#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 1005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int c[mx];
int LCP[mx],PLCP[mx],Phi[mx];
char str[mx],str1[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()
{
    for(int i=0; i<n; i++)
    {
        RA[i]=str[i];
        SA[i]=i;
    }

    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];
        }
        if(RA[SA[n-1]]==n-1) break;
    }
}

void build_LCP()
{
    Phi[SA[0]]=-1;
    for(int i=1; i<n; i++)
        Phi[SA[i]]=SA[i-1];
    for(int i=0,L=0; i<n; i++)
    {
        if(Phi[i]==-1)
        {
            PLCP[i]=0;
            continue;
        }
        while(str[i+L]==str[Phi[i]+L]) L++;
        PLCP[i]=L;
        L=max(L-1,0);
    }

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

map<string,bool>mp;

int main()
{

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

    bool check=0;
    while(scanf("%s",str)!=EOF)
    {
        scanf("%s",str1);
        strcat(str,"$");
        int l1=strlen(str)-1;
        strcat(str,str1);
        strcat(str,"#");
        n=strlen(str);
        build_Suffix_Array();
        build_LCP();
        string str2=str;
        int ans=0,maxi=0;

        if(check)
            pf("\n");
        check=1;

//        for(int i=0;i<n;i++)
//            cout<<SA[i]<<" ";
//        cout<<endl;
//        for(int i=0;i<n;i++)
//            cout<<LCP[i]<<" ";
//        cout<<endl;
//
//        for(int i=0;i<n;i++)
//        {
//            cout<<str2.substr(SA[i])<<endl;
//        }
//        cout<<endl;

        for(int i=1; i<n; i++)
        {
            if((SA[i]<l1 && SA[i-1]<n && SA[i-1]>l1) || (SA[i]>l1 && SA[i]<n && SA[i-1]<l1))
                maxi=max(maxi,LCP[i]);
        }

        if(maxi==0)
        {
            pf("No common sequence.\n");
            continue;
        }

        mp.clear();

        for(int i=1; i<n; i++)
        {
            if((SA[i]<l1 && SA[i-1]<n && SA[i-1]>l1)|| (SA[i]>l1 && SA[i]<n && SA[i-1]<l1))
            {
                if(LCP[i]==maxi)
                {
                    string temp=str2.substr(SA[i],maxi);
                    if(mp[temp]) continue;
                    else
                        mp[temp]=1;
                    printf("%s\n",temp.c_str());
                }
            }
        }
    }


    return 0;
}


SPOJ: BEADS – Glass Beads

0

Problem Link : http://www.spoj.com/problems/BEADS/


#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 101005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int cnt_sort[mx];
char T[mx];
string str;
int n;

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

    for(int i=0,sum=0;i<maxi;i++)
    {
        int x=cnt_sort[i];
        cnt_sort[i]=sum;
        sum+=x;
    }

    for(int i=0;i<n;i++)
    {
        int a=SA[i]+k<n?RA[SA[i]+k]:maxi-1;
        int x=cnt_sort[a];
        cnt_sort[a]++;
        tempSA[x]=SA[i];
    }

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

void build_Suffix_Array()
{
    for(int i=0;i<n;i++)
    {
        RA[i]=str[i];
        SA[i]=i;
    }
    for(int k=1;k<n;k*=2)
    {
        counting_sort(k);
        counting_sort(0);
        tempRA[SA[0]]=0;
        int 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];
        if(RA[SA[n-1]]==n-1)break;
    }

//    for(int i=0;i<n;i++)
//        pf("%s\n",str.substr(SA[i]).c_str());
}

int main()
{

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

    int t;
    sf(t);
    TEST_CASE(t)
    {
        scanf("%s",T);
        str.clear();
        str=T;
        str+=str;
        n=SZ(str);
//        cout<<str<<endl;
        build_Suffix_Array();
        for(int i=0;i<n;i++)
        {
            if(SA[i]<n/2)
            {
                pf("%d\n",SA[i]+1);
                break;
            }
        }
    }

    return 0;
}


UVa 10679 – I Love Strings!!

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620

Solution Idea: Build Suffix Array then binary search on the sorted sequence.


#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 100005

int suffix_array[mx],position[mx];

struct data
{
    pii rank;
    int pos;
};

bool cmp(data a, data b)
{
    return a.rank<b.rank;
}

char str[mx],query[mx];

int main()
{

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

    int t;
    sf(t);
    TEST_CASE(t)
    {
        scanf("%s",str);

        int n=strlen(str);

        for(int i=0;i<n;i++) position[i]=str[i];

        for(int k=1;k<n;k*=2)
        {
            vector<data>v(n);
            for(int i=0;i<n;i++)
            {
                int a=position[i];
                int b;
                if(i+k>=n)
                    b=-1;
                else
                    b=position[i+k];
                v[i].rank=pii(a,b);
                v[i].pos=i;
            }

            sort(all(v),cmp);

            position[v[0].pos]=0;
            suffix_array[0]=v[0].pos;
            for(int i=1;i<n;i++)
            {
                suffix_array[i]=v[i].pos;
                if(v[i].rank==v[i-1].rank)
                    position[v[i].pos]=position[v[i-1].pos];
                else
                    position[v[i].pos]=i;
            }
        }

        int q;
        sf(q);
        while(q--)
        {
            scanf("%s",query);
            int l=strlen(query);
            int lo=0,hi=n-1;
            bool ans=0;
            while(lo<=hi)
            {
                int mid=(lo+hi)/2;
                int x=strncmp(str+suffix_array[mid],query,l);
                if(x==0)
                {
                    ans=1;
                    break;
                }
                else if(x>0)
                    hi=mid-1;
                else
                    lo=mid+1;
            }
            if(ans)
                pf("y\n");
            else
                pf("n\n");
        }
    }

    return 0;
}