NOIP2011普及组T2 统计单词数

【题目描述】

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。

【输入描述】

2 行：

第 1 行为一个字符串，其中只含字母，表示给定单词；

第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

【输出描述】

只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。

【输入样例1】

To
to be or not to be is a question

【输出样例1】

2 0

【输入样例2】

to
Did the Ottoman Empire lose its power at that tim

【输出样例2】

-1

【输入输出样例 1 说明】

输出结果表示给定的单词 To 在文章中出现两次，第一次出现的位置为0。

【输入输出样例 2 说明】

表示给定的单词 to 在文章中没有出现，输出整数-1。

【数据范围】

1 ≤ 单词长度≤ 10。

1 ≤ 文章长度≤ 1,000,000。

【分析】

1. 题目是字符串处理问题，有一定难度。
2. 题目忽略大小写，所以要进行统一的大小写转换。
3. 比较坑的点，输入两行字符，末尾是换行“\n”不处理就会忽略掉第二行的输入。
4. 比较简单的一点是单词的长度较小。
5. 注意，空格也算位置。不能忽略空格去查单词的位置。
6. 当然，字符串有可能出现开头一堆空格，然后再是字符的。这个点更坑。

【思路1】

对于题目中句子和单词来说，匹配的时候遇到空格就可以断定前面的是单词，但是这样，最后一个单词就没法断定，因此可以在单词和句子后面单独加一个空格，这样减少匹配的难度。参考洛谷上一位大神的代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string> 
using namespace std;
int main()
{
	char word[11], sent[1000001]; //定义要读入的单词和句子
	int p=0,flag,sum=0,location; //定义 
	int i,j,k; 
	gets(word);
	gets(sent); //读入单词和句子
	strcat(word," ");
	strcat(sent," ");  //在单词和句子后面加上一个空格，便于匹配。
	strlwr(word);
	strlwr(sent); //统一转换成小写
	
	for(i=0;sent[i]!='\0';i++)  //遍历长的句子， 
	{
		if(sent[i]==' ') //当句子遇到了空格，说明前面的是一个完整的单词 
		{
			flag =1;
			for(j=p, k=0;j<=i,word[k]!='\0'; j++,k++)  //p记录了每个单词的起始位置 
			{
				if(sent[j]==word[k])
					flag*=1; //用flag来记录是否对应，如果每一位都一样，结果就是1
				else
					flag*=0; //一旦有一位不一致就是0  
			}
			if(flag==1)  //符合条件就计数 
				sum++; 
			if(sum==1 && flag ==1)   //记录第一次符合的位置 
				location=p;
			p=i;
			p++; 
		}
	} 
	 
	if(sum==0)
	{	
		sum=-1;
		printf("%d",sum);	
	}else if(sum>0)
	{
		printf("%d %d",sum,location);
	}
			
	return 0;
	
} 

---

返回目录：NOIP/CSP信息学奥赛复赛

---