# Light OJ: 1347 – Aladdin and the Magical Lamp

0

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
/*------------------------------------------------*/

//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

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
/*------------------------------------------------*/

//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

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
/*------------------------------------------------*/

//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

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
/*------------------------------------------------*/

//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: SUBLEX – Lexicographical Substring Search

0

Solution Idea:

My solution for this problem is using suffix array and LCP array.
At first Build Suffix array and LCP array. Then find from which position of the suffix array you can get the K’th substring. Determine the position and determine the length for which it is the K’th smallest substring. Then print it.

We can get number of distinct substring using Suffix Array and LCP array. If you don’t know it how to do this job then solve this problem first.
SPOJ: DISUBSTR – Distinct Substrings

#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
/*------------------------------------------------*/

//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];
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++)
{
//        D(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);
string str1=str;
strcat(str,"\$");
n=strlen(str);
build_Suffix_Array();
build_LCP();

//        for(int i=0; i<n; i++)
//            cout<<SA[i]<<" ";
//        cout<<endl;
//        for(int i=0; i<n; i++)
//            cout<<LCP[i]<<" ";
//        cout<<endl;

int string_len=SZ(str1);

int q;
sf(q);
while(q--)
{
ll k;
sfl(k);
ll ans=0;
int pos=0,len=0;
for(int i=1;i<n;i++)
{
int temp=string_len-SA[i]-LCP[i];
if(ans+temp<k)
ans+=temp;
else
{
pos=SA[i];
len=ans+temp-k;
len=LCP[i]+temp-len;
break;
}
}
pf("%s\n",str1.substr(pos,len).c_str());
}

}

return 0;
}

# SPOJ: DISUBSTR – Distinct Substrings

1

Solution Idea: Build Suffix Array and LCP array. Then the answer will be subtraction of length of the ith suffix and LCP[i].

This works because LCP[i] holds the length of the longest common prefix of Suffix SA[i] and SA[i-1] where SA[] is suffix array.

Don’t forget to add an smaller extra or invalid symbol at the end of the string after taking input. Here I add a ‘\$’.

#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
/*------------------------------------------------*/

//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];
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++)
{
//        D(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();

//        for(int i=0; i<n; i++)
//            cout<<SA[i]<<" ";
//        cout<<endl;
//        for(int i=0; i<n; i++)
//            cout<<LCP[i]<<" ";
//        cout<<endl;

int ans=0;

int string_len=n-1;

for(int i=1; i<n; i++)
{
ans+=(string_len-SA[i]-LCP[i]);
}

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

}

return 0;
}

# UVa: 11512 – GATTACA

0

Solution Idea: Build Suffix array and LCP array then answer is the maximum entry in LCP array.

Lesson: Always use a ‘\$’ Symbol in this implementation of Suffix Array. Otherwise you will get nothing but WA -_- .

#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
/*------------------------------------------------*/

//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 count_sort[mx];
char str[mx],pattern[mx];

int Phi[mx],LCP[mx],PLCP[mx];

int n;

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

for(int i=0; i<n; i++)
{
int a=SA[i]+k<n?RA[SA[i]+k]:0;
int b=count_sort[a];
count_sort[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;
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 compute_LCP()
{
int l=0;
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])
{
//            D(str[i+L]);
//            D(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 find_pattern(int len)
{
int lo=0,hi=n-1;
while(lo<hi)
{
int mid=(lo+hi)/2;
int res=strncmp(str+SA[mid],pattern,len);
if(res>=0) hi=mid;
else
lo=mid+1;
}
ll ret=lo;
if(strncmp(str+SA[ret],pattern,len)!=0) return 0;
lo=0,hi=n-1;
while(lo<hi)
{
int mid=(lo+hi)/2;
int res=strncmp(str+SA[mid],pattern,len);
if(res>0) hi=mid;
else
lo=mid+1;
}

if(strncmp(str+SA[hi],pattern,len)!=0) hi--;
return hi-ret+1;
}

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);
string str1=str;
build_Suffix_Array();
//        for(int i=0; i<n; i++)
//            pf("%d\n",SA[i]);
compute_LCP();

//        for(int i=0; i<n; i++)
//            cout<<SA[i]<<" ";
//        cout<<endl;
//        for(int i=0; i<n; i++)
//            cout<<LCP[i]<<" ";
//        cout<<endl;

int ans=0;
for(int i=0; i<n; i++)
ans=max(ans,LCP[i]);
if(ans<=0)
{
pf("No repetitions found!\n");
continue;
}
int cnt=0,pos=0;
for(int i=0; i<n; i++)
{
if(LCP[i]==ans)
{
pos=i;
break;
}
}

strncpy(pattern,str+SA[pos],ans);

cnt=find_pattern(ans);

printf("%s %d\n",str1.substr(SA[pos],ans).c_str(),cnt);

}

return 0;
}

0

#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
/*------------------------------------------------*/

//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

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
/*------------------------------------------------*/

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

# UVa 1314 – Hidden Password

0

Solution Idea: Concatenate the input string with itself and find the suffix array. Answer will be the smallest string in suffix array which lie between index 0 to n-1 and which index is smaller.

#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
/*------------------------------------------------*/

//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));}
/*------------------------------------------------*/

char ara[100005];

struct data
{
pii rank;
int pos;
};

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

int suffix_ara[200005];

int position[200005];

int main()
{

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

int t;
sf(t);
TEST_CASE(t)
{
int n;
sf(n);
getchar();
gets(ara);
string str=ara;
str+=str;
n*=2;
for(int i=0;i<n;i++)
{
position[i]=str[i]-'a';
}

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

sort(all(v),cmp);

position[v[0].pos]=0;
suffix_ara[0]=v[0].pos;

for(int i=1;i<n;i++)
{
suffix_ara[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;
}
}

for(int i=0;i<n;i++)
{
if(suffix_ara[i]<n/2)
{
pf("%d\n",suffix_ara[i]);
//                pf("%s\n",str.substr(suffix_ara[i]).c_str());
break;
}
}
}

return 0;
}