I think it can be done by modifying the h-array and by making some changes
in KMP-algorithm
On Mon, Jun 4, 2012 at 9:35 AM, Jeevitesh <jeeviteshshekha...@gmail.com>wrote:
> 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.
>
--
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology
--
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.
