Background
一封好的情书需要撰写人全身心的投入。CYY同学看上了可爱的c**想对她表白，但却不知道自己写的情书是否能感动她，现在他带着情书请你来帮助他。
Description
为了帮助CYY，我们定义一个量化情书好坏的标准感动值。判断感动值的方法如下:
1.在情书的一句话中若含有给定词汇列表中的特定单词，则感动值加1，但每一单词在同一句话中出现多次感动值不叠加，不同单词不受影响。保证输入的单词不重复。
2.每句话以英文句号定界。
3.全文不区分大小写。
Input
第一行包含一个数字n，表示导致感动值提升的词汇列表中单词的数量，随后n行是给定单词，每行一个。保证单词只包含英文字母。
最后一行为情书正文，保证只包含以下几种字符: 英文字母、数字、空格、英文逗号、英文句号。
Output
一个数字g，表示情书带来的感动值。
这题先要读清题好吧 emm。
每一单词在同一句话中出现多次,感动值不增加.
这个同一句话就是严格的同一句话.就是遇到'.'才算一句话。
还记得我当年写情书的时候,那时候.....
我们用\(Trie\)树来解决这一个匹配问题.
"为什么不用\(AC\)自动机",
"我太弱了 ,用不来。
因此,我用了\(Trie\)树.
我们对\(n\)个串构建\(Trie\)树.
对于情书中的,遇到一个标点符号(题目中的,空格,逗号,句号)就查询一次.
判断是否重复出现,就标记某个单词之前出现在哪个句子中即可.
我们每遇到一个句号,就将句子数量\(++\)。
统计答案的时候判断\(val[u]==cnt\)即可。
如果相同,那他们就在同一个句子中，\(return \ false\)
PS：返回\(true\)的条件还有,这个单词在\(Trie\)树中出现过.
读入很毒瘤！！！
样例没出但是A了QWQ
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register
using namespace std;
const int maxn=5008;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int idx,val[maxn*15],ans,cnt=1,n,len;
char tri[maxn*15][26],s[maxn];
inline void insert(R char *s,R int len)
{
R int u=0;
for(R int i=1;i<=len;i++)
{
R int v=s[i]-'a';
if(!tri[u][v])tri[u][v]=++idx;
u=tri[u][v];
}
val[u]=20011003;
}
inline bool query(R char *s,R int len)
{
R int u=0;
for(R int i=1;i<=len;i++)
{
R int v=s[i]-'a';
if(!tri[u][v] or s[i]>'z' or s[i]<'a')
return false;
u=tri[u][v];
}
if(val[u]!=cnt and val[u])
{
val[u]=cnt;
return true;
}
return false;
}
int main()
{
in(n);
char c;
for(R int i=1;i<=n;i++)
{
len=0;
while((c=getchar())!='\n' and c!=' ')
{
if(c>='A' and c<='Z')c=c-'A'+'a';
s[++len]=c;
}
insert(s,len);
}
len=0;
while((c=getchar())!=EOF)
{
if(c==' ' or c=='.' or c==',')
{
if(query(s,len))ans++;
len=0;
cnt=cnt+(c=='.');
continue;
}
if(c>='A' and c<='Z')c=c-'A'+'a';
s[++len]=c;
}
if(query(s,len)) ans++;
printf("%d",ans);
}