任务描述
本关任务：编写一个程序，利用kmp算法求子串在主串中不重叠出现的次数。
实验目的：深入掌握KMP算法的应用。
实验内容：编写一个程序，利用KMP算法求子串t在主串s中出现的次数，例如：s=“aabbdaabbde”，t=“aabbd”，t在s中出现2次；再例如：s=“aaaaa”，t=“aa”，t在s中出现2次。
实验工具：本关提供顺序串SqString的基本运算及其实现（在头文件sqstring.h中）；您也可以直接使用C++ STL提供的string容器。
编程要求
根据提示，在右侧编辑器补充完成代码，计算并输出字符串t在字符串s中不重叠出现的次数。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括2行。
第一行为字符串s，长度不超过 。
第二行为字符串t，长度不超过 。
输出格式
在一行中输出t在s中出现的次数。样例输入1
aaaaa
aa样例输出1
2样例输入2
aabbdaabbde
aabbd样例输出2
2开始你的任务吧，祝你成功！
测试代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string> //C++ STL之string容器
using namespace std;#include "sqstring.h" //包含顺序串SqString基本运算算法//利用KMP算法求t在s中出现的次数
int Count(string s, string t); //利用KMP算法求t在s中出现的次数
int Count(char* s, char* t); //利用KMP算法求t在s中出现的次数
int Count(SqString s, SqString t); /*** 说明：任选上面三个函数中的一个进行实现。*///请在下面编写代码补充代码：
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=1000010;
char s[M],p[N];
int ne[N];int main(){cin >> s + 1 >> p + 1;int n = strlen(s + 1) , m = strlen(p + 1);for(int i = 2 , j = 0 ; i <= m ; i ++ ){while(j && p[i] != p[j + 1]) j = ne[j];if(p[i] == p[j + 1]) j ++;ne[i] = j;}int tot = 0;for(int i = 1 , j = 0 ; i <= n ; i ++ ){while(j && s[i] != p[j + 1]) j = ne[j];if(s[i] == p[j + 1]) j ++;// cout << i << " " << j << endl;if(j == m){tot ++;j = 0;}} cout << tot;return 0;
}
