有一个文本字符串s，和一个模式串p，想要查找s中是否包含p，以及s中p出现的第一个位置。
首先用暴力匹配，主要是不相等的时候就回溯，这样时间复杂度较高。
核心思想i和j分别指向s和p，如果s[i] == p[j]  {i++,j++,count++}
如果count == p.size()就说明找到了；如果s[i] != p[i]，此时回溯，i = i-j+1;j=0;
代码如下： 
    int findStrWithoutKMP(string s,string p)
    {
        if(s.size() == 0 || p.size() == 0 || s.size() < p.size()) return -1; //表示不存在 s的长度要大于等于p
        int i =0;
        int j =0;

        int curLen = 0;

        while (i>=0 && i<s.size())
        {
            //cout<<"This i is "<<i<<" j is "<<j<<endl;
            curLen = 0;
            for(int j=0;j<p.size();) //j++不需要在这里+
            {
                if(s[i] == p[j] && i<s.size() && j<p.size()) //加上 i<s.size()和j<p.size这个判断和快速排序left right判断一个道理
                {
                    curLen++;
                    //cout<<"This i is "<<i<<" j is "<<j<<" This curLen is "<<curLen<<endl;
                    if(curLen == p.size()) //先进行curLen判断 再进行i++和j++
                    {
                        return (i-p.size()+1) + 1; //i-p.size()+1是从0开始的位置 等于2表示是0 1 2位置所以从1开始实际是第3个，所以再加个1
                    }
                    i++; 
                    j++;
                } else
                {
                    i = i-j+1;
                    j = 0;
                    break;
                }
                
            }
        }
        return -1;

    }
下面再说先kmp算法，kmp算法核心就是利用next数组，是的文本串s不回溯，一直向前，模式串p根据next数组来回溯到对应的位置。
next数组的求法和kmp主函数的有一定类似。这个kmp函数返回的是s中所有包括p的位置，可能有多个，位置从0开始。主要代码如下： 
    vector<int>  next(string s)
    {
        vector<int> res(s.size(),0);
        if(s.size() == 0) return res;
 
        int count = 0;
        for(int i=1;i<s.size();i++)
        {
            while (count > 0 && s[i] != s[count])
            {
                count = res[count -1];
            }
            if(s[i] == s[count])
            {
                count++;
            }
            res[i] = count;
        }

        return res;

    }
    

        //00011212001212000                       
    //string s = "abcaababdfababfds";
    //string p = "abab";
    //int findIndexStr(string )
    vector<int> searchByKMP(string s,string p)
    {
        vector<int> positions;
        vector<int> nextVector = next(s); //这个vector命名居然不能和原来的一样

                /************************************
        for(int i=0;i<nextVector.size();i++)
        {
            cout<<nextVector[i]<<" ";
        }
        cout<<endl;
                ************************************/ 
        int count = 0;
        for(int i=0;i<s.size();i++)
        {
            while (count > 0 && p[count] != s[i])
            {
                count = nextVector[count-1];
            }
            
            if(p[count] == s[i])
            {
                count++;
            }

            if(count == p.size())
            {
                positions.push_back(i - p.size()+1);
                count = nextVector[count-1]; //关键这一行是为啥
            }
        }

        return positions;

    }