问题 R: 【字符串】动物简介（KMP模板题）

有一种隐忍其实是蕴藏着的一种力量，有一种静默其实是惊天的告白。

题目描述

到了动物园，琦琦开心得跳起来。哗，这里好多动物呀，有老虎，有狮子……，在开心之余，琦琦也不忘妈妈的教导：观察动物时要认真仔细，还要看动物园附上的动物简介呀。
动物的简介原来还有英文版的呢！为了卖弄自己的英文水平，琦琦就告诉妈妈每张动物简介里出现了多少次该动物的名称。注意：琦琦只认识小写字母，而且她只认得动物的单词，因此她认为monkeys或者smonkey或者smonkeys都是出现了monkey这个词。
你能编程完成琦琦的任务吗？

输入

输入共n+2行：
第1行为数字n（n<=3000），表示该动物的简介共有n行。
第2行为一个单词，表示琦琦认识的动物名称。
接着是n行，每行为一个长度小于250个字符的字符串，表示动物的简介。

输出

输出共1行，为简介里出现了多少次琦琦能识别出的动物的单词。

样例输入

复制样例数据

2 snake The snake is a long and thin animal. Snakes have no legs or feet.

样例输出

1这里有KMP的详解哟：https://mp.csdn.net/postedit/89311107

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <deque>

#include <queue>

#include <stack>

#include <cctype>

#include <cstdio>

#include <bitset>

#include <string>

#include <vector>

#include <complex>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

#include <functional>

#define inf 0x3f3f3f3f

typedef long long ll;

using namespace std;

int xyg[3010];

void getx(string s)

{

int j=-1,l=s.length();

for(int i=1; i<l; i++)

{

while(j!=-1&&s[i]!=s[j+1])

{

j=xyg[j];

}

if(s[i]==s[j+1])

j++;

if(j==-1||s[i+1]!=s[j+1])

xyg[i]=j;

else

xyg[i]=xyg[j];

}

}

int kmp(string s1,string s2)

{

int jg=0,j=-1;

int l1=s1.length(),l2=s2.length();

for(int i=0; i<l1; i++)

{

if(j!=-1&&s1[i]!=s2[j+1])

j=xyg[j];

if(s1[i]==s2[j+1])

j++;

if(j==l2-1)

{

jg++;

j=xyg[j];

}

}

return jg;

}

int main()

{

int n,jg;

string s1,s2;

scanf("%d",&n);

getchar();

getline(cin,s1);

getx(s1);

jg=0;

for(int i=0; i<n; ++i)

{

getline(cin,s2);

jg+=kmp(s2,s1);

}

printf("%dn",jg);

return 0;

}