Moderator: Board moderators

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)
DJYA
New poster

Posts: 7
Joined: Sat Jan 10, 2004 10:18 pm

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

Posts: 1
Joined: Sun Mar 07, 2004 3:30 pm

Any more hint on the linear approach?
howardcheng
Learning poster

Posts: 70
Joined: Thu Aug 21, 2003 1:56 am

### 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
hackfox
New poster

Posts: 8
Joined: Fri Aug 08, 2003 9:39 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.
rskvijay
New poster

Posts: 3
Joined: Fri Mar 23, 2007 5:57 pm

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.
20717TZ
New poster

Posts: 21
Joined: Tue Apr 27, 2004 7:41 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;)
Angeh
Experienced poster

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

### 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
suneast
New poster

Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU

### 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

### 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

### 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.
zobayer
Experienced poster

Posts: 110
Joined: Tue May 06, 2008 2:18 pm

### 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.
DD
Experienced poster

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

### Re: 719 - Glass Beads

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

Posts: 147
Joined: Mon Jun 07, 2010 11:43 am

### Re: 719 - Glass Beads

What code do you use? By suneast?
quietroit
New poster

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

Previous