【正确答案】对于字符串的匹配，最直接的方法就是逐个比较字符串中的字符，这种方法比较容易实现，但是效率也比较低下。对于这种字符串匹配的问题，除了最常见的直接比较法外，经典的KMP算法也是不二选择，它能够显著提高运行效率，下面分别介绍这两种方法。
   方法一：直接计算法
   假定主串S=“S₀ S₁ S₂…S_m”，模式串P=“P₀ P₁ P₂…P_n”。实现方法为：比较从主串S中以S_i (0≤i＜m)为首的字符串和模式串P，判断P是否为S的前缀，如果是，那么P在S中第一次出现的位置则为i，否则接着比较从S_i+1开始的子串与模式串P，这种方法的时间复杂度为O(m*n)。此外如果i＞m-n，那么在主串中以S_i为首的子串的长度必定小于模式串P的长度，因此，在这种情况下就没有必要再做比较了。实现代码如下：
   """
   方法功能: 判断p是否为s的子串, 如果是, 那么返回p在s中第一次出现的下标, 否则返回-1
   输入参数: s和p分别为主串和模式串
   """
   def match(s,p):
   #检查参数的合理性
   if s==None or p==None:
   print "参数不合理"
   return -1
   slen=len(s)
   plen=len(p)
   #p肯定不是s的子串
   if slen＜plen:
   return -1
   i=0
   j=0
   while i＜slen and j＜plen:
   if list(s)[i]==list(p)[j]:
   #如果相同, 那么继续比较后面的字符
   i+=1
   j+=1
   else:
   #后退回去重新比较
   i=i-j+1
   j=0
   if(i＞slen-plen):
   return -1
   if j＞=plen: #匹配成功
   return i-plen
   return -1
   
   if__name__=="__main__":
   s="xyzabcd"
   p="abc"
   print match(s,p)
   程序的运行结果为：
   3
   算法性能分析：
   这种方法在最差的情况下需要对模式串P遍历m-n次(m，n分别为主串和模式串的长度)，因此，算法的时间复杂度为O(n(m-n))。
   方法二：KMP算法
   在方法一中，如果“P₀ P₁ P₂…P_j-1”==“S_i-j…S_i-1”，那么模式串的前j个字符已经和主串中i-j到i-1的字符进行了比较，此时如果P_j!=S_i，那么模式串需要回退到0，主串需要回退到i-j+1的位置重新开始下一次比较。而在KMP算法中，如果P_j!=S_i，那么不需要回退，即i保持不动，j也不用清零，而是向右滑动模式串，用P_k和S_i继续匹配。这种方法的核心就是确定k的大小，显然，k的值越大越好。
   如果P_j!=S_i，可以继续用P_k和S_i进行比较，那么必须满足：
   (1)“P₀ P₁ P₂…P_k-1”==“S_i-k…S_i-1”
   已经匹配的结果应满足下面的关系：
   (2)“P_j-k…P_j-1”==“S_i-k…S_i-1”
   由以上这两个公式可以得出如下结论：
   “P₀ P₁ P₂…P_k-1”=“P_j-k…P_j-1”
   因此，当模式串满足“P₀ P₁ P₂…P_k-1”==“P_j-k…P_j-1”时，如果主串第i个字符与模式串第j个字符匹配失败，那么只需要接着比较主串第i个字符与模式串第k个字符。为了在任何字符匹配失败的时候都能找到对应k的值，这里给出next数组的定义，next[i]=m表示的意思为：“P₀P₁…P_m-1”=“P_i-m…P_i-2P_i-1”。计算方法如下：
   (1)next[j]=-1 (当j==0时)
   (2)next[j]=max (Max{k|1＜k＜j且“P₀…P_k”==“P_j-k-1…P_j-1”)
   (3)next[j]=0 (其他情况)
   实现代码如下：
   """
   方法功能: 求字符串的next数组
   输入参数: p为字符串, nexts为p的next数组
   """
   def getNext(p,nexts):
   i=0
   j=-1
   nexts[0]=-1
   while i＜len(p):
   if j==-1 or list(p)[i]==list(p)[j]:
   i+=1
   j+=1
   nexts[i]=j
   else:
   j=nexts[j]
   
   def match(s,p,nexts):
   #检查参数的合理性, s的长度一定不会小于p的长度
   if s==None or p==None:
   print "参数不合理"
   return -1
   slen=len(s)
   plen=len(p)
   #p肯定不是s的子串
   if slen＜plen:
   return -1
   i=0
   j=0
   while i＜slen and j＜plen:
   print "i="+str(i)+","+"j="+str(i)
   if j==-1 or list(s)[i]==list(p)[j]:
   #如果相同, 那么继续比较后面的字符
   i+=1
   j+=1
   else:
   #主串i不需要回溯, 从next数组中找出需要比较的模式串的位置j
   j=nexts[j]
   if j＞=plen: #匹配成功
   return i-plen
   return -1
   
   if __name__=="__main__":
   s="abababaabcbab"
   p="abaabc"
   lens=len(p)
   nexts=[0]*(lens+1)
   getNext(p,nexts)
   print "nexts数组为: "+str(nexts[0]),
   i=1
   while i＜lens-1:
   print ","+str(nexts[i]),
   i+=1
   print '\n'
   print "匹配结果为:"+str(match(s,p,nexts))
   程序的运行结果为:
   next数组为:-1,0,0,1,1
   i=0,j=0
   i=1,j=1
   i=2,j=2
   i=3,j=3
   i=3,j=1
   i=4,j=2
   i=5,j=3
   i=5,j=1
   i=6,j=2
   i=7,j=3
   i=8,j=4
   i=9,j=5
   匹配结果为：4
   从运行结果可以看出，模式串P="abaabc"的next数组为[-1,0,0,1,1]，next[3]=1，说明P[0]==P[2]。当i=3，j=3的时候S[i]!=P[j]，此时主串S不需要回溯，跟模式串位置j=next[j]=next[3]=1的字符继续进行比较。因为此时S[i-1]一定与P[0]相等，所以，就没有必要再比较了。
   算法性能分析：
   这种方法在求next数组的时候循环执行的次数为n(n为模式串的长度)，在模式串与主串匹配的过程中循环执行的次数为m(m为主串的长度)。因此，算法的时间复杂度为O(m+n)。但是由于算法申请了额外的n个存储空间来存储next数组，因此，算法的空间复杂度为O(n)。

【答案解析】

[考点] 如何实现字符串的匹配。