北京旅游攻略_石家庄尚武科技_网页代码_鹤壁搜索引擎优化

头歌实训：利用kmp算法求子串在主串中不重叠出现的次数

任务描述

本关任务：编写一个程序，利用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，长度不超过10⁶。
第二行为字符串t，长度不超过10⁶。

输出格式

在一行中输出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); /*** 说明：任选上面三个函数中的一个进行实现。*///请在下面编写代码
int main()
{string s, t;cin >> s >> t;//cout << s << " " << t << endl;int cnt = Count(s, t);cout << cnt << endl;return 0;
}int Count(string s, string t)
{int next[t.length()], j = 0, k = -1, i, cnt = 0; //next数组用于遍历时字符串t的下标回溯，j用于遍历字符串t，i用于便利字符串s，k用于给next数组赋值，cnt用于记录子字符串出现的次数next[0] = -1;   //将第一个next数组的下标置为-1while(j < t.length() - 1)   //获得next数组{if(k == -1 || t[j] == t[k]){j++;k++;next[j] = k;}else{k = next[k];}}i = j = 0;  //初始化两个下标while(i < s.length())   //通过while循环获得出现次数{if(j == -1 || s[i] == t[j]){i++;j++;}else{j = next[j];}if(j == t.length()) //当匹配成功时计数器++并且回溯j到0{cnt++;j = 0;}}return cnt; //返回出现次数
}