KMP算法用于模式串字符匹配，因为没有提前预习，上课时听得云里雾里，后来回去看了一晚上，翻了一些网上的讲解才理解了。我简单讲一下，我们在一串字符串A里搜索匹配另一段字符串B时，思路最简单方法的就是从第一位开始一个个对照匹配，出现错误就移动到第二个字符继续匹配，不匹配再第三个。但这样毕竟性能比较低，KMP引入了一个next数组，先将需要匹配的这段字符B计算出next值，在AB匹配的时候如果出现不匹配的情况，就根据next值跳到对应的字符继续匹配，所以中间就省略了一些不必要的匹配，从而提高了性能。next值的计算网上有很几种不同的方法，初始下标从-1~1都有。我学习的主要是严蔚敏老师的书，从0开始，第二位是1，书里是根据最经典的next值计算公式计算的。贴下代码让大家参考一下，具体的next值计算回学校拿到书后更新。

 

第一个输入t，表示有t个实例

第二行输入第1个实例的主串，第三行输入第1个实例的模式串

以此类推

第一行输出第1个实例的模式串的next值

第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0

以此类推

 

#include 
     
      #include 
      
       using namespace std;class myString{    private:            string mainstr;        int size;                void GetNext(string p,int next[]);        int KMPFind(string p,int pos,int next[]);            public:                myString();        ~myString();        void SetVal(string sp);        int KMPFindSubsstr(string p,int pos);};myString::myString(){    size = 0;    mainstr = "";}myString::~myString(){    size = 0;    mainstr = "";}void myString::SetVal(string sp){    mainstr = "";    mainstr.assign(sp);    size = mainstr.length();}int myString::KMPFindSubsstr(string p,int pos){    int i;    int L = p.length();    int *next = new int[L+1];    next[0] = 0;    GetNext(p,next);    for(i=1;i<=L;i++)    {        cout <
       
        <<' ';    }        cout<
        
         p.length())    {        return i-p.length();    }    else    {        return 0;    }}int main(){    int num;    cin>> num;    for(int i=0;i
         
          >main;        myString NewString;        NewString.SetVal(main);        cin >>pattern;        cout <
          
           <