#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10000000
#include<stdlib.h>
#include<string.h>
char s[MAX];
int p[MAX];
int bucket[MAX],nbucket[MAX];
struct suffix
{
int idx;
}pos[MAX];
int H=0;
bool cmp(struct suffix i,struct suffix j)
{
if(H==0)
{
return s[i.idx]<s[j.idx];
}
else
{
if(bucket[i.idx]==bucket[j.idx])
{
return bucket[i.idx+H]<bucket[j.idx+H];
}
else
{
return bucket[i.idx]<bucket[j.idx];
}
}
}
bool cmp1(struct suffix *i,struct suffix *j)
{
if(H==0)
{
if(s[i->idx]==s[j->idx])
return true;
else
return false;
}else{
if(bucket[i->idx]==bucket[j->idx] && bucket[i->idx+H]==bucket[j->idx+H])
return true;
else
return false;
}
}
int update(int l)
{
int id=0,start=0,c=0;
for(int i=0;i<l;i++)
{
if(i>0 && !cmp1(&pos[i],&pos[i-1]))
{
id++;
start=i;
}
if(i!=start)
c=1;
nbucket[pos[i].idx]=id;
}
memcpy(bucket,nbucket,4*l);
return c;
}
void suffixsort(int l)
{
int i=0;
int c=0;
for(i=0;i<l;i++)
{
pos[i].idx=i;
}
sort(pos,pos+l,cmp);
c=update(l);
for(H=1;c;H*=2)
{
sort(pos,pos+l,cmp);
c=update(l);
}
return;
}
int main()
{
gets(s);
int l=strlen(s)+1;
suffixsort(l);
for(int i=1;i<l;i++)
printf("%d\n",pos[i].idx);
return 0;
}
easiest implementation of suffix array
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10000000
#include<stdlib.h>
#include<string.h>
char s[MAX];
int p[MAX];
int bucket[MAX],nbucket[MAX];
struct suffix
{
int idx;
}pos[MAX];
int H=0;
bool cmp(struct suffix i,struct suffix j)
{
if(H==0)
{
return s[i.idx]<s[j.idx];
}
else
{
if(bucket[i.idx]==bucket[j.idx])
{
return bucket[i.idx+H]<bucket[j.idx+H];
}
else
{
return bucket[i.idx]<bucket[j.idx];
}
}
}
bool cmp1(struct suffix *i,struct suffix *j)
{
if(H==0)
{
if(s[i->idx]==s[j->idx])
return true;
else
return false;
}else{
if(bucket[i->idx]==bucket[j->idx] && bucket[i->idx+H]==bucket[j->idx+H])
return true;
else
return false;
}
}
int update(int l)
{
int id=0,start=0,c=0;
for(int i=0;i<l;i++)
{
if(i>0 && !cmp1(&pos[i],&pos[i-1]))
{
id++;
start=i;
}
if(i!=start)
c=1;
nbucket[pos[i].idx]=id;
}
memcpy(bucket,nbucket,4*l);
return c;
}
void suffixsort(int l)
{
int i=0;
int c=0;
for(i=0;i<l;i++)
{
pos[i].idx=i;
}
sort(pos,pos+l,cmp);
c=update(l);
for(H=1;c;H*=2)
{
sort(pos,pos+l,cmp);
c=update(l);
}
return;
}
int main()
{
gets(s);
int l=strlen(s)+1;
suffixsort(l);
for(int i=1;i<l;i++)
printf("%d\n",pos[i].idx);
return 0;
}
ahmedhamdy 0 Light Poster
nitin1 15 Master Poster
nitin1 15 Master Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Gonbe 32 Newbie Poster
nitin1 15 Master Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
nitin1 commented: you are awesome, you are strict and you also teach well. :-D thanks a lot to you +2
nitin1 15 Master Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
nitin1 commented: awesome explaination! can't get this wording from anybody who is in contact of me :-) +2
nitin1 15 Master Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.