任务描述

本关任务：编写一个程序，利用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;
}