A cool way of solving this is by using the suffix tree.
1. Concatenate the string with itself.
2. Create a suffix tree.
3. Descend along the least lexicographic path from the root.
Solution works in O(n).
On Jan 15, 4:55 pm, Jammy <xujiayiy...@gmail.com> wrote:
> @Wei Please test you code on "cdbbcbbca". I believe it outputs 2
> instead of 8.
>
> On Jan 14, 4:09 am, "Wei.QI" <qiw...@gmail.com> wrote:
>
>
>
>
>
>
>
> > FindStartIndex(char[] a)
> > {
> > int start = 0;
> > int current = 1;
> > while(current < a.Length)
> > {
> > if(a[current] < a[start])
> > {
> > start = current;
> > ++current;
> > }else if(a[current] > a[start])
> > {
> > ++current;
> > }else //a[current] == a[start]
> > {
> > int lookforward = 0;
> > int startnext = start;
> > int currentnext = current;
> > while(startnext != currnet && a[startnext] == a[currentnext])
> > {
> > ++lookforward;
> > startnext = (start + lookforward) % a.Length;
> > currentnext = (current + lookforward) % a.Length;
> > }//finish when compare to current head or there is different
> > if(startnext == current || a[startnext] < a[currentnext])
> > {
> > if(current > currentnext)
> > {
> > break;
> > }else
> > {
> > current = currentnext+1;
> > }
> > }
> > else //a[startnext] > a[currentnext]
> > {
> > start = current;
> > if(current < currentnext)
> > {
> > current = currentnext + 1;
> > }else
> > {
> > break;
> > }
> > }
> > }
> > }
> > return start;
>
> > }
>
> > On Fri, Jan 14, 2011 at 12:45 AM, radha krishnan <
>
> > radhakrishnance...@gmail.com> wrote:
> > > There s O(n) solution for this :)
>
> > > On Fri, Jan 14, 2011 at 2:13 PM, radha krishnan
> > > <radhakrishnance...@gmail.com> wrote:
> > > > append the string to original string and
> > > > index=answer of that spoj problem
> > > > now u can ouput the string from index to index+strlen(originalstring)-1
>
> > > > On Fri, Jan 14, 2011 at 2:12 PM, radha krishnan
> > > > <radhakrishnance...@gmail.com> wrote:
> > > >> wow
> > > >> This s a spoj problem
> > > >>http://www.spoj.pl/problems/MINMOVE/
>
> > > >> On Fri, Jan 14, 2011 at 1:40 PM, snehal jain <learner....@gmail.com>
> > > wrote:
> > > >>> Write the code to find lexicographic minimum in acirculararray, e.g.
> > > >>> for thearray
> > > >>> BCABDADAB, the lexicographic mininum is ABBCABDAD.
>
> > > >>> --
> > > >>> You received this message because you are subscribed to the Google
> > > Groups "Algorithm Geeks" group.
> > > >>> To post to this group, send email to algogeeks@googlegroups.com.
> > > >>> To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> > > .com>
> > > .
> > > >>> For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> > > .com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
