utsav: It works fine, I did little bug fixing on boundaries as here goes : bool IsValid(string s) { for(int len=1;len<=s.size()/2;len++) { int start1=0,start2=len; while(start2<s.size()) { int i=0; for(;i<len && start2+i<s.size() && s[start1+i]==s[start2+i];i++); if(i>=len) return false; //"not valid" start1++; start2++; } } return true; // valid } It works for both input you provided. :)
On Mon, Jun 4, 2012 at 8:14 AM, utsav sharma <utsav.sharm...@gmail.com>wrote: > @jeevitesh :- yes i am also thinking of suffix tree, > but i am facing problem in implementing it. did you implement it ?? > > > On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma <utsav.sharm...@gmail.com>wrote: > >> @hassan :- it will not work for many strings as you are checking from the >> mid of strings. try out "ababcdef","aabc". >> @atul :- it should be done in O(n). >> >> >> On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared <hmonfa...@gmail.com>wrote: >> >>> yes it's not valid >>> >>> >>> On Sun, Jun 3, 2012 at 5:36 PM, anugrah <anugrah.agra...@gmail.com>wrote: >>> >>>> So any string with two same characters is not valid?? >>>> >>>> for example : >>>> >>>> GEEK has E followed by E. >>>> >>>> So GEEK is also invalid? >>>> >>>> On Jun 3, 1:49 pm, Hassan Monfared <hmonfa...@gmail.com> wrote: >>>> > bool IsValid(string s) >>>> > { >>>> > for(int len=0;len<s.len/2;len++) >>>> > { >>>> > int start1=0,start2=len+1; >>>> > while(start2<s.size()) >>>> > { >>>> > for(int i=0;i<len && start2+i<s.size() && >>>> > s[start1+i]=s[start2+i];i++); >>>> > if(i==len) >>>> > return false; //"not valid" >>>> > start1++; >>>> > start2++; >>>> > } >>>> > } >>>> > return true; // valid >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > } >>>> > On Sun, Jun 3, 2012 at 12:52 PM, atul anand <atul.87fri...@gmail.com> >>>> wrote: >>>> > > can be done with O(n^2) time complexity.. >>>> > >>>> > > can it be done with O(n) complexity ??? >>>> > >>>> > > On 6/3/12, utsav sharma <utsav.sharm...@gmail.com> wrote: >>>> > > > given a string tell wether it is valid or not. >>>> > > > string is valid if there is no substring which have the same >>>> substring >>>> > > > following it. >>>> > >>>> > > > these strings are not valid:- "stringstring","geek123123rt", >>>> > > > "abcadabcad","strngstingstrngsting" >>>> > >>>> > > > -- >>>> > > > 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. >>>> > >>>> > > -- >>>> > > 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. >>>> >>>> -- >>>> 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. >>>> >>>> >>> -- >>> 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. >>> >> >> > -- > 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. > -- 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.