有一个字符串“ATGACATGCA”，我想搜索“ATGC”，可以在(5, 15)处找到。
如果把“ATGC”分成“A”、“T”和"GC"；假设不知道"T”，只查“A”和"GC"，那么分别n =(0, 3, 5, 9)和m = (7,)处找到。
“A”的长度1，在n和m的范围中选择合适的数字，5+1+1=7。
“A”所在的位置有四个，如果隔一个字母后要是“GC”的话，那“A”所在位置必须在加1才是“GC”的位置。
习题3：
将一个字符串分成三个部分，第一个子字符串，丢失的部分（长度为1），第二个子字符串。
写出函数constrainedMatchPair。此函数有三个参数：第一个子字符串起始位置的元组；第二个子字符串起始位置的元组；第一个子字符串的长度。
函数能够返回所有第一个组元中的所有数据（n），此数据能够和第二个组元中的数据（k），满足n+m+1 = k，m为第一个字字符串的长度。
函数按如下定义，
def constrainedMatchPair(firstMatch,secondMatch,length):
def constrainedMatchPair(firstMatch, secondMatch, length):m = lengthmatch = ()for n in firstMatch:for k in secondMatch:if n + m + 1 == k:match = match + (n,)return match
然后通过subStringMatchOneSub来验证,此函数要用到之前的subStringMatchExact
通过bing就能很容易搜到ps3_template.py：
所有代码如下：
from string import finddef subStringMatchExact(target, key):tuple = ()order = 0while find(target, key, order) != -1:tuple = tuple + (find(target, key, order),)order = find(target, key, order) + 1return tupledef constrainedMatchPair(firstMatch, secondMatch, length):m = lengthmatch = ()for n in firstMatch:for k in secondMatch:if n + m + 1 == k:match = match + (n,)return match# this is a code file that you can use as a template for submitting your# solutions# these are some example strings for use in testing your code# target stringstarget1 = 'atgacatgcacaagtatgcat'target2 = 'atgaatgcatggatgtaaatgcag'# key stringskey10 = 'a'key11 = 'atg'key12 = 'atgc'key13 = 'atgca'### the following procedure you will use in Problem 3def subStringMatchOneSub(key,target):"""search for all locations of key in target, with one substitution"""allAnswers = ()for miss in range(0,len(key)):# miss picks location for missing element# key1 and key2 are substrings to matchkey1 = key[:miss]key2 = key[miss+1:]print 'breaking key',key,'into',key1,key2# match1 and match2 are tuples of locations of start of matches# for each substring in targetmatch1 = subStringMatchExact(target,key1)match2 = subStringMatchExact(target,key2)# when we get here, we have two tuples of start points# need to filter pairs to decide which are correctfiltered = constrainedMatchPair(match1,match2,len(key1))allAnswers = allAnswers + filteredprint 'match1',match1print 'match2',match2print 'possible matches for',key1,key2,'start at',filteredreturn allAnswersfor key in (key10, key11, key12, key13):for target in (target1, target2):print subStringMatchOneSub(key,target)
习题4：
写一个函数subStringMatchExactlyOneSub，有两个参数：目标字符串和关键词字符串。返回关键词中有一个不同在目标中的起始位置的元组。
def subStringMatchExactlyOneSub(target,key):
def subStringMatchExactlyOneSub(target,key):possible = subStringMatchOneSub(key,target)certain = subStringMatchExact(target, key)one = ()for p in possible:for c in certain:if p == c:breakelif c == certain[-1]:one = one + (p,)return one
