Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com

And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Friday, June 17, 2016

SUBLEX - Lexicographical Substring Search

Lexicographical Substring Search


Given below code is for sublex spoj or Lexicographical substring search spoj.

Hint :-



It can be done using Suffix array and LCP array.
Let p[] denote suffix array lcp[] denote LCP array.
create a array which store the number of distinct sub string till i'th rank suffix. This can be calculated using this formula. For more details see Here 
 

Let cum[] denote cumulative array which can be calculated as follow:


cum[0] = n - p[0];
for i = 1 to n do:
    cum[i] = cum[i-1] + (n - p[i] - lcp[i])

Now for finding i'th sub string just find the lower bound of i in cumulative array cum[] that will give you rank of suffix from where your sub string should start and print all character till length of


i - cum[pos-1] + lcp[pos] // i lies between cum[pos-1] and cum[pos] so for finding 
                          // length of sub string starting from cum[pos-1] we should 
                          // subtract cum[pos-1] from i and add lcp[pos] as it is 
                          // common string between current rank suffix and 
                          // previous rank suffix. 
where pos is value return by lower bound.
Whole above process can be summarized as follow:
string ithSubstring(int i){
    pos = lower_bound(cum , cum + n , i);
    return S.substr(arr[pos] , i - cum[pos-1] + lcp[pos]);// considering S as original character string 
}

C++ code for above logic:-

#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
#define LL long long 
int Rank[20][MAX];
int arr[100000],cum[100000],lcp[100000];
struct Tuple
{
    int left,right,pos;
};
bool compare(const Tuple &a, const Tuple &b)
{
    return a.left == b.left ? a.right < b.right : a.left < b.left;
}
void counting_sort(Tuple t[] , int n)
{
    int count[MAX+9];
    Tuple temp[n + 9];
    memset(count , 0 , sizeof count);

    for(int i = 0 ;i < n ; i++)
        count[t[i].right + 1]++;

    for(int i = 1 ; i  < MAX ; i++)
        count[i] += count[i-1];

    for(int i = 0 ; i<n ; i++)
    {
        temp[count[t[i].right +1] - 1] = t[i];
        count[t[i].right + 1]--;
    }   

    memset(count , 0 , sizeof count);

    for(int i = 0 ; i < n ; i ++)
        count[t[i].left + 1] ++;

    for(int i = 1 ; i<MAX ; i++)
        count[i] += count[i-1];

    for(int i = n- 1; i>=0 ; i--)
    {
        t[count[temp[i].left + 1] - 1] = temp[i];
        count[temp[i].left + 1]--;
    }
}
void suffix_array(char s[],int n)
{

    for(int i=0;i<n;i++)
        Rank[0][i] = s[i] - 97;

    Tuple t[n+9];


    for(int stp = 1 , cnt = 1 ; (cnt>>1) < n ; cnt<<=1 , stp++)
    {
        for(int i=0;i<n;i++)
        {
            t[i].left = Rank[stp-1][i];
            t[i].right = i+cnt < n ? Rank[stp-1][i + cnt] : -1;
            t[i].pos = i;
        }
        //sort(t,t+n,compare);
        counting_sort(t , n);
        for(int i=0;i<n;i++)
            Rank[stp][t[i].pos] = i > 0 && t[i-1].left == t[i].left && t[i-1].right == t[i].right ? Rank[stp][t[i-1].pos] : i;
    }
    int pos = ceil(log(n)/log(2));
    for(int i = 0;i<n;i++)
        arr[Rank[pos][i]] = i;
}
void lcpArray(char s[],int n)
{
        int k=0,sum = 0;
        vector<int> rank(n,0);
        for(int i=0; i<n; i++) rank[arr[i]]=i;
                lcp[0] = 0;
        for(int i=0; i<n; i++, k?k--:0)
        {
                if(rank[i]==n-1) {k=0; continue;}
                int j=arr[rank[i]+1];
                while(i+k<n && j+k<n && s[i+k]==s[j+k]) k++ ;
                lcp[rank[i] + 1] = k;
        }
}
int main()
{
    char s[100000];
    scanf("%s",s);
    int  n = strlen(s);
    suffix_array(s,n);
    lcpArray(s , n);
    cum[0] = n - arr[0];
    for(int i = 1;i < n;i++){
        cum[i] = cum[i-1] + (n - arr[i] - lcp[i]);
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int a ;
        scanf("%d",&a);
        int pos ;
        pos = lower_bound(cum , cum + n , a) - cum;
        int i , j;
        for(int j = 0 , i = arr[pos] ; j< a - cum[pos-1] + lcp[pos] ; j++,i++)
            printf("%c",s[i]);
        printf("\n");
    }
    return 0;
}

1 comment:

Your comment is valuable to us