Velocity Reviews > New Logic

# New Logic

Spidey
Guest
Posts: n/a

 11-27-2005
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

Mike Wahler
Guest
Posts: n/a

 11-27-2005

"Spidey" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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

pemo
Guest
Posts: n/a

 11-27-2005

"Spidey" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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)

Malcolm
Guest
Posts: n/a

 11-27-2005

"Spidey" <(E-Mail Removed)> 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.

Mark McIntyre
Guest
Posts: n/a

 11-27-2005
On 26 Nov 2005 22:08:15 -0800, in comp.lang.c , "Spidey"
<(E-Mail Removed)> 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 =----

Simon Biber
Guest
Posts: n/a

 11-27-2005
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.

Randy Howard
Guest
Posts: n/a

 11-27-2005
Simon Biber wrote
(in article <4389d463\$0\$25857\$(E-Mail Removed)> ):

> 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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post spike Python 8 02-09-2010 12:31 PM Jyoti Ballabh Software 3 11-26-2009 06:48 PM jacko VHDL 0 08-01-2008 04:56 PM David Li C++ 1 08-04-2004 12:38 AM btrix Computer Support 7 05-28-2004 02:39 PM

Advertisments