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?