Moderator: Board moderators

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 1314 - Hidden Password

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1314 - Hidden Password

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
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 1314 - Hidden Password

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
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 1314 - Hidden Password

Hi , Brian fry

Code: Select all

1
20 riverriverriverriver
I get 3 in my mac machine ..

But getting 18 in ideone ?? Why this ??

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1314 - Hidden Password

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.
Check input and AC output for thousands of problems on uDebug!