@rebirth1120
2019-08-08T09:31:04.000000Z
字数 1288
阅读 801
解题报告
洛谷
直接上题面吧
题目背景
一封好的情书需要撰写人全身心的投入。CYY同学看上了可爱的c**想对她表白,但却不知道自己写的情书是否能感动她,现在他带着情书请你来帮助他。
题目描述为了帮助CYY,我们定义一个量化情书好坏的标准感动值。判断感动值的方法如下:
- 在情书的一句话中若含有给定词汇列表中的特定单词,则感动值加1,但每一单词在同一句话中出现多次感动值不叠加,不同单词不受影响。保证输入的单词不重复。
- 每句话以英文句号定界。
- 全文不区分大小写。
输入格式
第一行包含一个数字n,表示导致感动值提升的词汇列表中单词的数量,随后n行是给定单词,每行一个。保证单词只包含英文字母。
最后一行为情书正文,保证只包含以下几种字符: 英文字母、数字、空格、英文逗号、英文句号。
输出格式
一个数字g,表示情书带来的感动值。
输入输出样例
输入 #1
3
love
so
much
I love you so much.输出 #1
3
说明/提示
对于所有的数据,保证1 ≤ n,m,k ≤ >100,每个单词不超过50字符,全文不超过1000字符。
第一眼,AC自动机?
看了眼数据范围,……
本来还以为要 kmp 的,但是这里出现的单词必须是一个完整的单词(也就是由空格或逗号或句号隔开的),那么,就直接暴力枚举吧……
虽然是道大水题,但是还是有些坑的,比如什么“全文不区分大小写。”,最后竟然交了 5 次才过……
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100+7;
const int M=50+7;
const int S=1000+7;
int n,len[N],ans;
char t[N][M],s[S];
void run(int lst,int end,int k){
int j=1;
for(int i=lst+1;i<end;i++){
if(s[i]==t[k][j]||s[i]==t[k][j]-'a'+'A'||s[i]==t[k][j]-'A'+'a') j++;
else{
j=1;
while(i<end&&s[i]!=' '&&s[i]!=','&&s[i]!='.') i++;
}
if(j==len[k]+1){
j=1;
if(s[i+1]==' '||s[i+1]==','||s[i+1]=='.'){
ans++;
return;
}
}
}
}
int main(){
//freopen("love.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++){
scanf("%s",t[i]+1);
len[i]=strlen(t[i]+1);
}
gets(s);
gets(s+1);
int lst=0;
for(int i=1;i<=strlen(s+1);i++){
if(s[i]!='.') continue;
for(int j=1;j<=n;j++) run(lst,i,j);
lst=i;
}
printf("%d\n",ans);
return 0;
}