// KMP.cpp : 定义控制台应用程序的入口点。

 //

 #include "stdafx.h"

 #include <iostream>

 #include <new>

 using namespace std;

 /************************************************************************

    这个算法的关键在于不用回溯指示主串当前比较位置的变量i，

    当主串和模式串失配时，只需要将模式串向右滑动尽可能大的距离

    即决定主串当前位置i上的元素 应该和 模式串的哪个元素比较

    即关键在于求的一个next[j]数组，当主串在i位置和模式串的j位置失配时，

    应该将模式串的next[j]位置元素和主串i位置元素开始比较，重复此过程

    所以问题的关键在于求解一个next[j]数组，这个数组的求解是和主串无关的。

 ************************************************************************/

 //以下代码并没有完全的对参数进行检查

 //求解next数组

 //lpString为模式串

 //next为输入数组

 void GetNext(const TCHAR* lpString, int* next)

 {

     if (NULL == lpString || NULL == next){ return; }

     int j = ;

     int k = ;

     next[] = -;

     j = ;

     k = -;

     int length = _tcslen(lpString);

     while (j < length - )

     {

         if (- == k || lpString[j] == lpString[k])

         {

             ++j;

             ++k;

             next[j] = k;

         }

         else

         {

             k = next[k];

         }

     }

 }

 int KMPMatch(const TCHAR* lpMain, const TCHAR* lpMatch)

 {

     int nMain = _tcslen(lpMain);

     int nMatch = _tcslen(lpMatch);

     int* pNext = new int[nMatch]();

     int i = ;

     int j = ;

     if (NULL == pNext)

     {

         return -;

     }

     GetNext(lpMatch, pNext);

     while (i < nMain && j < nMatch)

     {

         if (- == j || lpMain[i] == lpMatch[j])

         {

             ++i; ++j;

         }

         else

         {

             j = pNext[j];

         }

     }

     delete[] pNext;

     pNext = NULL;

     if (j >= nMatch)

     {

         return i - nMatch;

     }

     return -;

 }

 int _tmain(int argc, _TCHAR* argv[])

 {

     const TCHAR* lpMain = _T("helloworld");

     const TCHAR* lpMatch = _T("oworl");

     wcout<<"模式串 "<<lpMatch<<" 在主串 "<<lpMain<<" 中的位置为 " \

         <<KMPMatch(lpMain, lpMatch)<<endl;;

     return ;

 }