i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would prefer suffix array as
it is easier) traverse the each suffix till you encounter the first letter
of the suffix you are traversing and check to see this suppose i is the
index you found out the starting letter then check
s.substring(0,i)==s.substring(i,2i).
I hope you get the idea.
On Mon, Jun 4, 2012 at 9: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.
>
--
*Thanks,
Jeevitesh Shekhar Singh.*
--
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.
