字符串匹配问题描述：设有两个字符串A和B，A字符串长度为N，B字符串长度为M，现在要确定B字符串是否出现在A字符串中，如果是，返回位置，如果不是返回结果为false，在这里，我们成字符串B为模式字符串，A为主串。

最近经常会被问到字符串匹配的问题，实际上这些问题在网上都有很多资源，我觉得没有必要自己写一个，但是看了之后可能过段时间又不是很清楚了，因此在这里做个记录，记录那些让我感觉讲得比较清楚的主页。

1. KMP算法

KMP算法是O(M+N)的算法，KMP算法的思想很简单，那就是要利用之间比较的结果，其中有贪心算法和回溯算法的影子。此算法需要对模式字符串B进行预处理，得到一个长度与B相同的Partial数组（）

• 讲得比较明白浅显易懂的是： 只是一个简单的介绍
• 讲得比较简洁清晰的是：  讲得很好，用C++实现了一下这个算法：
  #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; /*预处理的过程有人称之为求next数组，有人称之为求partial table   需要注意的是，next数组的长度不能是本身的长度，也就是说"aa"的next数组长度为1而不是2   不要问为什么，这个是由KMP算法的需求决定的 */ vector
              
                 preprocessing(string & sub) {
            vector
               
                 ret; if (sub.empty()) { return ret; } for(int i=0;i
                
                 =0) { if(sub[forward]==sub[ret[backward]]) { ret[forward]=ret[backward]+1;break; } else { backward=ret[backward]-1; } } if(backward<0){ret[forward]=0;} } return ret; } bool isSubString(string & master ,string &sub,int &index) { if(master.length()
                 

  P=preprocessing(sub); vector
  ::iterator int_iter; for(int_iter=P.begin();int_iter!=P.end();++int_iter) { cout<<*int_iter; } cout<