题意分析

农夫约翰（Farmer John）记录了$M$（$1 \leq M \leq 1,000$）条短语，每条短语的长度在$1$到$60$之间，由字母（区分大小写）、标点符号（. , ?）或空格组成。现在有$N$（$1 \leq N \leq 10,000$）条录音消息，每条消息可能是短语本中某个短语的前缀（包括完全匹配的情况）。我们需要统计有多少条消息是短语本中至少一个短语的前缀。

解题思路

1. 输入处理

   • 读取$M$和$N$，然后读取$M$条短语存入列表phrases，再读取$N$条消息存入列表messages。
   • 由于比较是区分大小写的，因此不需要进行大小写转换。

2. 前缀匹配检查

   • 对于每条消息msg，检查是否存在至少一条短语phrase，使得msg是phrase的前缀。
   • 直接遍历所有短语，用字符串的startswith()方法判断即可。

3. 优化匹配效率

   • 最坏情况下，每条消息需要遍历所有$M$条短语，时间复杂度为$O(N \times M \times L)$，其中$L$是平均短语长度。
   • 由于$M \leq 1,000$，$N \leq 10,000$，$L \leq 60$，总计算量在$6 \times 10^5$左右，暴力匹配完全可行。

4. 输出结果

   • 统计满足条件的消息数量，输出答案。

标程

#include <iostream>
#include <cstring>
#include <algorithm> 
#include <cstdio> 
#include <vector>

using namespace std;
int main()
{
	int NUM1;
	int NUM2;
	scanf("%d %d ",&NUM1,&NUM2);
	string str2[NUM2];
	vector<string> str1;
	for(int i=0;i<NUM1;i++)
	{
		char str[300];
		gets(str);
		str1.push_back(str);
	}
	sort(str1.begin(),str1.end());
	int jg=0;
	for(int i=0;i<NUM2;i++)
	{
		char str[300];
		gets(str);
		str2[i]=str;
		int t=lower_bound(str1.begin(),str1.end(),str2[i])-str1.begin();
		if((t>=0)&&(t<NUM1))
		{
			if((str1[t].size()>=str2[i].size())&&(str1[t].substr(0,str2[i].size())==str2[i]))
			{
				jg++;
			}
		}
	}
	printf("%d",jg);
	return 0;
}