* tree substrings*
tree-->|---mississippi m .. mississippi
|
|---i-->|---ssi-->|---ssippi i .. ississippi
| | |
| | |---ppi issip,issipp,issippi
| |
| |---ppi ip, ipp, ippi
|
|---s-->|---si-->|---ssippi s .. ssissippi
| | |
| | |---ppi ssip, ssipp, ssippi
| |
| |---i-->|---ssippi si .. sissippi
| |
| |---ppi sip, sipp, sippi
|
|---p-->|---pi p, pp, ppi
|
|---i p, pi
*--- Suffix Tree for "mississippi" ---*
in this example, any bifurcation implies that the substring is repeated(eg
i, s, ss, si, p, issi) and looks like this problem can be done while
forming the suffix trie
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Tue, Jun 5, 2012 at 12:28 AM, Abhishek Sharma <abhi120...@gmail.com>wrote:
> 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.
>
--
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.
