Problem C
问题
某人在教育学弟时说:“电院的万神,比你们高的不知道哪里去了,我和他
谈笑风生!”但是学弟 too young,too simple,根本不认识万神,只好自己到百
度上搜。
为了衡量搜索结果和万神的相关程度,学弟希望知道一篇文章中“万神”二
字出现的次数。你能帮助他吗?
输入格式
输入包含多组数据,请处理到文件结束。
每组数据,第一行包含整数 n,表示这组数据的行数。之后 n 行表示学弟搜
到的文章。为了避免中文编码问题,文章用拼音给出。
保证文章只包含大写英文字母(英文)、小写英文字母(拼音)、句号 “.” 、
逗号”,” 。
保证 1 ≤ n ≤ 100,输入文件总长度至多是 5MB 。
输出格式
对于每组数据,输出文章中“万神”二字(拼音为 “wanshen”,不含引号)
的出现次数。
输入样例
5
wanshenshixidianACM
dediyidashen.erqiew
anshendeDOTAyedadeh
enhao.womendouhenOR
Zwanshen.
1
WANSHEN.
输出样例
3
0
样例解释
对于第一组样例,注意“万神”跨越了文章的第 2 行和第 3 行。
对于第二组样例,我们不认为英文字母序列 “WANSHEN” 表示万神。
思路
KMP模板，，最长公共前后缀
/*************************************************************************
> File Name: c.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年04月20日 星期三 13时04分24秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 50086;
int nxt[10];
char a[101][N];
char p[10] = "wanshen";
int n;
int l = strlen(p);
void init()
{
int k = 0;
nxt[0] = 0;
for(int i = 1; i < l; i++)
{
while(k && p[i] != p[k]) k = nxt[k-1];
if(p[i] == p[k]) k++;
nxt[i] = k;
}
}
int kmp()
{
int ans = 0;
int k = 0;
for(int i = 0; i < n; i++)
{
int len = strlen(a[i]);
for(int j = 0; j < len; j++)
{
while(k && a[i][j] != p[k]) k = nxt[k-1];
if(p[k] == a[i][j]) k++;
if(k == l)
{
ans++;
k = 0;
}
}
}
return ans;
}
int main()
{
init();
while(cin>>n)
{
for(int i = 0; i < n; i++)
{
scanf("%s", a[i]);
}
printf("%d\n", kmp());
}
return 0;
}