## Suffix Array

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
EduardoQuintana
Posts: 14
Joined: 8 years ago
Gender:

### Suffix Array

I found this document refering to Suffix Array (SA):
"(appeared in GInfo 15/7, November 2005) Suffix arrays – a programming contest approach Adrian Vladu and Cosmin Negruşeri"
The running time for this algorithm is O(n log^2 n).

It seems to me, problem "Casting Spells" (at "http://coj.uci.cu/24h/problem.xhtml?abb=2073") can be solved using SA.
I implemented the article's SA, but I got a "Time Limit Exceded".

Questions:
-Is it correct for this problem to use (given the time limits) SA? or there is another way?
-If it is correct to use SA in this problem: then how can I improve it?

L@grang3

ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

### Re: Suffix Array

You should know that there is an implementation practically O(n) for SA. Then, yes, you can improve your solution.
Grettings
"Every problem has a simple, fast and wrong solution" OJ's Main Law.

Spartan
Posts: 11
Joined: 8 years ago
Gender:

### Re: Suffix Array

would you write that efficient solution for us?

ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

### Re: Suffix Array

Code: Select all

``````//------------------------------- 2250 Substring Frequency - Using a Suffix Array (MAXN*K) + LCP
#define INVCICLE(i,a,b,c) for(int i = (a); i >= (b); i -= (c))
#define CICLE(i,a,b,c) for(int i=(a); i<=(b); i += (c))
#include <algorithm>
#define MAXN 2000002
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
inline bool leq(int a1, int a2, int b1, int b2) // lexicographic order
{ return(a1 < b1 || a1 == b1 && a2 <= b2); }                 // for pairs
inline bool leq(int a1, int a2, int a3, int b1, int b2, int b3)
{ return(a1 < b1 || a1 == b1 && leq(a2,a3, b2,b3)); }        // and triples
// stably sort a[0..n-1] to b[0..n-1] with keys in 0..K from r
static void radixPass(int* a, int* b, int* r, int n, int K)
{ // count occurrences
int* c = new int[K + 1];                          // counter array
for(int i = 0; i <= K; i++) c[i] = 0;            // reset counters
for(int i = 0; i < n; i++) c[r[a[i]]]++;      // count occurrences
for(int i = 0, sum = 0; i <= K; i++)      // exclusive prefix sums
{ int t = c[i]; c[i] = sum; sum += t; }
for(int i = 0; i < n; i++) b[c[r[a[i]]]++] = a[i];         // sort
delete [] c;
}
// find the suffix array SA of T[0..n-1] in {1..K}^n
// require T[n]=T[n+1]=T[n+2]=0, n>=2
void suffixArray(int* T, int* SA, int n, int K)
{
int n0 = (n+2)/3, n1 = (n+1)/3, n2 = n/3, n02 = n0 + n2;
int* R = new int[n02 + 3]; R[n02] = R[n02+1] = R[n02+2] = 0;
int* SA12 = new int[n02 + 3]; SA12[n02] = SA12[n02+1] = SA12[n02+2] = 0;
int* R0   = new int[n0];
int* SA0 = new int[n0];

//******* Step 0: Construct sample ********
// generate positions of mod 1 and mod 2 suffixes
// the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
for(int i=0, j=0; i < n+(n0-n1); i++) if(i%3 != 0) R[j++] = i;

//******* Step 1: Sort sample suffixes ********
// lsb radix sort the mod 1 and mod 2 triples
radixPass(SA12, R , T+1, n02, K);
radixPass(R,  SA12, T  , n02, K);
// find lexicographic names of triples and
// write them to correct places in R
int name = 0, c0 = -1, c1 = -1, c2 = -1;
for(int i = 0; i < n02; i++)
{
if(T[SA12[i]] != c0 || T[SA12[i]+1] != c1 || T[SA12[i]+2] != c2)

{ name++; c0 = T[SA12[i]]; c1 = T[SA12[i]+1]; c2 = T[SA12[i]+2]; }
if(SA12[i] % 3 == 1) { R[SA12[i]/3]      = name; } // write to R1
else                 { R[SA12[i]/3 + n0] = name; } // write to R2
}
// recurse if names are not yet unique
if(name < n02)
{
suffixArray(R, SA12, n02, name);
// store unique names in R using the suffix array
for(int i = 0; i < n02; i++) R[SA12[i]] = i + 1;
}
else // generate the suffix array of R directly
for(int i = 0; i < n02; i++) SA12[R[i] - 1] = i;

//******* Step 2: Sort nonsample suffixes ********
// stably sort the mod 0 suffixes from SA12 by their first character
for(int i=0, j=0; i < n02; i++) if(SA12[i] < n0) R0[j++] = 3*SA12[i];

//******* Step 3: Merge ********
// merge sorted SA0 suffixes and sorted SA12 suffixes
#define GetI() (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2)
for(int p=0, t=n0-n1, k=0; k < n; k++)
{
int i = GetI(); // pos of current offset 12 suffix
int j = SA0[p]; // pos of current offset 0 suffix
if(SA12[t] < n0 ? // different compares for mod 1 and mod 2 suffixes
leq(T[i],         R[SA12[t] + n0], T[j],        R[j/3]) :
leq(T[i], T[i+1], R[SA12[t]-n0+1], T[j], T[j+1],R[j/3+n0]))
{// suffix from SA12 is smaller
SA[k] = i; t++;
if(t == n02) // done --- only SA0 suffixes left
for(k++; p < n0; p++, k++) SA[k] = SA0[p];
}
else
{// suffix from SA0 is smaller
SA[k] = j; p++;
if(p == n0) // done --- only SA12 suffixes left
for(k++; t < n02; t++, k++) SA[k] = GetI();
}
}
delete [] R; delete [] SA12; delete [] SA0; delete [] R0;
}

void findLCP(int* T, int* SA, int* rank, int* lcp, int N)
{
int i, j, k=0;
CICLE(p,1,N,1) rank[SA[p]]=p;
for(i=0; i<N; lcp[rank[i++]]=k)
for(k ? k-- : 0, j=SA[rank[i]-1]; T[i+k]==T[j+k]; k++);
}

int T, LA, LB, N, K, A[MAXN], SA[MAXN], RANK[MAXN], LCP[MAXN];
int main()
{
scanf("%d",&T);
CICLE(t,1,T,1)
{
CICLE(p,0,N-1,1) A[p] = cad[p]; A[N] = A[N+1] = A[N+2] = 0;
suffixArray(A, SA, N+1, K = 260); findLCP(A, SA, RANK, LCP, N);
int pos = 1, res = 0; while(SA[pos] != LA+1) pos++;
while(pos < N && LCP[pos+1] >= LB) pos++, res++;
printf("Case %d: %d\n",t,res);
}
}
``````
This is submission http://coj.uci.cu/24h/submission.xhtml?id=369018 (with TLE answer, for that problem).

Best Regards, and bon appetit...
"Every problem has a simple, fast and wrong solution" OJ's Main Law.

HaZard
Posts: 114
Joined: 6 years ago
Location: Camagüey - Cuba
Gender:
Contact:

### Re: Suffix Array

tengo una duda y no sé si el Suffix Array sea la solucion:
teruel

ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

### Re: Suffix Array

Puede servir pero no es muy eficiente digamos.
Para ese tipo de problemas es más conveniente explotar el KMP en realidad.
"Every problem has a simple, fast and wrong solution" OJ's Main Law.