How to search for substrings of a string in a list?

Discussion in 'Python' started by Girish Sahani, Jun 5, 2006.

  1. Given a length k string,i want to search for 2 substrings (overlap
    possible) in a list consisting of length k-1 strings. These 2 substrings
    when 'united' give the original string.

    e.g given 'abc' i want to search in the list of 2-length strings
    ['ab',ac','cd','bc','bd'] to extract either
    1) 'ab and 'ac' OR ('a' common)
    2) 'ab' and 'bc' OR ('b' common)
    3) 'ac' and 'bc' ('c' common)
    In all these cases, one of the letter is common in the 2 strings.
    Out of the k-1 letters in each length k-1 string,k-2 will be common.
    Another e.g is:
    Given 'abcd' and list ['abc,'abd','bcd'],i must extract
    1)abc and abd OR ('ab' common)
    2)abc and bcd OR
    3)abd and bcd OR
    Here 2 letters are common in all the solutions.
    I havent been able to figure out a method. Pleeez help!!

    Thanks in advance,
    girish
    Girish Sahani, Jun 5, 2006
    #1
    1. Advertising

  2. Girish Sahani schrieb:
    > Given a length k string,i want to search for 2 substrings (overlap
    > possible) in a list consisting of length k-1 strings. These 2 substrings
    > when 'united' give the original string.
    > e.g given 'abc' i want to search in the list of 2-length strings
    > ['ab',ac','cd','bc','bd'] to extract either
    > 1) 'ab and 'ac' OR ('a' common)
    > 2) 'ab' and 'bc' OR ('b' common)
    > 3) 'ac' and 'bc' ('c' common)


    Here is a simple brute force solution that also works for different
    lengths of your strings:

    complete = 'abc'
    partial = ['ab','ac','cd','bc','bd']

    for i1, s1 in enumerate(partial):
    for s2 in partial[i1+1:]:
    if set(s1).union(set(s2)) == set(complete):
    print s1, s2

    -- Christoph
    Christoph Zwerschke, Jun 5, 2006
    #2
    1. Advertising

  3. How to generate all k-1 level substrings of a string?

    I want to generate all substrings of size k-1 from a string of size k.
    e.g 'abcd' should give me ['abc','abd','bcd','acd']
    Order of these strings in the list doesnt matter.
    Also order doesnt matter inside the string e.g 'abc' or 'bca' or 'bac' is
    the same.
    I wrote the following code but it doesnt give the full output:

    subsetList = []
    for element in prunedNew:
    for i in range(0,2):
    subsetList.append(element[i:i+len(element)-1])
    continue
    continue
    return prunedNew


    Thanks in Advance,
    girish
    Girish Sahani, Jun 6, 2006
    #3
  4. Girish Sahani

    K.S.Sreeram Guest

    Re: How to generate all k-1 level substrings of a string?

    Girish Sahani wrote:
    > I want to generate all substrings of size k-1 from a string of size k.
    > e.g 'abcd' should give me ['abc','abd','bcd','acd']


    def get_sub_set( s ) :
    return [s[:i]+s[i+1:] for i in range(len(s))]

    >>> print get_sub_set( 'abcd' )

    ['bcd', 'acd', 'abd', 'abc']

    Regards
    Sreeram


    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2.2 (MingW32)
    Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

    iD8DBQFEhPFyrgn0plK5qqURAoMaAKC7oRnEPkQKMeX5xhz2eXhH4pSlTQCgp8Qu
    gPiJ3A029tq5jgAJI33DLUY=
    =3E6C
    -----END PGP SIGNATURE-----
    K.S.Sreeram, Jun 6, 2006
    #4
    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. Amit Khemka
    Replies:
    8
    Views:
    299
    Amit Khemka
    Nov 23, 2005
  2. Replies:
    8
    Views:
    643
    Thorsten Kampe
    Jul 13, 2006
  3. Tung Chau
    Replies:
    1
    Views:
    462
    SM Ryan
    Aug 6, 2004
  4. Tung Chau
    Replies:
    0
    Views:
    367
    Tung Chau
    Aug 6, 2004
  5. Replies:
    12
    Views:
    242
Loading...

Share This Page