«

What is best solution for finding "a repeatedly occuring lenghtiest sub
SEQUENCE from a given paragraph"

ex:
input:
hello world is a good hello world. Is that the way it is
a way.
Output:
hello world

"Spidey" <> wrote in message
news: oups.com...
> What is best solution for finding "a repeatedly occuring lenghtiest sub
> SEQUENCE from a given paragraph"

The 'best solution' in the context of this newsgroup is
to write a C program to do it.

>
> ex:
> input:
> hello world is a good hello world. Is that the way it is
> a way.
> Output:
> hello world

Nobody is going to write the code for you, however if
you post your best attempts (code) accompanied by specific
questions, you'll get plenty of help.

-Mike

"Spidey" <> wrote in message
news: oups.com...
> What is best solution for finding "a repeatedly occuring lenghtiest sub
> SEQUENCE from a given paragraph"
>
> ex:
> input:
> hello world is a good hello world. Is that the way it is
> a way.
> Output:
> hello world
>

It's reasonably difficult, as you're looking for n-gram frequency. So,
there's text chunking to do, and more than a little strtok'ing etc.

Have a look around some Computational Linguistics sites - hint: there are
tools on the web to do this (not neccessarily in C, or with source code
though)

"Spidey" <> wrote
> What is best solution for finding "a repeatedly occuring lenghtiest sub
> SEQUENCE from a given paragraph"
>
> ex:
> input:
> hello world is a good hello world. Is that the way it is
> a way.
> Output:
> hello world
>
It's a programming problem rather than a C program.
Look up "dot plot" and "protein sequence" in Google for an example of a
real-life application of this problem.

On 26 Nov 2005 22:08:15 -0800, in comp.lang.c , "Spidey"
<> wrote:

>What is best solution for finding "a repeatedly occuring lenghtiest sub
>SEQUENCE from a given paragraph"

This is an algorithms question. Try asking in comp.programming.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Spidey wrote:
> What is best solution for finding "a repeatedly occuring lenghtiest sub
> SEQUENCE from a given paragraph"
>
> ex:
> input:
> hello world is a good hello world. Is that the way it is
> a way.
> Output:
> hello world

Here's my solution...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Find the longest sub-sequence of src, *
* which is repeated at least once. */

char *longsubseq(const char *src)
{
size_t substrlen, offset, srclen = strlen(src);
char *substr = malloc(srclen/2 + 1), *repeat;
if(!substr) return NULL;
for(substrlen = srclen/2; substrlen > 0; substrlen--)
{
for(offset = 0; offset < srclen - substrlen; offset++)
{
substr[0] = 0;
strncat(substr, src + offset, substrlen);
repeat = strstr(src + offset + substrlen, substr);
if(repeat) return substr;
}
}
free(substr);
return NULL;
}

If there is no subsequence that is repeated at least once, it will
return a null pointer. Otherwise, it returns a pointer to allocated
memory containing a string with the longest repeated subsequence.

This uses a rather naive algorithm, certainly not the most efficient.

--
Simon.

Simon Biber wrote
(in article <4389d463$0$25857$> ):

> Spidey wrote:
>> What is best solution for finding "a repeatedly occuring lenghtiest sub
>> SEQUENCE from a given paragraph"
>>
>> ex:
>> input:
>> hello world is a good hello world. Is that the way it is
>> a way.
>> Output:
>> hello world
>
> Here's my solution...

Thanks for contributing to the increased graduation rates
amongst cheating students. Well done.


--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw