题意
ZJM 的女朋友是一个书法家,喜欢写一些好看的英文书法。有一天 ZJM 拿到了她写的纸条,纸条上的字暗示了 ZJM 的女朋友 想给 ZJM 送生日礼物。ZJM 想知道自己收到的礼物是不是就是她送的,于是想看看自己收到的礼物在纸条中出现了多少次。
Input
第一行输入一个整数代表数据的组数
每组数据第一行一个字符串 P 代表 ZJM 想要的礼物, 包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 并且字符串长度满足 1 ≤ |P| ≤ 10,000 (|P| 代表字符串 P 的长度).
接下来一行一个字符串 S 代表 ZJM 女朋友的纸条, 也包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 满足 |P| ≤ |S| ≤ 1,000,000.
Output
输出一行一个整数代表 P 在 S中出现的次数.
输入样例
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
输出样例
1
3
0
提示
分析
这也是一道用KMP算法解决的字符串问题。
1. KMP算法的作用
KMP算法是用来求一个字符串在另一个字符串中出现的次数,或是所有出现的位置。
如:abbabab中bab出现的次数为2。分别为第3-5个字符和第5-7个字符。显然子串在字符串中出现的不同位置可以有部分重复。
其中用来匹配的子串被称作模式串,被匹配的长字符串为主串。
2. next数组
next数组是实现KMP算法的关键。
next[i]存储的是字符串中从开头到下标为i的这一段子串中,首尾相同字符串的长度。
如,abcabc:
3. KMP算法
算法过程如下:
4. 求next数组
next数组完全可以用KMP算法求得。也就是模式串自己匹配自己来获得next数组。
从模式串的第一个和第二个字符开始匹配,即主串从第二哥字符开始扫描,模式串从第一个字符开始。因为对第一个字符来说不存在首尾部分。
在这个匹配过程中,模式串和主串相同。其中模式串扫描的部分就相当于是原字符串中的首部分,而被匹配的主串与模式串所匹配的部分就是原字符串中的尾部分。
也就是用字符串每一个首部分与其每一个尾部分匹配(首尾部分最长就为前半部分和后半部分),来得到第一个字符开始到每一个字符结尾所构成的字符串中的首尾相同子串的长度。
next的使用原理:
假设主串和模式串中第 i 个字符匹配失败,若next[i] = p。
则第i个字符的前p个字符与模式串的前p个字符完全相同,那么将模式串移动,直到第i个字符的前p个字符与模式串前p个字符一一对应。
那么显然,接下来要从主串的第i个字符和模式串的第p + 1个字符开始继续进行匹配。
而模式串重新开始扫描字符在字符串数组的下标就等于p(若从下标为0处开始存储),因此next数组是用来重新定位模式串扫描起点的。
这道题就是利用KMP算法解决。只要理解了KMP算法,就可以很好解决。这道题是用该算法求出现次数。
总结
- 这个算法的难点在于理解next数组的计算过程。但是稍微思考一下还是没啥问题的。
代码
#include <iostream>
#include <string>
using namespace std;
int Next[10002];
void get_next(string s1,int length)
{
Next[0] = 0;
for( int i = 1 , j = 0 ; i < length ; i++ )
{
while( j && s1[i] != s1[j] )
j = Next[j - 1];
if( s1[i] == s1[j] )
j++;
Next[i] = j;
}
}
int kmp(string s1,string s2)
{
int res = 0;
get_next(s2,s2.size());
for( int i = 0,j = 0 ; i < s1.size() ; i++ )
{
while( j && s1[i] != s2[j] )
j = Next[j - 1];
if( s1[i] == s2[j] )
j++;
if( j == s2.size() )
{
res++;
j = Next[j - 1];
}
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
int t = 0;
cin>>t;
while( t-- )
{
string s1,s2;
cin>>s2>>s1;
cout<<kmp(s1, s2)<<endl;
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)