算法-KMP-C++

   kmp算法中的经典，应用于字符串匹配的问题。
   给定两个串：str="acbc" match=“bc” 返回2
                        str="acbc" match="bcc" 返回-1
   本人水平有限只简单描述一下求解过程，如果要对算法本身有了解，需要找相关的资料再看看，比如next数组中的前缀后缀最大匹配长度的计算。  

1.暴力方法：
    str1:0          1           2
    str2:0...m    0....m   0...m
所有位置匹配一遍

2.KMP
    1.求str2的next数组。
    2. str1 x   不匹配时，x不动 y 跳转到 next数组对应位置，而不是回到0位置
        str2 y

using namespace std;
typedef vector<int> vci;
    int getIndexOf(string s, string m) 
    {
        if (s == "" || m == "" || m.length() < 1 || s.length() < m.length())
        {
            return -1;
        }

        int X = 0;                            //str1中比对到的位置
        int Y= 0;                             //str2中比对到的位置

        vci next = getNextArray(m);           //str2的next数组
        while (X < s.length() && Y < m.length()) // XY不越界
        {
            if (s[X] == m[Y])                  //1.匹配 继续
            {
                X++;
                Y++;
            }
            else if (next[Y] == -1)           // 2.匹配不上 ，str1换位置  
            { 
                 X++;
            }
             else                            //3.Ynext数组值不是-1 X停不变，Y往前跳
            {   
             Y = next[Y];
             }
         }      
        return Y == m.size() ? X - Y : -1; 
    }