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

G

Girish Sahani

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
 
C

Christoph Zwerschke

Girish said:
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
 
G

Girish Sahani

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
 
K

K.S.Sreeram

Girish said:
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))]
['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-----
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top