14436: NH字符串

14436: NH字符串

时间限制: 10 Sec   内存限制: 128 MB

题目描述

给一个字符串 T，问在字符串 T 中可以包含最多多少个不重叠的字符串 S。
字符串中的每个字符为小写或者大写字母。

输入

第一行输入一个字符串 S。
第二行输入一个字符串 T。

输出

输出一行，包括一个整数表示答案。

样例输入 Copy

Aba

Abababa

样例输出 Copy

1

提示

50%的数据，1<=字符串T长度<=20000,1<=字符串S长度<=100
100%的数据，1<=字符串T长度<=1000000,1<=字符串S长度<=100000。其中多数是随机产生。

解析：

求一个字符串是否包含另一个字符串，很容易让人想到KMP算法，但是因为我们要计算包含多少个，所以当找到相同的字串时，处理方法和KMP不同，具体见下面代码：

#include<bits/stdc++.h>

#define N 1000005

using namespace std;

char s1[N],s2[N];

int len1,len2;

int next1[N];

int ans;

void get_next(){

int t1=0,t2;

next1[0]=t2=-1;

while(t1<len2)

if(t2==-1||s2[t1]==s2[t2])

next1[++t1]=++t2;

else t2=next1[t2];

}

void kmp(){

int t1=0,t2=0;

while(t1<len1){

if(t2==0-1||s1[t1]==s2[t2])t1++,t2++;

else t2=next1[t2];

if(t2==len2){ans++;t2=0;}

//找到子串后我们不是直接挂到末尾位置，而是向后一位重新扫描

}

}

int main(){

cin>>s2>>s1;

len1=strlen(s1);len2=strlen(s2);

ans=0;

get_next();kmp();

cout<<ans<<endl;

return 0;

}