1314 - Hidden Password

[Repon kumar Roy]

I am using Suffix Array Structure ..
I am learning this string approach ... Tried to solve this one But WA
Here is my code....

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
#include <map>
using namespace std;

/*------- Constants---- */
#define MX 100009
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
/* -------Global Variables ------ */
ll euclid_x,euclid_y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline void extended_euclid_returning_gcd(T a,T b){ if(b==0){d = a;euclid_x=1;euclid_y=0;} else {extended_euclid_returning_gcd(b, a%b);
	T x1 = euclid_y; T y1 = euclid_x - (a / b) * euclid_y ; euclid_x = x1 ; euclid_y = y1 ;}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}
int N ;
string S ;
int pos[MX];
int SA[MX];
int tmp[MX];
int gap;

int sufcmp(int i , int j)
{
      if( pos[i] != pos[j]) {
            return pos[i] < pos[j];
      }else {
            i += gap;
            j +=gap;
            
            return pos[i%N] < pos[j%N];
      }
}
void buildSA()
{
      for(int i = 0 ; i < N ; i ++) {
            SA[i] = i  ;
            pos[i] = S[i ];
      }
      
      for (gap = 1; gap < N ; gap *=2) {
            sort(SA, SA + N, sufcmp);
            
            for(int i = 0 ; i < N-1 ; i ++){
                  tmp[i+1] = tmp[i] + sufcmp(SA[i] , SA[i + 1]);
            }
            for( int i = 0 ; i < N; i ++ ){
                  pos[SA[i]] = tmp[i];
            }
            if( tmp[N- 1] == N-1) break;
      }
      
      
}
int main()
{
      
      int T ;
      cin >> T ;
      while (T -- ) {
            cin>> N >>S ;
            S = S;
            buildSA();
            printf("%d\n",SA[0]);
            ms(tmp, 0);
            
      }
}

Again , Any link to learn suffix array will be appreciated

[brianfry713]

You can solve this problem in O(L) per test case without using SA.
Just iterate through the string keeping track of the best starting position.
Input:

Code: Select all

1
20 riverriverriverriver

AC output: 3

[Repon kumar Roy]

Now getting RE ??

Code: Select all

#define MX 4000006
char S[MX];
int main()
{
      
      int T , N ;
      cin >> T ;
      int best = 0;
      while (T -- ) {
            cin>> N >> S ;
            strcat(S, S);
            best = 0;
            for(int i = 1 ; i < N ; i ++){
                  int res = strncmp(S + best, S + i , N);
                  if( res > 0 ){
                        best = i;
                  }
            }
            cout << best << endl;
  
            
      }
}

[Repon kumar Roy]

Hi , Brian fry

Code: Select all

1
20 riverriverriverriver

I get 3 in my mac machine ..

But getting 18 in ideone ?? Why this ??

[brianfry713]

Your second RE code won't compile without the #include statements. Post the code you'd actually submit.

That code doesn't run in O(L), try it with a string of 100000 of the same char.

I don't know why your other compiler is getting different results, it usually means you have some uninitialized data or you are reading/writing outside of array bounds. Try inserting some temporary debug print statements and looking for the difference. You should test your code using g++, the same as the judge.