@hasan :-ohhh sorry, i didn't see the outer loop
yeah, it works but it is O(n^2), required solution is of O(n).
On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared <hmonfa...@gmail.com>wrote:
> 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.
>
--
Utsav Sharma,
NIT Allahabad
--
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.
