Moderator: Board moderators

DJYA
New poster
Posts: 7
Joined: Sat Jan 10, 2004 10:18 pm
Adrian Kuegel wrote: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
New poster
Posts: 1
Joined: Sun Mar 07, 2004 3:30 pm

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

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
Any more hint on the linear approach?

hackfox
New poster
Posts: 8
Joined: Fri Aug 08, 2003 9:39 pm

### Try a sequence of 10000 'a'

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
New poster
Posts: 3
Joined: Fri Mar 23, 2007 5:57 pm
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
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:
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.
I Believe I Can - leestime.com

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 719 - Glass Beads

I Need some Clear hints please .....
how to find the O(n) algorithm ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 719 - Glass Beads

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
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 719 - Glass Beads

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?
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 719 - Glass Beads

Got AC!
The case was "aaaa", how could I miss such a trivial case
Input is nice. No blank line or anything.
Last edited by zobayer on Wed Feb 16, 2011 10:43 am, edited 1 time in total.
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 719 - Glass Beads

suneast wrote: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!
You should not always say what you know, but you should always know what you say.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 719 - Glass Beads

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.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 719 - Glass Beads

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

quietroit
New poster
Posts: 2
Joined: Wed Nov 02, 2011 9:06 pm

### Re: 719 - Glass Beads

What code do you use? By suneast?

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

### Re: 719 - Glass Beads

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 );
}
}