719 - Glass Beads

[DJYA]

It is possible to solve this problem in O(n).

Could anyone please give me more hint ?
I don't know how to do it in O(n)

[javier lira]

TLE in C++, i don't have more ideas , someone to help me or give me a hint, please!!!!!!

[howardcheng]

Any more hint on the linear approach?

[hackfox]

Hi javier lira,

You can try a case with aaaaa.....(repeat 10000 times)
or try a case with aaaaa...(5000 times)...bbbbb...(5000 times).

Remember that you don't need to scan from left to right for the start point with step 1 always.

If there are matches more than one characters, you can move to next start point with more steps.

--
The keypoint is that there is one string only

[rskvijay]

hav submitted this many times and i keep on getting wrong answer..
my program runs in O(n) time.. can i have some test cases plzzz??

thanx,
vijay.

[20717TZ]

Hi javier lira,

You can try a case with aaaaa.....(repeat 10000 times)
or try a case with aaaaa...(5000 times)...bbbbb...(5000 times).

Remember that you don't need to scan from left to right for the start point with step 1 always.

If there are matches more than one characters, you can move to next start point with more steps.

What do you mean "If there are matches more than one characters"? I cannot understand. Would mind give me a clear explanation, and give me the examples? Thanks.

I do have the case "aaaa...."(10000), and "aaaa....bbbb" as you mentioned. They are running slow because of my algorithm is O(n*n).

Thanks.

[Angeh]

I Need some Clear hints please .....
how to find the O(n) algorithm ...

[suneast]

hi , all :
I think I have a better O(N) solution using an Algorithm by "??(ZhouYuan)" called "?????(Minimum Expression)" in Chinese..

Code: Select all

@ double the string -> str[] = "String""String"
@ i=0 j=1 k=0 len=str.length()
   while(i<len && j<len)
      # if(str[i+k] == str[j+k]) { k++; if(k==len) break; }
      # if(str[i+k] > str[j+k])  { i=i+k+1;  if(i<=j) i=j+1; k=0; }
      # if(str[i+k] < str[j+k])  { j=j+k+1; if(j<=i) j=i+1; k=0; }

   return Min(i,j)

A simple code using O(N)time above will solve the problem

if U want to know more details about the algorithm, you can search the Internet using keyword "?? ?????" (in Chinese)

Hope I'm help to you all

[zobayer]

I am getting wrong answer. I used suffix array to solve the problem. This is my algorithm: I concatenate the string with the original one and then construct the sorted suffix array. The first suffix starting in the first string is the answer. Is there anything wrong with this approach? Can there be words of 0 length?
Thanks in advance...

[zobayer]

Got AC!
The case was "aaaa", how could I miss such a trivial case
Input is nice. No blank line or anything.

[zobayer]

hi , all :
I think I have a better O(N) solution using an Algorithm by "??(ZhouYuan)" called "?????(Minimum Expression)" in Chinese..

A simple code using O(N)time above will solve the problem

if U want to know more details about the algorithm, you can search the Internet using keyword "?? ?????" (in Chinese)

Hope I'm help to you all

Damn this is cool, I got AC with both Suffix Array and yours algorithm. My suffix array implementation was also O(n). But considering the coding complexity, suffix array is a shit when compared to this... Thanks for sharing!

[DD]

I am curios how to use suffix array to solve this problem since it also needs sorting which needs O(nlogn) time. I solved this problem by the aforementioned minimum expression. That algorithms is really cool , looks like a twist of Boyer-Moore string matching algorithm.

[Shafaet_du]

With same code i got ac in spoj,live archive but getting TLE in uva. why??

[quietroit]

What code do you use? By suneast?

[Repon kumar Roy]

WHY RTE ??
COULD not FIND ANY ERROR...

Code: Select all

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				400006
#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
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define msg(x)			cout<<x<<endl;
#define EPS				1e-7
/*---- 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 ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/


#define LG 21
char A[LMT];
struct entry {
	int nr[2], p;
} L[LMT] , T[ LMT ];
int P[LG][LMT], N, i, stp, cnt;
int counterAray[LMT];
int prefixArray[LMT];

int cmp(struct entry a, struct entry b)
{
	return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
	
}

void countingSort (entry v[] , int index , int len )
{
	int iM = -100;
	for(int  i = 0 ; i < len ; i ++ ){
		iM = max(iM , v[i].nr[index] + 1);
	}
	
	
	memset(counterAray ,0, (iM + 1) * sizeof(int));
	for(int i = 0 ; i< len; i ++ ) {
		counterAray[v[i].nr[index] + 1] ++;
	}
	
	prefixArray[0] = counterAray[0];
	for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
		prefixArray[i] = counterAray[i] + prefixArray[i-1];
	}
	
	for (int i = len - 1; i >=0 ; i -- ) {
		prefixArray[v[i].nr[index] + 1] --;
		
		if( prefixArray[v[i].nr[index] + 1] < 0 ) {
			printf("ARRAY LESS\n");
		}
		T[prefixArray[v[i].nr[index] + 1]] = v[i];
	}
	
	for(int i = 0 ;i <len; i ++ ) v[i] = T[i];
	
}
void buildSA()
{
	
	for (N = strlen(A), i = 0; i < N; i ++)
		P[0][i] = A[i] - 'a';
	for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
	{
		for (i = 0; i < N; i ++)
		{
			L[i].nr[0] = P[stp - 1][i];
			L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
			L[i].p = i;
		}
		//countingSort(L , 1 , N);
		//countingSort(L , 0 , N );
		
		sort(L, L + N , cmp);
		for (i = 0; i < N; i ++)
			P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;
		
		
	}
}

int lcp(int x, int y)
{
	int k, ret = 0;
	if (x == y) return N - x;
	for (k = stp - 1; k >= 0 && x < N && y < N; k --){
		
		if( k >= LG ) {
			printf("LHSLHDD\n");
		}
		if (P[k][x] == P[k][y])
			x += 1 << k, y += 1 << k, ret += 1 << k;
	}
	return ret;
	
}

int main()
{
	int tc;
	
	//freopen("in.txt", "r", stdin);
	sc(tc);
	
	while (tc -- ) {
		scanf("%s",A);
		strcat(A, A );
		
		buildSA();
		int ans = -1;
		for(int i = 0; i < N -1  ; i ++ ) {
			if(L[i].p < N/2 ) {
				if(ans ==-1 ) ans = L[i].p;
				
				if(lcp( ans ,  L[i + 1].p ) >= N / 2 ) {
					if( ans > L[i+1]. p ) ans = L[i+1].p;
				}
			}
		}
		
		printf("%d\n", ans + 1 );
	}
}