28

解法一，暴力法

//暴力
        if(haystack.length()<needle.length())
        {
            return -1;
        }
        for(int i=0;i<=haystack.length()-needle.length();i++)
        {
            if(needle==haystack.substr(i,needle.length()))
            {
                return i;
            }
        }
        return -1;

KMP算法

暴力算法的不足：每次都从第二串的头部开始匹配，没有从上一次的匹配中收获有用信息
KMP算法核心：利用匹配失败后的信息，尽量减少模式串和主串的匹配次数，达到快速匹配的目的主串：A 模式串：B
KMP算法不回溯i，只回溯j到指定位置
只有当A子串的后缀集合与B子串的前缀集合有交集时，回溯j

B串需要往后移动多少即j回溯的位置，所以需要找到B子串前缀集合与A子串的后缀集合的交集中最长元素，最长元素使B串后移最少，已知匹配的最多，所以需要其长度
因为在前面的匹配中，B子串=A子串，所以上述可以表示为，B子串的前缀集合和他本身的后缀集合的交集，

j指针的位置=B字串的最长公共前后缀
通过隐藏信息，匹配失败时，A串和B串存在着一段相同的子串，j指针的位置，只与B串有关，与A无关，
所以，可以在匹配之前就通过B串计算回溯位置，存在一个数组next当中，
next与B串形成映射数组，next[i]就是B[1]~B[i]的最长公共前后缀的长度

具体的匹配步骤
i，j初始化为0

如果A[i]=B[j],i++,j++继续匹配
如果A[i]!=B[j]，回溯j到next[j]，直到A[i]B[j]，
当j=0时，忽略j，增加i，知道A[i]B[j]
3.当j=模式串长度，输出位置，继续匹配

只能说不是很理解

int n=haystack.length();
        int m=needle.length();
        //计算next数组
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }

        //匹配
        for(int i=0,j=0;i<n;i++)
        {
            while(j>0&&haystack[i]!=needle[j])
            {
                j=pi[j-1];
            }
            if(haystack[i]==needle[j])
            {
                j++;
            }
            if(j==m)
            {
                return i-j+1;
            }
            

        }
        return -1;