2477 - 动物简介(animal) （1046）
到了动物园，琦琦开心得跳起来。哗，这里好多动物呀，有老虎，有狮子……，在开心之余，琦琦也不忘妈妈的教导：观察动物时要认真仔细，还要看动物园附上的动物简介呀。
动物的简介原来还有英文版的呢！为了卖弄自己的英文水平，琦琦就告诉妈妈每张动物简介里出现了多少次该动物的名称。注意：琦琦只认识小写字母，而且她只认得动物的单词，因此她认为monkeys或者smonkey或者smonkeys都是出现了monkey这个词。
你能编程完成琦琦的任务吗？
Input
输入文件共n+2行：
第1行为数字n（n<=3000），表示该动物的简介共有n行。
第2行为一个单词，表示琦琦认识的动物名称。
接着是n行，每行为一个长度小于250个字符的字符串，表示动物的简介。
Output
输出文件共1行，为简介里出现了多少次琦琦能识别出的动物的单词。
Examples
Input
1 monkey She often jumps onto my knees. I like to give her a bath.
Output
0
Solution C++
#include <bits/stdc++.h> using namespace std; int nextval[300]; void getnextval(string s){ int j=-1; nextval[0]=-1; for(int i=0;i<s.size();i++){ while(j!=-1&&s[i]!=s[j+1]){ j=nextval[j]; } if(s[i]==s[j+1]) j++; if(j==-1||s[i+1]!=s[j+1]) nextval[i]=j; else nextval[i]=nextval[j]; } } int KMP(string text,string pattern){ int n=text.size(),m=pattern.size(); getnextval(pattern); int ans=0,j=-1; for(int i=0;i<n;i++){ while(j!=-1&&text[i]!=pattern[j+1]){ j=nextval[j]; } if(text[i]==pattern[j+1]) j++; if(j==m-1){ ans++; j=nextval[j]; } } return ans; } int main(){ string pattern; int n,i; int num=0; cin>>n; getchar(); cin>>pattern; getchar(); for(i=0;i<n;i++){ string text; getline(cin,text); num+=KMP(text,pattern); } cout<<num<<endl; return 0; }