5-5 E. 可重叠子串 (Ver. I)

本文主要是介绍5-5 E. 可重叠子串 (Ver. I)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个字符串（模式串）和一些待查找的字符串，求每个待查找字符串在模式串中出现的次数（可重叠）

输入

第一行输入t，表示有t组测试数据

每一组测试数据包含多行：

每一组的第一行包括一个字符串P，长度不超过105，且非空串

每一组的第二行包括一个整数N，代表待查找的字符串数量 (1 <= N <= 5)

每一组接下来的N行，每一行包括一个待查找的字符串，其长度不超过50，且非空串

输入样例：

2
aabbcc
3
aa
bb
cc
ababab
1
aba

输出

对于每组测试数据，

输出每个待查找字符串出现的次数，

具体输出见样例

输出样例：

aa:1
bb:1
cc:1
aba:2

代码 

#include <iostream>
using namespace std;class FindStr{
public:string P,S;int N,Slen,res;int *next;FindStr(){cin >> P;cin >> N;while(N--){cin >> S;Slen = S.length();next = new int[Slen];getNext();res = MethKPM();cout << S << ":" << res << endl;}}void getNext(){next[0] = -1;int i=0,j=-1;while(i < Slen){if(j == -1 || S[i] == S[j]){i++;j++;next[i] = j;}else{j = next[j];}}}int MethKPM(){  //对KPM算法进行变化int count=0,i=0,j=0;while(i < P.length() && j < Slen){if(j == -1 || P[i] == S[j]){i++;j++;}else{j = next[j];}if(j >= Slen){  //当发现模式串与主串相同时count++;i -= Slen-1;  //i退回到原本返回值的后一位，继续找有无相同部分，直至遍历完主串j = 0;}}return count;}
};int main()
{int t;cin >> t;while(t--){FindStr key;}return 0;
}

这篇关于5-5 E. 可重叠子串 (Ver. I)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---