New Logic

Discussion in 'C Programming' started by Spidey, Nov 27, 2005.

  1. Spidey

    Spidey Guest

    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, Nov 27, 2005
    #1
    1. Advertising

  2. Spidey

    Mike Wahler Guest

    "Spidey" <> wrote in message
    news:...
    > 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
     
    Mike Wahler, Nov 27, 2005
    #2
    1. Advertising

  3. Spidey

    pemo Guest

    "Spidey" <> wrote in message
    news:...
    > 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)
     
    pemo, Nov 27, 2005
    #3
  4. Spidey

    Malcolm Guest

    "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.
     
    Malcolm, Nov 27, 2005
    #4
  5. 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 =----
     
    Mark McIntyre, Nov 27, 2005
    #5
  6. Spidey

    Simon Biber Guest

    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, Nov 27, 2005
    #6
  7. Spidey

    Randy Howard Guest

    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
     
    Randy Howard, Nov 27, 2005
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Qunwei Chen
    Replies:
    6
    Views:
    3,655
    Renaud Pacalet
    Aug 22, 2003
  2. David Li
    Replies:
    1
    Views:
    500
    David Hilsee
    Aug 4, 2004
  3. jacko
    Replies:
    0
    Views:
    460
    jacko
    Aug 1, 2008
  4. spike
    Replies:
    8
    Views:
    1,506
    Steve Holden
    Feb 9, 2010
  5. Replies:
    2
    Views:
    487
    Thomas 'PointedEars' Lahn
    Mar 11, 2008
Loading...

Share This Page