match string count based on kmp
之前已经实现了KMP，不过July师兄确实非常热情，不断修改，争取所有人都懂。July师兄的博客典型的特点就是特别接地气！！！
这也是我的目标。
标准KMP实现的找出第一次匹配的pat在母串的start index，找不到返回-1
如果要数匹配的count，是不是直接把里面找到的分支里面 j=0，然后出口只有i走到头了就OK了？
我已开始也以为是，但是测了几个例子发现不对，因为i是一直往前走，不后退，那么可能会丢弃匹配的一个子串中有个length>=1后缀和模式串前缀匹配的情况,举例来说
ADA
ADADADA
这两个串，第一次匹配结束，i=3,j=3,此时如果j=0的话，那么就丢了 ADA和母串str(2,4)匹配了，因为i匹配第一个结束已经到3了。
那么这个怎么办，是不是要改回BF算法呢？不需要，因为利用next数组发现，pat(0)A=pat(2)A, 而str(0)=str(2),由于前面匹配了一段，因此str[2]=pat[2]=pat[0], 因此看str[i=3]?=pat[1=next[3]]即可。
所以这里需要为next数组多加一位，最简单的做法pat最后加一个前面不会出现的字符(现在发现其实不需要是不出现的，任意一个字符都可以，因为不会匹配到这个字符 下标j就回溯了)，然后KMP匹配时pat长度还是原来长度，因此有了下面的代码，这样是再次利用next数组的有趣的性质。
#include <iostream>
#include <string>
using namespace std;
#define read freopen("in.txt","r",stdin);
#define write freopen("out.txt","w",stdout);
#define STRMAXNUM 1000000
#define PATMAXNUM 10000
int next[PATMAXNUM+1];//add end char
void GetNext(string str)
{
int strlen=str.size();
next[0]=-1;
int k;
for(int j=0;j<=strlen-2;j++)
{
k=next[j];
while(k!=-1 && str[k]!=str[j])
k=next[k];
next[j+1]=k+1;
}
}
int Kmp(string str, string pat)
{
GetNext(pat);
int i=0,j=0,strlen=str.size(),patlen=pat.size()-1;
int matchedcount=0;
while(i<strlen)
{
if(j==-1 || str[i]==pat[j])
i++,j++;
else
j=next[j];
if(j==patlen)
{
j=next[j];//add end char, avoid missing part matched which was in just matched substr
matchedcount++;
}
}
return matchedcount;
}
int main()
{
//read;
//write;
int casen;
cin>>casen;
string str,pat;
//char c_str[STRMAXNUM+1], c_pat[PATMAXNUM+1];
getline(cin,pat);
while(casen--)
{
getline(cin,pat);
getline(cin,str);
pat+='$';//any char is ok
/*
gets(c_pat);
gets(c_str);
gets(c_str);
pat=c_pat, str=c_str;*/
cout<<Kmp(str,pat)<<endl;
//gets(c_pat);
}
return 0;
}