the pseudo code can be like this:
func(string s) // returns an array a[]
int i=1;
int j=0;
int a[0]=0;
while(i<s.size()){
if(s[i]==s[j])
a[i]=j+1;
i++;
j++;
else if j>0 a[i]=a[j-1];
else a[i]=0; i++;
}
this can calculate the maxm repeated string. Next I can easily traverse the
array to check what is the maxm lenght and how many times it has repeated.
I think complexity is O(s.size*2).
On Fri, Feb 25, 2011 at 7:46 AM, Terence <[email protected]> wrote:
> @Dave: I think it is to find the longest substring which appears more than
> once in the given string.
>
> @bittu:
> You could use suffix tree: http://en.wikipedia.org/wiki/Suffix_tree, and
> find the deepest branch node.
> or use suffix array: http://en.wikipedia.org/wiki/Suffix_array, and find
> the length of common prefix of neighbouring elements, then choose the
> maximum.
>
>
> On 2011-2-25 1:46, Dave wrote:
>
>> @Bittu: Your statement of the problem doesn't make any sense.
>> Apparently, you are given a string and somehow that string is
>> repeated. Can you clarify it and give an example?
>>
>> Dave
>>
>> On Feb 24, 10:24 am, bittu<[email protected]> wrote:
>>
>>> Given a string (assume there no spaces or punctuations), write a
>>> program that returns the max. length of the string that has repeated
>>> more than once.
>>>
>>> Thanks
>>> Shashank
>>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
