KMP算法

于是，我的每个梦里都会有你

#include <iostream>
#include <string>
using namespace std;

int* getNext(string s){
    if(s.size()<=1){
        return new int[1]{-1};
    }
    int len = s.size();
    int* next = new int[len];
    next[0] = -1;
    next[1] = 0;
    int current = 0;
    int i = 2;
    while(i < len){
        if(s[i-1] == s[current]){
            //如果前缀和后缀匹配
            next[i++] = ++current;
        }else{
            if(current > 0){
                //继续寻找current前面的最小字串
                current = next[current];
            }else{
                next[i++] = 0;
            }
        }
    }
    return next;
}

//s是主串，m是模式串
int getIndexOf(string s,string m){
    int* next = getNext(m);
    int i1,i2;
    i1 = i2 = 0;
    while(i1 < s.length() && i2 < m.length()){
        if(s[i1] == m[i2]){
            ++i1;
            ++i2;
        }
        //如果不等
        else
            {
                if(next[i2] == -1){
                //第一个字串就不相等
                ++i1;
            }else{
                //推动m到指定位置
                i2 = next[i2];
            }
        }
    }
    delete[] next;
    return i2 == m.length() ? i1-i2 : -1;
}


int main(int argc, char const *argv[])
{
    /* code */
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    int ans = getIndexOf(s1,s2);
    cout << ans << endl;
    return 0;
}